CS61C Project 1

Sudoku Solver

Due:2006-02-06
Project TA:Hayden So <cs61c-th at imail dot eecs dot berkeley dot edu>

Background

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:

Sample sudoku puzzle

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:

Sample sudoku puzzle solution

Your Task

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.

Execution

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.

Input File Format

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

Return value

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.

Examples

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.

Grading Criteria

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.

Submission Details (Updated 2/6/06)

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

Note

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.