Sudoku is a puzzle that has been found in most newspapers since it gained popularity in 2005. Typically, the puzzle is played with a 9x9 grid that is subdivided into nine 3x3 boxes. The object of the puzzle is to fill the grid such that the digits 1 to 9 are contained (without repeats) in each row, each column, and each box. Seed digits are initially placed in the grid to define the puzzle and to limit where additional digits can be added by the person solving the puzzle. A puzzle is considered valid if the seed digits constrain the puzzle so that there is exactly one way to fill the remaining grid spaces. When trying to solve a Sudoku, people rely on logical reasoning to determine where certain digits can and cannot be placed in the grid. This is only fun when you are working on a valid puzzle. If there is more than one solution, it would be impossible to reason through; at some point you would have to guess. Clearly having no solution would be quite disturbing too. Is it possible to write a computer program that a) solves these puzzles and b) can discriminate valid puzzles from invalid ones? Yes - and you are going to write it!
Instead of trying to reason through the solution, you are going to use a brute-force approach to attempt to solve the puzzle and determine if your solution is unique. Begin by creating a class that represents a sudoku puzzle. Assume that puzzles are a 9x9 grid. Include an instance variable that represents a board, and a constructor that reads a file that represents a board. To display a sudoku puzzle, create a toString method. Test your class on the files in the tar file Puzzles.tgz. Note that empty cells have the value 0.
In order to solve a puzzle, you should create a method validMove that when given a row, a column, and a value to place it into the specified cell, it returns true if the move is valid and false otherwise. This method would benefit from three helper methods that test each of the three conditions that would cause a move to be invalid.
Create a recursive method in the puzzle class that solves a puzzle by testing every possible move in every possible cell. The method should have parameters for the current cell and for the number to try in the current cell. It should also return true if it was able to solve the puzzle and false if it was not able to. The recursion will be helpful, because if there is no move that produces a solution for a particular cell, then there is an error in a move that was previously performed. Recursion allows the program to backtrack to the problem easily.
Next, create a recursive method that determines whether a puzzle is valid, that is it has only one solution. This function will be similar to the last. Finally, create a program that reads puzzle files and outputs a unique solution if there is one, otherwise it should print that either the puzzle is not unique or it does not have a solution.
Hand In: Tar and email your code to your instructor with a subject of cpsc170 postlab10.