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