Skip to end of metadata
Go to start of metadata

Justin Gelwicks

CS231

Project 3: Solving Sudoku


Summary:

In project 3, we continued our work with 2D lists but implemented a new data-structure, the stack. Stacks are a very simple data structure that only allows things to be removed or added from the top, or last modified value. We used stacks with a 2D implementation in order to take in the information and solve a Sudoku board. To do this, I created a Cell class, which stored all the information and relevant cell methods. It was to be used in my Board class which created boards from cells and could also take in information about other boards, such as if a value is valid at a certain position on the board. In the end, I was able to solve given sudoku boards, but as the given values increased, so did the time it took to solve the board while the likelihood of being solved decreased.

Solution:

 The hardest part of this project was creating the ValidValue method in the Board class and the solve method in the Sudoku class. The ValidValue method checked each column and row to make sure it did not repeat any values. Then, it checked each 3x3 room to make sure that there were no repeat values.

The solve method in the Sudoku Class was quite difficult; it ran validValue until it encountered a case where the value would not work. Then, it went back on the stack, popped the previous value and tried others.

This is an example of the Sudoku class solving an empty board. I noticed that as I passed in more values, the time it took for the board to be solved increased exponentially. While all empty boards, and ones with only ten decided values, were solved, only about half of the twenty input boards were solved and none of the thirty and forty input boards were solved.


Conclusion:

This project was a great dive into visualization in java. It also exposed me to stacks, a data structure that I’m sure will be very useful in the future. This project was rewarding because it was the first time I was able to see my code tackle complex tasks

 

Collaborators:

TA hours

Office hours: Layton




Labels