Project 4 - Sudoku Solver

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

1. All original functionality of the Sudoku program must be preserved.
2. 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.
3. 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.
4. If a valid solution does not exist, your program will print an error message and exit the program.

Hints

1. You may use your solution to Project 1 or you may use the solution provided in /home/public/cs112/project1
2. 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.
3. 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.