Due: | 2006-02-06 |
---|---|

Project TA: | Hayden So <cs61c-th at imail dot eecs dot berkeley dot edu> |

Sudoku is a logic puzzle that has gained massive attraction around the globe in the past year or so: You can find daily sudoku puzzle on many major newspapers; You see books describing sudoku solving techniques ranked among top-sellers in major bookstores; You see them online everywhere. BBC news compared this sudoku craze with the Rubik's cube craze in the 80's. Sudoku is a simple, yet addictive, logic puzzle. There are plenty of information on the internet about sudoku, including daily puzzle, solver, and even mathematical analysis of the puzzle. A few great sites that offers sudoku information are wikipedia and Sudoku.com . A typical sudoku puzzle is shown below:

Each sudoku puzzle consists of a 3-by-3 grid of *boxes*. Each *box*
itself is a 3-by-3 grid of *cells*. Therefore, there is a total of 81
cells. Some of them are filled, called *givens*, when the puzzle is
given to you. The rule to solve a sudoku puzzle is simple: Fill in
all the cells with a number from 1 to 9, such that no number appears
more than once in a row, a column, or a box. For example, the
solution to the above sample is as follows:

In this project, you will write a sudoku solver in C. Your solver
should also be able to solve puzzles not in the original sudoku 3-by-3
configuration. In general, your solver is required to solve puzzle of
n-by-n grid of n-by-n boxes, where *n* is larger than or equal to 3.

Your code will be compiled into an executable named `sudoku`. It
will be passed a filename on the command line which contains the
initial puzzle (see Input File Format below). If the special
filename `-` is given, you should read the file from `stdin`
rather than opening a file to read. Otherwise you should print a
**very descriptive** usage string.

Example invocation with a filename:

nova% ./sudoku simple.puzzle ;; Output as specified below

Example invocation with the argument `-`:

nova% cat simple.puzzle | ./sudoku - ;; Output as specified below

Example invocation with no arguments:

nova% ./sudoku ;; Your VERY DESCRIPTIVE usage string would print here

All your program output should be printed to `stdout`. Your program
should display the solved puzzle in the same format as
your input, except all "0" (blank cells) are replaced with the correct
number. Also, there is no need to display the first line of the input
file that specifies `n`. If the puzzle has no solution, it should
print a string **No solution** to `stdout`. You might be passed an
input file that is not in the described format. In that case, your program
should print a message **Parse error**.

Some sudoku puzzles can be solved in a non-unique way. You are *not*
required to find all solutions to a given puzzle. Any valid solution
is acceptable for this project.

The file format for the sudoku puzzle is as follows:

The first line contains a positive integer that reprsents *n*, the
width of a sudoku box. For example, a sudoku puzzle in the original
form has *n* = 3. An integer *n* represents a puzzle with
a n-by-n grid of n-by-n cells. In other words, there are *n* ^4 cells
in the puzzle.

Starting with the second line is the actual sudoku puzzle. Each cell is represented by a positive integer, followed by one or more space characters. An empty cell is represented by a "0", while a cell with "given" are represented by the given number.

Each line in the input file represents a row of cells. Therefore,
there are *n* * *n* integers on each row, and there are *n* * *n* + 1
lines in the input file.

Below is an example input puzzle that represents the above sample sudoku puzzle:

3 0 1 4 5 2 0 0 0 9 3 0 0 0 9 0 4 5 1 5 0 8 0 0 0 0 6 7 0 0 0 0 0 3 7 0 0 0 0 6 2 0 5 1 0 0 0 0 3 4 0 0 0 0 0 4 3 0 0 0 0 6 0 2 8 2 7 0 4 0 0 0 5 1 0 0 0 5 2 8 4 0

Your program should return 0 upon successful solving of the given puzzle. If the given puzzle has no solution, your program should return 1. If the given puzzle file is not formatted correctly or the command line arguments are incorrect, such as a missing input file name, your program should return 2.

The following directory contains some simple test cases.

http://inst.eecs.berkeley.edu/~cs61c/projs/01/examples

or on an inst machine:

ls ~cs61c/projs/01/examples

There is an executable file called `sudoku_ta` in the directory
`~cs61c/projs/01/bin`, which acts as an oracle to show you the
expected result of your program. We recommend you to run the
executable directly from the above mentioned location, as we might make
minor bug fixes to this executable in the coming weeks.

Your project will be graded by it's correctness. We will be using your program to solve a set of undisclosed input puzzles with different sizes and difficulties. Your program is expected to generate the expected result according to the above mentioned specification. Although speed is not a main grading criteria, we do regard a program as failing to solve a puzzle if it does not return in a reasonable amount of time.

Create a directory named `proj1` containing all the source code for
your project, a `Makefile` to build the code, and a `README` file.
In the `README`, please discuss design decisions you have made. Explain
your choice of data structures, and if you like, *briefly* comment on
any problems you encountered and how you overcame them.

A sample `Makefile` as well as a skeletal `sudoku.c` is available at:

http://inst.eecs.berkeley.edu/~cs61c/projs/01/

Once all your files are ready, issue the following command within the directory `proj1`:

nova% submit proj1

If you have already submitted via bSpace before 2/6/06, and you have
no intention to resubmit your project, you can do nothing. However,
if you decide to resubmit your project, please use the new `submit`
method.