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.

Hint: If your experiment is taking too long to run, consider adding a timeout so that if your solve method runs for more than some number of iterations, it just gives up. Some boards will be solveable/not solveable before the timeout is reached, but some boards take a very long time to figure out whether they have a solution or not with the method we implemented!

  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? How many of them timeout?
  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.


Reflections

1. Breadth-First or Depth-First?

In your report, consider and discuss why we used depth first search instead of breadth first search in this project. Be as explicit as possible - I'd expect some sort of computation...

2. Making Good Boards

As you may be aware, the New York Times has a puzzle website that they update daily with some games. One of those games is Sudoku! If you check out the hard puzzle, you'll notice that there's some starting values, but they're somewhat sparse (compared to the easy puzzle, anyway). However, even though there's a relatively small number of starting cells, there is always exactly one valid solution that stems from these starting values. Obviously, this is not the case with the randomly generated boards you have made so far.

Your task for this question is to (randomly) create boards with a reasonably small number of starting values but from which only one valid solution can be written. There are a couple different ways of doing this, but I suggest the following:

  1. First, get any solved board. A reasonable way to do this is just start with a blank board and call solve.
  2. Next, permute the symbols of the board. To do that, you can just copy this code into your Board class:
    /**
    * Randomly permutes the symbols used in the solution.
    */
    private void randomPermute(){
        int[] permutation = new int[getRows()];
        Random rand = new Random();
        for(int i = 0; i < getRows(); i++){
            int swapIndex = rand.nextInt(i + 1);
            permutation[i] = permutation[swapIndex];
            permutation[swapIndex] = i;
        }
    
        for(int r = 0; r < getRows(); r++){
            for(int c = 0; c < getCols(); c++){
                set(r, c, permutation[value(r, c) - 1] + 1);
            }
        }
    }
    
    After you copied it in, when your Board is solved just called random permute and you'll get a random new solution!
  3. Technically, we've now got a Board that has exactly 1 valid completion (since it's already solved, that completion is achieved by doing nothing). What we want is a Board whose only valid completion is this one. One way of doing this is randomly removing values as long as doing so doesn't increase the number of possible solutions. Obviously, the difficulty here is determining if removing a value admits a new possible solution. There are a number of different ways to do this; probably the easiest way is to make a method like public int numSolutions() that returns the number of solutions which can be built from the current board (I would probably make sure to lock all non-zero entries at the start of this method). Conveniently, you can do this by copying your code over from solve and adding ~3 lines of code.
In your report, include a couple boards you were able to create with a reasonably small number of starting values and discuss how you implemented it along with any choices you made along the way.


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.