CSC 427: Data Structures and Algorithm Analysis
Fall 2008
HW6: Sudoku and Recursive Backtracking
For this assignment, you are to design and implement a Java program for
solving Sudoku puzzles. If you are not familiar with Sudoku, it is played on
a 9x9 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 speed up the development of your solution, two classes are provided for you.
- SudokuGUI is a simple GUI that allows the
user to copy-and-paste a Sudoku grid into a text area and then click on a button
to see the solved grid in that area. Note: This class was built with the NetBeans
GUI builder using Java 1.6. You will also need to copy the
SudokuGUI.form file and save it in your NetBeans project to be able to edit this class. Since there were GUI library changes going from Java 1.5 to Java 1.6, this file will not compile if you are
using an older version of Java. In that case, you would need to rebuild a GUI from scratch and copy-and-paste the appropriate button code into your GUI class.
- SudokuGrid
is the framework of a class that stores and manipulates a Sudoku grid. You will need
to complete the definition of this class so that the fill method executes
the recursive backtracking approach to filling the grid with numbers. This will
no doubt involve writing numerous helper methods.
To assist you in testing your code, two sample Sudoku grids are listed below, with dashes
representing empty spots in the grid.
2 - 7 - - 3 - 8 -
- 5 - - 9 - - - 6
- - - - - - - - 9
- 4 - 2 - - - - -
- - 8 5 - 1 6 - -
- - - - - 4 - 3 -
4 - - - - - - - -
5 - - - 7 - - 2 -
- 3 - 9 - - 4 - 5
- - - - - - 5 4 -
- - 6 - - - - - 8
4 2 - 7 - - - - -
- - 3 6 7 - - - 2
- - - 1 - 8 - - -
9 - - - 4 2 1 - -
- - - - - 3 - 6 7
5 - - - - - 9 - -
- 9 2 - - - - - -
For full credit, your program should be able to solve any 3x3 Sudoku grid (assuming
it has a solution). For extra credit, make sure that your program also allows for solving
larger (square) boards, e.g., 16x16 or 25x25.