Sudoku is (I am told) an old game that is currently quite popular and giving crossword puzzles a run for their money in newspapers. It's a game well suited for computers because it is a matter of finding legal placements for numbers on the board.
The game: Sudoku is played on a 9 x 9 grid. Initially, a few of the cells of that grid contain a numbers, all integers between 1 and 9. The goal for the player is to fill in the remaining cells of the grid, also with integers between 1 and 9, given the following constraints:
Each value (1 through 9) must appear exactly once in each row.
Each value (1 through 9) must appear exactly once in each column.
Each value (1 through 9) must appear exactly once in each 3 x 3 sub-grid, where the 9 x 9 board is divided into 9 such sub-grids.
A valid Sudoku game begins with initial numbers that, when combined with the constraints above, admit exactly one complete solution. That is, the initial numbers cannot make it impossible to fill in the board legal, nor can they allow multiple solutions.
The first part of your project is to write a Sudoku verifier. That is, you must write a method that accepts an allegedly solved Sudoku grid and then verifies whether the solution is valid.
For this part of the project, you will be given three pre-made solvers. One of the solvers works correctly, the other two do not. You must use your verifier to determine which solver works. You should also try to figure out in what way the other two solvers fail.
Details: This program is split into a number of files. Some of them are code that I have written that you will simply use. Others are files that you must modify or write.
Sudoku.class: This file contains the Sudoku class whose main() method will be used to drive the program. It reads a file that describes an initial Sudoku board, prints the initial (unsolved) board, calls the requested solver, prints the final (solved) board, and then calls the verifier on that solved board. It's the conductor of this show.
SolverA.class, SolverB.class, and SolverC.class: These are the pre-compiled Sudoku solvers, SolverA, SolverB, and SolverC, that you are seeking to evaluate. Code within Sudoku calls on the code within these solvers.
SolverX.java: This is the solver that you will write in part B of the project. It exists currently as a placeholder (lest the compiler get upset that Sudoku is trying to call on SolverX methods; that is, this solver doesn't do anything. You can open the file and see for yourself. You must compile this file (even in its impotent state) in order to work on part A of the project, even though you won't use this solver at all.
Verifier.java: This file contains the class Verifier. Sudoku relies on this class to contain one particular method:
public static boolean check (int[][] grid)
This is the method that Sudoku code calls to test an allegedly solved grid. Your code must correctly determine whether the grid is solved or not, returning true if it is and false otherwise. Note that you are welcome to add additional methods to this file that support the check method. Also note that, like the solve method in SolverX, there's currently a placeholder method that simply returns false.
Files that you need: You must copy some files from my directory to get started on this project:
cp -v ~sfkaplan/public/cs12/project-8/*.* .
Here is a quick description of the files:
Sudoku.class: The entry point to the program (that is, it contains main()). It reads the file that describes the initial state of the game, calls a solver, calls a verifier on the solution, and then prints the outcome.
Solver[ABC].class: Three classes that contain solve() methods that can be called by the Sudoku class. Two of these methods produce incorrect solutions, while the third produces legitimate solutions.
SolverX.java: The skeleton of a new solver class. It currently contains a solve() method that can be called by the Sudoku class, but that method currently does nothing. It is your job, for Part B, to write this method (and other methods that will support it), such that it correctly solves Sudoku puzzles.
Verifier.java: The skeleton of a verifier class. It currently contains a check() method that can be passed a Sudoku board by the Sudoku class, but currently the method does nothing. Your job, for Part A, is to write this method (and its supporting methods) such that it tests the given Sudoku board, returning true if it is a correctly solved Sudoku puzzle, and returning false otherwise.
sudoku.board: A sample Sudoku puzzle. The 0 values are stand-ins for the blank spaces in the initial state of the board. The non-zero values are initially placed ones that should never be changed.
Running the program: Once you have written a Verifier class, you can compile your .java files and run the program like so:
java -server Sudoku sudoku.board A
First, note the use of -server. The (unsatisfying) explanation for this addition is that it will make the program run faster -- I'll explain how during lab. Second, note the two command-line arguments passed to the program. sudoku.board is the name of the file that contains the initial description of the board, and A is the name of the solver to use (that is, this example will call on SolverA to compute a solution).
HINT: Before you change the check method in Verifier.java, try compiling all of the .java files and running the program. It should work, and you can see how the thing is going to operate. Then begin modifying the check method so that it actually performs its intended task.
As described above, there is an additional, fourth solver, namely SolverX. Armed with a working verifier, you should now write your own solve method within SolverX.java. It will accept an initial grid (as an int[][]), and its job it then to fill in the empty cells of the grid with values. Your method must of course obey the constraints on those values, thus producing a correct solution.
Part A: Use the cs12-submit command to turn in your Verifier.java file as project-8a. Also submit a text file named observations.txt that indicates which solver you think is the correct one. Also describe what types of errors the two flawed solvers produce.
Part B: Use the cs12-submit command to turn in your SolverX.java file as project-8b.