15-200 Fall 2006

Homework Assignment 9

Sudoku

Program Due: Friday Dec. 08, 2006 at 11:59pm


Overview:

In this assignment you will write a program to solve Sudoku logical puzzles that currently taking the world by storm! A puzzle consists of a grid of size 9x9 divided into 9 subgrids of size 3x3. Some of the grid cells are filled with numbers from 1 to 9. You have to fill in the reamining cells in the grid with numbers from 1 to 9 so that each row, each column, and each 3x3 subgrid has all the different numbers. Visit the Sudoku web site for examples.

We've built a nice, pretty GUI for your Sudoku program. When you're finished, you will be able to play Sudoku games, load in different boards, time how fast your implementation is, and more. For this assignment, all you will be doing is implementing the backend of the application (the grid, the cells, and the solver).


Objectives:


Instructions:

Part I:

In this part, you will create a data-structure for storing the configuration of a Sudoku grid, together with methods for reading in the input file, adding numbers to the grid, printing out the grid, and checking whether the grid is legal.

The obvious data structure to use to represent a grid is a two-dimensional array of objects of a new class, that would allow to store several numbers in each cell of the grid. People usually put marks on Sudoku grid to record values they wish to remember as they go about solving the puzzle (How would you store this information?).

The grid is illegal if if there is a repeated value in any row, column or subgrid, or if there is an incorrect value (anything not 0tt-9 inclusive).

The Sudoku input file uses a simple format to express the boards. An example of the format is the following

     000 395 000
     005 008 902
     000 020 005
     602 000 007
     084 000 530
     700 000 106
     300 060 000
     506 200 700
     000 831 000
 
where zeros represent empty cells.

 

Part II:

In this part you are to solve the Sudoku puzzle, by filling all the blank cells of the grid. There are several methods to solve the puzzle. You will implement the depth-first search, also known as a backtracking. The main idea of this recursive approach is the following: It begins by storing all possible values for an empty cell (all cells with 0s). Then for each possible value of that cell, recursively go to the next empty cell, and repeat, all along, checking if the grid is valid. Once all squares are filled in, and the grid is valid, then we are finished!

Extra Credit:

Many of "easy' Sudoku problems can be solved without ever having to backtrack. This could be done by checking if only one candidate is left for a cell. For each constraint (row, column, and subgrid) and each number, see if that number is present in only one cell's canidate list. For example, for each row of numbers, check if only one cell in the row has a given number, say 8, in its candiate list. If so, select that number for that cell. Do similarly for each column, and each subgrid. To solve harder problems, a combination of heuristics and backtracking is the fastest way to go. For extra credit, write the fastest implementation you can. The fastest 10 implementations of the class will get the following points:
1st place: 20 pts
2nd: 18
3rd: 16
4th: 14
5th: 12
6th: 10
7th: 8
8th: 6
9th: 4
10th: 2


Notes:

For your testing purposes, we provide several puzzles from each of the "easy", "medium" "hard" and "evil" types. You should try to solve all the problems, starting with the easy ones.


What You'll Need:

Download the lab.zip that contains the following template:


Handing in your Solution:

ftp your solution to /afs/andrew/course/15/200/www/handin