Introduction to Computer Science I

Project 4


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:

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:

Testing your code

There are three Sudoku board files:

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

This assignment is due Friday, 2008-May-09, at 5:00 pm

Scott F. H. Kaplan
Last modified: Fri Apr 25 11:45:18 EDT 2008