Solving Sudoku

This week we'll explore the game of Sudoku. In particular, you will write a stack-based solver for the game that implements a depth-first search algorithm. Once your code can solve Sudoku games, then you will explore how the number of starting values provided affects the complexity of the search for a solution.

Tasks

Testing

As always, as you are coding up this project create testing files for each class you create exercising the public methods implemented in this class. Follow the format of the test files we have been giving you this semester.

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.

    An auxiliary constructor should take in a String filename and call the read method.

  2. 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.

  3. 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.)

  4. 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.

  5. Randomly Generated Boards

    Add one more constructor that only takes an int parameter to specify the number of initial cells to be locked. Then randomly choose that many cells to give a fixed original value. Make sure that each cell is filled with a valid value using your method you created above.

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 with some number of pre-determined randomly placed values.

  2. Write a findNextValue method

    As we're working our way through a solution, we'll often need to find a valid value for a Cell. Moreover, we'll often need to backtrack, which means we'll revisit Cells for which we've already tried specific values, but we'll need to try new values. As such, this method will take in a Cell and use the Board::validValue method to determine if there is a valid value for this cell that we haven't tried. We can make sure that we are only searching over previously untried values by starting out search at the current value of the cell+1 and trying all remaining values up to 9. If there is a valid value, we should return that value; otherwise, we should return 0 to mark that no remaining values are valid.

  3. Write a findNextCell method

    We're going to need a method to help us find the next cell to go to and find an appropriate value for it. A reasonable default implementation of this is to go row by row and column by column looking for a cell whose value is still 0; upon finding it, use your findNextValue method to determine if there is a valid value to set it to. If so, update its value and return it; otherwise, return null to mark that there is no possible solution with the Board under its current setting.

  4. 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. 

    Allocate a stack, initially empty

while the stack size is less than the number of unspecified cells

    Create a cell called next by calling findNextCell.

    while next is null and the stack is non-empty:
        pop a cell off the stack
        call findNextValue on this Cell and set its value to the result
        if the cell's value is no longer 0, set next to this popped cell.
    
    if next is still null
        then the stack must be empty, so we can give up as we've tried all options
        return false
    else
        push next onto the stack

return true: the board contains the solution

    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 download this version of the class file, which has been updated to use a Board class instead of a Landscape.

  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). 

    public void draw(Graphics g, int x, int y, int scale){
    char toDraw = (char) ((int) '0' + getValue());
    g.setColor(isLocked()? Color.BLUE : Color.RED);
    g.drawChars(new char[] {toDraw}, 0, 1, x, y);
}
  2. Make a draw method in the Board class

    First, add a boolean field finished to your Board class. Update your Sudoku class to update finished appropriately in the solve() method. 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. 

    public void draw(Graphics g, int scale){
    for(int i = 0; i<getRows(); i++){
        for(int j = 0; j<getCols(); j++){
            get(i, j).draw(g, j*scale+5, i*scale+10, scale);
        }
    } if(finished){
        if(validSolution()){
            g.setColor(new Color(0, 127, 0));
            g.drawChars("Hurray!".toCharArray(), 0, "Hurray!".length(), scale*3+5, scale*10+10);
        } else {
            g.setColor(new Color(127, 0, 0));
            g.drawChars("No solution!".toCharArray(), 0, "No Solution!".length(), scale*3+5, scale*10+10);
        }
    }
}
  3. Add the LandscapeDisplay to the Sudoku class

    In your Sudoku class, add a LandscapeDisplay ld field to the class. In both constructors, assign to the field a new LandscapeDisplay, passing in the board as the argument.

  4. Control the speed of the visualization

    In your solve method add an int parameter delay. Then, at the start of each iteration of the while loop, add the following code.

    if (delay > 0)
    Thread.sleep(delay);
if (ld != null)
    ld.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).

    Include a picture of a solved board in your report

Exploration

Use your simulation to explore the following questions. Running your system 50-100 times for each case is sufficient. Note, you can always set the delay to 0 to maximize the speed of the solve.

  1. What is the relationship between the number of randomly selected (but valid) initial values and the likelihood of finding a solution for the board? For example, if you run 5 boards for each case of 10, 20, 30, and 40 initial values, how many of each case have a solution?
  2. Is there a relationship between the time taken to solve a board and the number of initial values?

    3. Include a table or otherwise present your results in your report.

Extensions

  1. Try other algorithms to find the best next cell to explore. For example, find the cell with the fewest possible choices of valid values. Compare your algorithm's performance on the same set of boards.

    Note, you will discover there are many examples on how to solve Sudoku puzzles on the web. If you use any of them as a reference, be sure to cite it in your report.

    If you simply copy the code from your source, you haven't really learned anything except how to do a reasonable web search, which is not the point of this course. It's also not likely to get you a lot of credit. If you want to learn something, read up on strategies, design your own algorithm, and write your own code. Describe your algorithm in your report. You will get far more points for a bad algorithm of your own design that you analyze than an algorithm copy-pasted.

  2. Make really good tester files, and write about your choices of how to implement specific tests.
  3. The game of sudoku can be generalized to different values of size (in this case, this is a game where size = 9). For example, a valid board for size = 4 could be 
    1 2 3 4 
3 4 1 2
2 1 4 3
4 3 2 1
    Extend your project so that size can be given as a parameter (you should probably confirm that size is a perfect square, ie size is 1, 4, 9, 16, etc.). Try to determine how performance depends on the parameter size.

Report

Your intended audience for your report are your peers not in the class, but who have taken a CS course. Your report should explain the core CS concept used, present the results of your program, and discuss the meaning of the results: what did you discover and does it make sense?

Your project report should contain the following elements. Please include a header for each section.