# CS 231: Project #3

Spring 2018

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

### 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. Open the Board.java file from the lab and use it 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 int Size that has the value 9. The basic constructor should have no parameters, should create a new 2D array of Cells that is Board.Size by Board.Size, and should initialize each location in the grid with a new Cell with value 0.
2. 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 following 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 value(int r, int c): returns the value at Cell r, c.
6. public void set(int r, int c, int value): sets the value of the Cell at r, c.
7. public void set(int r, int c, int value, boolean locked): sets the value and locked fields of the Cell at r, c.

When you are finished with these, test them in your main function.

4. 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. You can 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 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 1 only.
• Position (8, 5) should be valie for a 4 only.
6. Finally, write a method `public boolean validSolution()` that returns true if the board is solved. You can easily 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 actualy solve a puzzle. You need a constructor that can create a board with some initial values, a solve method, and a main method.

1. 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 will be all zeros.
2. Create a second constructor that takes in an int parameter that is the number of populated starting values N. Make a new Board. You will also want a Random object. Then start looping. 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.

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. Create a method `public boolean solve()` using the following algorithm. The algorithm is fairly stupid, as it goes Cell by Cell testing values from 1 to 9 in order. All of the locations visited so far get pushed onto a stack. If the algorithm gets to a Cell and can't find a valid value, it backs up to the prior Cell and tries a different number there. Formally, this is a depth-first search algorithm. As the maximum depth of the search path is 81 (the number of Cells on the board), the algorithm is guaranteed to find a solution if one exists. It is not guaranteed to be fast.

```    public boolean solve() {
// declare a CellStack variable and assign it a new CellStack of size 100

// declare int variables curRow, curCol, curValue, and time.
// set curRow, curCol, and time to zero; set curValue to 1

// while the size of the stack is less than Board.Size * Board.Size
// increment time

// if the cell at curRow, curCol is locked
// get the cell at curRow, CurCol and push it on the stack
// update curCol and curRow to be the next Cell
// note, the next Cell may be on the next row
// continue (go back to the start of the loop)

// Starting at the current value of curValue, loop over
// the remaining possible values.  If one is valid, break
// out of the loop.  Use a for loop for this.

// if curValue is a valid value (meaning < 10)
// create a new Cell with curRow, curCol, curValue
// set the Cell at curRow, curCol to have curValue
// push the Cell onto the stack
// update curCol and curRow to be the next Cell
// set curValue to 1
// else
// if the stack size is greater than 0, we backtrack
// Assign to a Cell variable the top of the stack (stack.pop())
// while the Cell is locked
// if stack size is greater than 0
// assign to the Cell variable the top of the stack (i.e. pop)
// else
// print out the number of steps (time)
// return false (no solution found)
// assign to curRow the row value of the Cell
// assign to curCol the col value of the Cell
// assign to curValue the value of the Cell + 1
// set the value of the board Cell at curRow, curCol to 0
// else
// print out the number of steps (time)
// return false (no solution found)

// 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. 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.
2. In your Cell class, create a draw method `public void draw(Graphics g, int x0, int y0, int scale)` that draw 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.
3. In your Sudoku class, add a LandscapeDisplay field to the class. In the both constructors, as the last statement 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. In your solve method add an int parameter delay. Then, right after incrementing the time variable, add the following code.
```    if( delay > 0 ) {
try {
}
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?

### Extensions

1. Develop a faster solve technique. In particular, you can try to find spaces with fewer possible valid values and start with those.

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.

• A brief description of the overall project, in your own words. Identify both the data structure used and the simulation built using it. Finish by indicating whether the simulation worked as expected and what you discovered.
• As explanation of your solution, focusing on the interesting bits. The interesting bits this week are your strategy for solvin the puzzle and what you found about solution complexity.
• Printouts, pictures, or results to show what you did. For this assignment, Initial and solved boards as well as some tables on solution complexity.
• Other results to demonstrate extensions you undertook. If you tried different solution strategies, for example, show how those affected the overall simulation results.
• A brief conclusion and description of what you learned.
• A list of people you worked with, including TAs, and instructors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester.

### Handin

Make your writeup 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:

`cs231s18project3`

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.