###
CSC 427: Data Structures and Algorithm Analysis

Fall 2007

HW5: Sudoku and Recursive Backtracking

For this assignment, you are to design and implement a GUI-based Java program for
solving Sudoku puzzles. If you are not familiar with Sudoku, it is played on
a 9-9 puzzle grid in which the numbers 1 through 9 are placed.

To complete a puzzle,
the player must fill in the remaining positions of the grid such that the numbers
1 through 9 appear in every row, column, and 3x3 subsquare. For a person, solving
a Sudoku puzzle requires complex and careful logical reasoning.
However, it turns out that even the most challenging Sudoku puzzles can be easily
solved by a computer using recursive backtracking. In pseudocode:

while there are any empty spots
pick an empty spot & place a number in it
if a conflict occurs (i.e., a duplicate in any row/column/subsquare),
then remove the number and backtrack
To complete your Sudoku solver, you will need to design and implement a class
for representing a puzzle grid, including a method for solving the puzzle via
recursive backtracking. You will also need to create a GUI for entering the
initial board and displaying the solution. For example, an *extremely primitive*
GUI might look like the following (with the initial configuration on the left and
the solved puzzle on the right):

Additional features may be added to the interface for extra credit. For example,
it would be convenient to be able to load a puzzle directly from a file. You might
also add a button that checks to make sure the puzzle has only one solution.
*Impress me*!