Demonstrate the use backtracking to solve a "complex" problem.
Manipulate subsections of a 2D array
Description
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:
Create a simple Sudoku class.
instance data includes:
int boardSize
int boxSize
int[][] board
A constructor that takes 2 parameters: size and scan
size is assigned to boxSize
scan is used to read
input and initialize the board.
other instance data should be set.
A method that can be used to print the board.
Create a SudokuSolver class
Should use command line arguments to get a filename
Creates a scanner object (using the filename)
Reads the first number from the file 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
Creates a new Sudoku object
Test your code to make sure that you are adequately creating and
printing the puzzle board! You can download Puzzles.tgz for some sample files.
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 want to
create a few of your own that are different from the ones that you
downloaded.
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 do I do if I tried a
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?
Create a tar file that contains your two java programs
and any test puzzles that you created email it to me
by