We are going to write a program that can be used to solve Sudoku
puzzles. Typically the puzzle is defined as follows:
There is a 9x9 grid that is subdivided into nine 3x3 boxes.
The object of the puzzle is to fill the grid such that the digits
1 to 9 are contained (without repeats) in
each row
each column
each box
Some digits are initially placed in the grid to get started and
to establish contstraints that make the solution to the puzzle unique.
To Do
When humans try to solve Sudoku puzzles, they rely on the existing
numbers and logical reasoning to solve the puzzle. In
contrast, the program that you are going to write relies on the
speed of the computer to simply try all possible combinations until a
valid solution can be found.
You will need to do the following:
As you work on this assignment, you will be required to keep a journal
of the work that you are doing. Entries to your journal, Proj2Notes.XXX
(where XXX are your initials) should be made:
Whenever you complete a major component of the project. Provide details
on how much time you spent focused on that component
Whenever you have a major obstacle that you needed to overcome. If
there is a portion of the assignment that caused you to struggle, I would like
you to detail the problem and how you eventually overcame the problem.
To provide details regarding testing of your program. Indicate what
tests you ran to verify that your program is functioning correctly and how you
know that these tests are sufficient
Create a simple Sudoku class.
instance data includes:
int boardSize
int boxSize
int[][] board
A constructor that
Gets a number from input and uses that to determine
the boxSize of the puzzle
Your program should work generally for puzzles with boxSize 2
and 3 without any specific code handling
Reads additional input to initialize the board.
A method that can be used to print the board.
Create a SudokuSolver class that simply creates and prints
a new Sudoku object
Test your code to make sure that you are adequately creating and
printing the puzzle board. Since you will be doing a lot of testing, it
probably makes sense to use I/O redirection to feed data files to your program.
You can download
Puzzles.tgz for some sample files.
You should also create a couple of your own.
To solve the puzzle, you will need three "helper" methods
to determine if a move is valid:
boolean validRow(int num, int row)
boolean validColumn(int num, int col)
boolean validBox(int num, int row, int col)
These should all be private; external classes should not have
aceess to them - instead these methods will all be called by an overall
method called validMove(int
num, int row, int col).
Verify that these methods work completely
by calling validMove from your SudokuSolver class
with some sample puzzle files. You will probably need to
create a few of you additional puzzles that provide good test conditions for
these methods. (make sure to document testing in your journal)
Write a recursive function that finds a solution to the puzzle if
one exists - (return false if there is not a valid solution, otherwise
return true). Some things that you will need to think about:
What is the base cases?
What do I do when I reach the end of a row?
What do I do when I reach the last column?
What do I do if I tried an invalid number?
What if the the grid spot was already filled in (i.e. it was
one of the puzzle constraints)
When do I backtrack?
What do I need to do when I backtrack?
Bonus
One of the things that make Sudoku fun for humans to try to solve is
if that they have exactly one correct solution. As you have currently
implemented sudokuSolver, it gives you the first solution - but there
may be others that exist. Create a variation of your program called
validSudoku that verifies that there is exactly one solution.
Hand In
Create a tar file that contains your journal, your javaDoc,your java programs
and any test puzzles that you created email it to me. Submit hard copies of your journal, and your source code.