CS 231: Project #3

Title image Fall 2019

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

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.

    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.

    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.

    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.

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

    • 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.
  6. 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.

    + (more detail)

    To construct a board with N valid, but randomly selected values, you will need a random number generator and a loop.

    Each time through the loop generate a random row, random column, and random value. If the board already has a non-zero value there, try again. If the location does not yet have a value, then test if the value is valid in that location using your board's validValue method. If it is valid, then insert the value into the board at that location and specify it as locked. If it is not valid, then try again.

    Note that the loop will likely need to execute more than N times to generate N valid values. You can implement this a couple of different ways. One is to explicitly keep track of the number of initial values that have been successfully created and exit the loop when that number reaches the desired value. The other is to use a regular for loop, but decrement the loop variable any time the value generation fails.

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

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

    + (more detail)

    The following is a more detailed version of the above algorithm you can use as a template if you wish. Each comment not starting with "Purpose" corresponds to one line of code.

        public boolean solve() {
            // declare a CellStack variable and assign it a new CellStack of size 100
            // declare an int variable time to hold the number of steps
            // declare an int variable numLocked and assign it the number of locked Cells on the board
    
            // Purpose: loop until a solution is found or no solution is possible
            // while the size of the stack is less than Board.Size * Board.Size - numLocked
                // increment time
    
                // Purpose: pick the next Cell to test, including its initial value guess
                // assign to a Cell variable best the result of calling board.findBestCell()
    
                // Purpose (if): there is a Cell with a valid value, so push it on the stack
                // if best is not null
                    // push the Cell best onto the stack
                    // set the board to match the Cell best
    
                // Purpose (else): no valid value found, backtrack to the last Cell with a valid value to test
                // else
                    // assign to a boolean variable stuck the value true
    
                    // Purpose: backtrack to a Cell that has a valid value to test
                    // while stuck and the stack size is greater than 0
    
                        // Assign to a Cell variable last the top of the stack (stack.pop())
    
                        // Purpose: check if there is another valid value to try at this location
                        // for v is assigned last's current value + 1; while less than 10; increment v
                            // if v is a valid value as last's location
                                // set the value of last to v
                                // set the board to match the Cell last
                                // push last on the stack
                                // assign to stuck the value false
                                // break out of the for loop
                        // Purpose: no valid value was found at the last location, so set it to 0
                        // if stuck
                            // set the board's value at the location of last to 0
    
                    // Purpose: check if there is no solution (backtracked all the way)
                    // if the stack size is equal to 0
                        // print out the time
                        // return false
    
            // print out the number of steps taken
            // return true

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

    Include a picture of a solved board in your report

Exploration

Use your simulation to explore the following questions. The analysis does not need to be extensive. Running your system 5-10 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.

  2. Make the visualization fancier. Add a button to reset the board and do a new solve. Add output statistics, titles, better coloring, etc.
  3. Make a version that lets the user play a Sudoku game. This will likely be a lot of work.
  4. Automate the process of exploring the trends in the simulation. An automated process should be able to analyze the results of hundreds or even thousands of games.
  5. A small extension is to enable your read method to handle the files with extra spaces.

Report

Your report should have the following format.

Handin

Make your report for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.

Once you have written up your assignment, give the page the label:

cs231f19project3

You can give any wiki page a label using the label field at the bottom of the page. The label is different from the title.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it in your folder on the Courses fileserver. Create a directory for each project inside the private folder inside your username folder.