CSC 427: Data Structures and Algorithm Analysis
Fall 2006

HW6: 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 primitve GUI might look like the following (with the initial configuration on the left and the solved puzzle on the right):


For extra credit, impress me!

Note: late submissions will not be accepted for this assignment.