CS data structures project - sudoku solver
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. 1. 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 a public static final int Size that has the value 9. The final keyword 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. 2. Define a Board toString method Write a public 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 a main method you can run to test the constructor and the toString methods. The main method should create a new Board object and then print it. 3. Write the Board accessors and utility methods 1. public int getCols() - returns the number of columns 2. public int getRows() - returns the number of rows 3. public Cell get(int r, int c) - returns the Cell at location r, c. 4. public boolean isLocked(int r, int c) - returns whether the Cell at r, c, is locked. 5. public int numLocked() - returns the number of locked Cells on the board. 6. public int value(int r, int c) - returns the value at Cell r, c. 7. public void set(int r, int c, int value) - sets the value of the Cell at r, c. 8. 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. 4. 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. 1. Write a Board method to test if a value is valid Write a method public 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. 5. Position (1, 1) should be valid for a 4 only. 5. Position (1, 8) should be valid for a 2 only. 5. Position (8, 5) should be valid for a 4 only. 1. Write a Board method to test if the board is solved Finally, write a method public 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. 1. 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. 2. 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. 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. 3. Write a solve method Create a method public 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. 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. B. 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 1. Make a draw method in the Cell class In your Cell class, create a draw method public 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 the Graphics drawChars method to 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. 2. Make a draw method in the Board class In your Board class, create a public 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. 3. 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. 4. Control the speed of the visualization In your solve method add an int parameter delay. 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).