Tasks
Board Class
The Board class holds the array of Cells that make up the Sudoku board. It will be able to read a board from a file, test if a value is valid at a certain position on the board, and test if the board is solved.
Define the Board fields and constructor
Use your Board.java file from the lab as a starting point. Give the Board class one private field that is a 2D array of Cells. You may also want to create apublic static final int Sizethat has the value 9. Thefinalkeyword means the value cannot be changed.
The default constructor should have no parameters, should create a new 2D array of Cells that is Board.Size by Board.Size, and it should initialize each location in the grid with a new Cell with value 0.
Define a Board toString method
Write apublic String toString()method that generates a multi-line string representation of the board. To make it easy to examine the board, you may want to have spaces that separate the 9x9 board into 3x3 blocks. When you have written this function, write amainmethod you can run to test the constructor and the toString methods. The main method should create a new Board object and then print it.
Write the Board accessors and utility methods
- public int getCols()- returns the number of columns
- public int getRows()- returns the number of rows
- public Cell get(int r, int c)- returns the Cell at location r, c.
- public boolean isLocked(int r, int c)- returns whether the Cell at r, c, is locked.
- public int numLocked()- returns the number of locked Cells on the board.
- public int value(int r, int c)- returns the value at Cell r, c.
- public void set(int r, int c, int value)- sets the value of the Cell at r, c.
- public void set(int r, int c, int value, boolean locked)- sets the value and locked fields of the Cell at r, c.
Note, a locked Cell is one whose value is fixed. These are the Cells in the board with fixed initial values. These Cells should never be modified while solving the board.
When you are finished with these, test them in your main function.
Complete the Board read method
Update the read method from lab so that it fills in the board values when given a file with 9 rows of 9 digits separated by spaces.
Use the following test files to evaluate your read method. The first two files have no extra spaces or empty lines. The second two files have extra spaces and lines which you may have to modify your read method to handle. Handling the second two files is optional and a small extension.
Board 10 initial values
Board 10 solved
Board 20 initial values
Board 20 solved
Test your read method by updating your main function so it reads in a file, possibly using a command line argument, and prints out the resulting Board.
Write a Board method to test if a value is valid
Write a methodpublic boolean validValue(int row, int col, int value)that tests if the given value is a valid value at the given row and column of the board. It should make sure the value is unique in its row, in its column, and in its local 3x3 square. You can figure out which local 3x3 square it is in by using integer division. (Note, you probably want to test that the value is in the range [1,9] before doing anything else.)
Test your function by updating your main function so that it tests values on a solved board. For example, read the solved board 10 above and check at least the following cases.
- Position (1, 1) should be valid for a 4 only.
- Position (1, 8) should be valid for a 2 only.
- Position (8, 5) should be valid for a 4 only.
Write a Board method to test if the board is solved
Finally, write a methodpublic boolean validSolution()that returns true if the board is solved.
You can do this by looping over all of the Cells on the board. If any of the Cell values are 0 or are not valid (see prior function) then the board is not solved. If all of the Cells are between 1 and 9 and all the Cells are valid, the board is solved.
Update your main function so that it tells you if the Board read from a file is solved or not and make sure it works.
Sudoku Class
The next task is to write the Sudoku class that will actually solve a puzzle. You need a constructor that can create a board with some initial values, a solve method, and a main method.
Define the Sudoku fields and constructor
Create a Sudoku.java file, import java.util.Random, and create a public class Sudoku. The class should have a field for the Board object. Make a constructor that creates a new Board. By default, the Board should be all zeros.
Define a second constructor to create interesting boards
Create a second constructor that takes in an int parameter that is the number of populated starting values N. Initialize the board to have N randomly selected valid values.
+(more detail)
Once your constructor is written, test it by creating a main method that generates a board with initial values and prints it out. Use a command line parameter to control how many initial values there are.
Write a solve method
Create a methodpublic boolean solve()using the following algorithm, which uses a stack to keep track of the solution and allow backtracking when it gets stuck. At a high level, the algorithm is as follows.
Given: a stack, and the number of locked cells
while the stack size is less than the number of unspecified cells
select the next cell to check (this is where you add smarts)
if there is a valid next cell to try
push the cell onto the stack
update the board
else
while it is necessary and possible to backtrack
pop a cell off the stack
check if there are other untested values this cell could try
if there is another valid untested value for this cell
push the cell with its new value onto the stack
update the board
break
else
set this cell's value to 0 on the board
if the stack size is 0 (no more backtracking possible)
return false: there is no solution
return true: the board contains the solution
You probably want to write a board function to find and return the next cell to check:public Cell findBestCell()
- A simple approach to selecting the next cell is to scan the board by rows from the upper left to find the first cell with a 0 value. Then start checking the possible values from 1 to 9 using the validValue method. Use the first valid value found. If the cell has no valid value, then return null, which forces the algorithm to backtrack. Don't keep searching for a cell with a value. If a cell with no valid value is found, return null.
- A more sophisticated approach is to find the cell (anywhere on the board) with the fewest valid value options and try it first. In some cases there may be only one valid value. If there is a cell with no valid options, return null so the solver can backtrack.
Once you have coded up the solve algorithm, update your main method and try it on a board with 0 initial values. It should be able to find a solution very quickly for that case. Then test it on board 10 which has a solution. Have your program print out both the initial and final boards. Make sure the solution is a valid solution by checking it yourself.
LandscapeDisplay Class
The final part of the project is to use the LandscapeDisplay to create a visualization of the board. You can downloadthis versionof the class file, which has been updated to use a Board class instead of a Landscape.
Make a draw method in the Cell class
In your Cell class, create a draw methodpublic void draw(Graphics g, int x0, int y0, int scale)that draws the Cell's number. The x0 and y0 are a global offset for the board so it does not have to be smashed up against the upper left corner. The scale is how big a grid cell should be (30 or 40 are good values). you can use theGraphics drawChars methodto draw a character. You can use the expression(char)('0' + this.value)to create the proper character to be drawn. If you want, make each digit a different color.
+(more detail)
Make a draw method in the Board class
In your Board class, create apublic void draw(Graphics g, int scale)method. The method should loop over the board and call the draw method of each Cell. In addition, you may want to draw lines to divide the board into 3x3 blocks.
Add the LandscapeDisplay to the Sudoku class
In your Sudoku class, add a LandscapeDisplay field to the class. In both constructors, assign to the field a new LandscapeDisplay, passing in the board as the first argument and the scale factor (e.g. 30) as the second.
Control the speed of the visualization
In your solve method add an int parameterdelay. Then, right after incrementing the time variable, add the following code.
if( delay > 0 ) {
try {
Thread.sleep(delay);
}
catch(InterruptedException ex) {
System.out.println("Interrupted");
}
display.repaint();
}
This will update the visual display live as it tries to solve the board. Update your main method so it calls solve with a delay of 10 (which is 10ms).