In this project, I implement a depth-first search algorithm to simulate the game of Sudoku. The main concept is stacks. A Stack is a data structure that follows a Last In First Out(LIFO) rule, which means we can only add an item at the top of the stack(push) or remove an item from the top of the stack(pop).
At the end of the project, I analyzed the relationship between the number of initial values and the performance of the solver by running a large number of simulations.
2. Board Class
The Board class holds the array of Cells that make up the Sudoku board. It is 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.
I made an overloaded constructor that could directly read a file passed in as a parameter when I created a new Board and modified my read() method accordingly.
The toString() method generates a multi-line string representation of the board. I separate the 9x9 board into 3x3 blocks using spaces by adding two if statements to check the row and column indices and add a new line or spaces accordingly.
The validValue() method tests if the given value is a valid value at the given row and column of the board. It makes sure the value is unique in its row, in its column, and in its local 3x3 square. I made two for loops and a double for loop with if statements in them to check if a value is valid.
To check the 3*3 sub grids, used integer division to handle this functionality. I first initialize two variables that determine the index of a 3*3 block. Knowing which block the value is in, I can check its local 3*3 grid to see if it is valid.
The validSolution() method returns true if the board is solved. I did this by looping over all of the Cells on the board.
3. Sudoku Class
The Sudoku class has a constructor that creates a board and a solve method so that it can solve a puzzle.
The second constructor takes in an int parameter referring to the number of initial values. I made an if else statement in the for loop to insert a valid value or try again if the value is invalid.
The solve() method goes Cell by Cell testing values from 1 to 9 in order. I use a lot of while loops, for loops, and if else statements.
An example of the method's functionality is that it tries every possible value in the range [1, 9] and breaks out the loop if it finds one valid value.
To handle the special case where the next Cell is on the next row, I use an if statement to check the location of the Cell.
4. LandscapeDisplay Class
The LandscapeDisplay class creates a visualization of the board. I implemented draw() methods in my Board class and Cell class.
The draw() method in the Board draws lines to divide the board into 9 sub-grids. The approach is basically the same as what I did to separate the 9x9 board into 3x3 squares using spaces.
In my draw method, I also swapped the order of row and column to adjust to the predesigned implementation of the LandscapeDisplay class to keep the landscape consistent with the board in the terminal.
A solved board is shown below.
The draw() method in the Cell class draws the Cell's number. I used the Graphics drawChars method to draw a character.
- 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?
The higher the number of initial values, the less likely it is to find a solution for the board. When the number of initial values is below 20, the board can always be solved. When the number of populated values gets larger, the solved times gradually decrease. After the number of initial values is larger than 25, the board cannot be solved any more.
2. Is there a relationship between the time taken to solve a board and the number of initial values?
When the number of initial values is below 20, which means the board can always be solved, the time taken to solve a board increases as the number of initial values becomes larger.
When the number of initial values gets above 25, which means the board can never be solved, the time taken decreases as the number of initial values increases because it takes less time for the solver to realize the board is unsolvable.
When the number of initial values is between 20 and 25, the relationship is random and not linear.
1) Make the visualization fancier.
Firstly, I modified the LandscapePanel class and changed the background color to black.
Secondly, I created a Random object in the Cell's draw method to generate random colors for the numbers and made them brighter using the brighter() method.
I also changed the font of the numbers to Georgia.
Finally, I drew lines to separate the big grid into 9 sub-grids, as explained above.
2) Add a button to reset the board and do a new solve. Add output statistics.
In the LandscapeDisplay class, I added two JButton objects to solve and reset a Board.
In my Sudoku class, I initialized two static variables Reset and Solve with default values false.
Then, I created a private class Control where I used two if statements to change the values of Reset and Solve to true after I press the buttons.
In the main function, I made a while loop with if statements to create a new Sudoku object if I press "Reset" and to solve a Sudoku if I press "Solve."
I also made a Scanner object to allow user to control the number of initial values in the terminal. Every time the game gets reset, the user is asked a question and needs to enter the number of initial values.
Another thing I did is to display the output statistics in a dialog box. In the LandscapeDisplay class, I created an output() method taking in two parameters–time and result--that uses the showMessageDialog() method of JOptionPane to show the time taken and the result of a game. Back to my Sudoku's main method, I call the output() method on a LandscapeDisplay object with time and result that are determined by the solve() method above.
The procedures are like this:
Firstly, I run Sudoku in the terminal, and it will pop up a question asking me to input the number of initial values on the next line.
After I hit Enter, a window appears, where the board has 10 initial values.
When I press the "Solve" button, it will solve the board.
And a dialog box shows up as well, indicating the steps taken and whether the board is solved or not.
If I press the "Reset" button, the same question shows up again.
This time, I set the number of initial values to be 5. And the board gets refreshed with 5 initial values on it.
And then I can solve the board again.
3) Automate the process of exploring the trends in the simulation. An automated process should be able to analyze the results of hundreds of games.
I created a new Automation class with a method auto() that returns a String showing the results of games and a main method that takes in command line arguments and prints the String returned by auto().
I first initialized three variables to keep track of the steps and the solved/unsolved times.
In a for loop, I increment the variables depending on the results.
Then I calculated the average steps taken per board and put the statistics into a String.
I simulated hundreds of games, trying to find the trend in the average steps.
My computer died when I played more than 600 games, so I only included 5 sets of statistics. However, the relationship between the number of games played and the average steps taken is not clear enough to draw a conclusion. So I decided to choose a pivotal number 25 as the number of initial values.
The relationship between the number of games and the solved/unsolved times:
The relationship between the number of games and the solved percentage:
From the chart, we can see that as the number of games increases, the percentage of a board being solved slightly grows and tends to be stable.
The relationship between the number of games and the average steps:
The average steps taken to solve a board fluctuates but generally increases as the number of games becomes larger.
4) Enable your read method to handle the files with extra spaces.
I modified my read() method in the Board class to handle files that have extra spaces and lines. The big idea is to replace the spaces with empty strings.
I read from a text file board_sp_20_solved.txt that has extra spaces and lines.
The output in the terminal is shown below:
5) Identify in comments when dynamically allocated memory is being "lost." Dynamic memory is any memory created with a
new command. Indicate the line of code in which the last reference to an object referencing dynamic memory is removed.)
CellStack.java line 36
From the project, I learned the new data structure–stacks and how to use backtracking to build a solver. However, the algorithm is inefficient regarding the time taken to solve a board. It was challenging but interesting to handle the details in designing a Board and a game of Sudoku.