Project 4 - Sudoku Solver
Due Friday, 11/11 - 5:00pm
Due Friday, 11/11 - 5:00pm
For this project, you will revisit Project 1 and modify your Sudoku problem so that it can solve any puzzle that has a valid solution. This project will give you experience with the following:
- recursion
- code refactoring
- algorithmic thinking
Requirements
- All original functionality of the Sudoku program must be preserved.
- At each iteration of the main loop (in the play method of Game), the user may choose to solve the puzzle instead of entering a new value to insert into the puzzle.
- If the user chooses to solve the puzzle, your program will produce a solution to the puzzle by setting each empty square to an appropriate value. Print the valid puzzle and exit the program.
- If a valid solution does not exist, your program will print an error message and exit the program.
Hints
- You may use your solution to Project 1 or you may use the solution provided in /home/public/cs112/project1
- Consider implementing a method in Board that will take as input a row and column and will return a list of all possible numbers that can go in that square.
- Your solver will use recursion and backtracking to try every possible combination until a valid solution is found. The basic idea of the algorithm is as follows: find the next empty square, select a valid candidate value for a particular square, and then recursively solve the remaining puzzle. We will spend a bit of time discussing this algorithm during the class period.