Homework Assignment 9

Sudoku

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

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).

- To gain experience working with multiple classes.
- To gain experience with recursive programming
- To gain experience in the game programming

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

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!

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

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.

Download the lab.zip that contains the following template:

- lab.html
- Grid.java
- Sudoku.java
- Solver.java
- Cell.java
- easy.txt
- medium.txt
- hard.txt
- evil.txt

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