The game of Sudoku

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.

Your assignment

Copying files from my directory

You must copy some files from my directory to get started on this project. To do so, follow these steps:

1. Login to remus/romulus and open a shell.

2. Create a project-4 directory and change into it.

3. Issue the following command from within your project-4 directory:

   cp -r ~sfkaplan/public/cs11/project-4/* .

If you look at your directory (use the ls -l command), you will see that there is one Java class file (Support.class) and three Sudoku board files (e.g., medium.board). Much like project 3, you will need to call the Support methods for particular tasks, and you will use the Sudoku board files to test your code. More on these later.

What you must write

You need to write a program, named Sudoku (written, of course, in a file named Sudoku.java), that can be run like this:

(remus)~/project-4> java Sudoku medium.board 
Initial board:
0 0 0 0 0 0 0 0 7 
0 0 0 0 7 0 3 0 8 
0 0 0 5 0 4 0 6 0 
0 0 0 0 0 0 0 8 0 
7 1 0 0 9 0 0 0 5 
8 0 0 0 1 5 9 0 0 
3 0 0 0 0 0 0 0 0 
0 0 8 9 4 0 6 3 0 
0 2 7 6 0 3 0 0 0 
Final board:
6 8 1 2 3 9 5 4 7 
2 4 5 1 7 6 3 9 8 
9 7 3 5 8 4 2 6 1 
5 9 4 7 6 2 1 8 3 
7 1 6 3 9 8 4 2 5 
8 3 2 4 1 5 9 7 6 
3 6 9 8 2 1 7 5 4 
1 5 8 9 4 7 6 3 2 
4 2 7 6 5 3 8 1 9 
Correct solution!
    

That is, the file medium.board contains a Sudoku puzzle (with 0 values where there would normally be blank entries). Go ahead, open it in Emacs and look. Your Sudoku program must read that board into a two-dimensional array of int. It must then solve the puzzle. That's all there is to it!

Using the Support methods

There are two methods in the Support class that you must use in your program:

• public static void printAndVerifyInitialBoard (int[][] board, String initialStatePath)

  When your program has read the initial state of the board from its file into a two-dimensional array of int, it must call this method, passing both the 2D array and the file name from which it was created. This method will print the initial board; it will also check the 2D array against the file, verifying that the array is correct.

• public static void printResults (boolean isSolved, int[][] board)

  After your program has (tried) to solve the puzzle, it must call this method. The first parameter, isSolved, should indicate whether your solver believed that it solved the puzzle. The second parameter, board, should be the 2D array containing the solved puzzle. This method will print the 2D array that is passed. Moreover, if isSolved is true, then this method will verify that the puzzle is indeed solved. If isSolved is false, this method will determine whether a solution should have been found.

Testing your code

There are three Sudoku board files:

• easy.board -- The easiest of the puzzles to solve. Start with this one.

• medium.board -- Fewer initial values are provided than in easy.board, making the search a bit harder.

• evil.board -- A minimal number of values are provided. This solution requires backtracking to work correctly. (That is, certain values will be placed, but their incorrectness will not be evident until much later in the search.)

So long as you call the Support methods at the right times, you should be able simply to use these three provided puzzles to test and debug your code. Feel free, also, to find other puzzles and make your own Sudoku board files.

Submitting your work

From within your project-4 subdirectory, use the following command to submit you work (all of your Java code files) when you are done:

cs11-submit project-4 *.java