Pages William B. Fitch’s Home CS 231 S20 CS 231 Project 3

Abstract

The project was about making a program that would solve Sudoku puzzles. The purpose of this project was to learn about Stacks, how they're designed and how to use them effectively. I used the Stack to store the potential solutions to each Sudoku board. The solver would push new cells onto the Stack until there was no legal way to continue. Then it would back up and retry by popping cells back off the Stack.

Methods

The main data structure used in this project was a Stack. It stores data in a "stack" by storing the data in various arrays. It actually only stores one array, and when it needs more space it makes a new array of twice the size. The Stack is useful because it is a very simple data structure of variable size which can store data efficienty.

Specifically, in this project I used a "CellStack" class which I wrote to hold Cells. A major difference between this and the built in array is that mine can ONLY store cells, whereas the built in Java Stack can store any object. The Stack functions by having a variable which references the top of the stack and an array storing the values. To add a Cell, it is put in the top of the stack + 1 position of the array. If there is not enough space, a new array of twice the size is created and the data is copied over. To pull from the Stack, the Cell at the top of the stack is returned, and the top of the stack variable reduced by 1.

Results

As more fixed starting values are added to the Sudoku's, fewer of the randomly generated boards have solutions. See the following printout from my built-in test:

With 10 starting positions 198 out of 200 were solvable. 99.0%

With 20 starting positions 140 out of 200 were solvable. 70.0%

With 30 starting positions 2 out of 200 were solvable. 1.0%

With 40 starting positions 0 out of 200 were solvable. 0.0%

On a smaller scale, when I ran the boards by hand, the boards with more starting values also took longer, but only when they had a solution. This makes sense, as the board with 10 starting positions would have more than one solution, so its more likely that one could be found relatively quickly. On the other hand, when there are no solutions, the program can figure it out relatively quickly by seeing if any cells have 0 possible values.

When I ran the boards on my own, 30 and 40 starting values were usually the fastest, as they were usually unsolvable, followed by 10, and then 20 which took the longest

Extensions

I modified the file reader in Board.java so it could parse spaced. I also implemented a way for the program to automatically run many boards and keep track of how many were solvable. I also implemented a method to allow the solver to use the best possible cell instead (determined by the one with the lowest number of possible values) instead of just the next cell. Additionally, I updated the graphics so it looks like a real sudoku board.

Reflection

I learned how to make Stacks and use them and implement solutions with them. I also learned how to parse files in Java. I also learned about do while loops.

Acknowledgements

Benjamin Raivel

Benjamin Southwick

Cynthia Rosas

Matthew Cerrato

Labels
• No labels