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.

  1. 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.
  2. 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.