CSC 427: Data Structures and Algorithm Analysis
Fall 2010

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:

as long as 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 if there is no conflict, attempt to fill in the rest of the grid if you are unable to fill the rest of the grid (i.e., a future dead-end is reached), 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 an adjacent area. You may use this crude GUI, augment it, or design your own. Note: that you will also need to download the SudokuGUI.form file and in order to edit the GUI in netBeans.
  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 fillGrid 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 90% CREDIT: Your program must be able to solve any 9x9 Sudoku puzzle (assuming it has a solution).

FOR 100% CREDIT: Your program must be able to solve any square puzzle up to 25x25 (assuming it has a solution).

FOR 110% CREDIT: Your program should have an additional feature that checks to make sure that the puzzle solution is unique. This will involve continuing the search after the first solution is found (i.e., pretending that solution doesn't exist) to see if another solution can be found. If so, your program should warn the user that the puzzle has multiple solutions.