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:
<![CDATA[
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.
- 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.
- 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.
<![CDATA[
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.