CIT 590 Assignment 3: Sudoku
Spring 2010, David Matuszek
In Sudoku, you are given a 9x9 grid, divided into nine 3x3 "boxes," as shown on the right. Each box has nine "cells," and some of these cells have digits in them (but most are blank). The puzzle is to fill in the rest of the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. Your assignment is to write a program to solve easy Sudoku puzzles. This image is from http://www.sudoku.com/, which is a very nice site with additional explanations and puzzles (and a Sudoku program for sale). 

Your job is to write a program to solve "easy" Sudoku puzzles. A problem is "easy" if, at all times, there is at least one location in the grid that has all but one of the nine digits occurring in the same row, column, or box.
For example, in the above puzzle, look at the bottom righthand corner of the middle box in the top row of boxes (that is, row 2, column 5remember to start counting with zero). The digits 2 and 1 occur in the same row; the digits 1, 3, 4, and 5 occur in the same box; and the digits 4, 5, 7, 1, 6, and 8 occur in the same column. The only missing digit is 9, which must perforce go into this location.
Use the number 0 to represent a "blank" location.
Your program should have exactly the following methods. You may have additional methods if you wish; all methods, except those that do I/O, must be unit tested.
def main()
def read_sudoku(file_name)
[ [ 0, 0, 4, 0, 0, 0, 0, 6, 7 ],
[ 3, 0, 0, 4, 7, 0, 0, 0, 5 ],
[ 1, 5, 0, 8, 2, 0, 0, 0, 3 ],
[ 0, 0, 6, 0, 0, 0, 0, 3, 1 ],
[ 8, 0, 2, 1, 0, 5, 6, 0, 4 ],
[ 4, 1, 0, 0, 0, 0, 9, 0, 0 ],
[ 7, 0, 0, 0, 8, 0, 0, 4, 6 ],
[ 6, 0, 0, 0, 1, 2, 0, 0, 0 ],
[ 9, 3, 0, 0, 0, 0, 7, 1, 0 ] ]
In Python we don't have "true" twodimensional arrays (lists); this is actually a list of nine lists of integers. So, for example, problem[8]
is the list [9, 3, 0, 0, 0, 0, 7, 1, 0]
, while problem[8][0]
contains the integer 9
. def print_sudoku(problem)
++++
 . . 4  . . .  . 6 7 
 3 . .  4 7 .  . . 5 
 1 5 .  8 2 .  . . 3 
++++
 . . 6  . . .  . 3 1 
 8 . 2  1 . 5  6 . 4 
 4 1 .  . . .  9 . . 
++++
 7 . .  . 8 .  . 4 6 
 6 . .  . 1 2  . . . 
 9 3 .  . . .  7 1 . 
++++
The above methods do input/output, and do not need to be unit tested. The following methods should not do any input/output, and you must have unit tests for each.
def solve(problem)
def occursInRow(digit, row, problem)
digit
(which must
be 1..9) occurs in the given row
(rows are 0..8),
and false otherwise.def occursInColumn(digit, column, problem)
True
if the given digit
(which
must be 1..9) occurs in the given column
(columns
are 0..8), and False
otherwise.
def occursInBox(digit, row, column, problem)
True
if the given digit
(which
must be 1..9) occurs in the box containing the location at the given row
and column
of
the 9x9 array, and False
otherwise. Note that
this method is given a row and column in the complete 9x9 array, but
must search for the given digit in the 3x3 box containing that
(row
, column
) location.def isPossibleDigit(digit, row, column, problem)
True
if the given digit
(which
must be 1..9) does not occur in the given row
,
or in the given column
, or in the box containing
this row
and column
, and False
otherwise.
That is, this digit is a possible candidate for putting in this location;
there may be other candidates.def isOnlyPossibleDigit(digit, row, column, problem)
True
if the given digit
can
be put in the given row
and column
,
and no other digit can be put there; returns False
otherwise.def getOnlyPossibleDigit(row, column, problem)
row
, column
)
location, return that digit, else return zero.Use exactly the function names and parameters as givenif you don't, our tests will fail, and your methods will be considered incorrect. You can create additional methods, but you must also have the given ones as specified. Any additional methods should also have unit tests.
The DRY principle in programming is: Don't Repeat Yourself. If one method can make use of another method in order to avoid duplicating code, it should do so.
Thursday, February 4, before midnight. Create two files, named sudoku.py
and sudoku_test.py
, zip them together, and submit via Blackboard.
(See my Instructions for Using
Zip Files and Blackboard). Only assignments submitted via Blackboard
will be accepteddo not send your program by
email. A late penalty of 5 points per day (out of 100 points) will apply.