CIT 590 Assignment 3: Sudoku
Spring 2010, David Matuszek

Purposes of this assignment:

General idea of the assignment:

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

 
Roll your mouse on and off the grid.
You may have to wait for the page to load fully

Details:

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 right-hand corner of the middle box in the top row of boxes (that is, row 2, column 5--remember 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.

Methods

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()
Asks the user for the name of a file containing a Sudoku problem to solve, reads in the problem, prints it, solves it, and prints the solution. (This is a simple method; it should call other methods to read, solve, and print).
def read_sudoku(file_name)
Reads and returns in a Sudoku problem from a file. The file will contain a list of lists, such as the following:
[ [ 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" two-dimensional 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.

Since I haven't told you yet how to read from files, the code read_sudoku.py is provided for you.
def print_sudoku(problem)
Prints the Sudoku array in the following form, using dots to represent zeros. 
+-------+-------+-------+
| . . 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)
Solves this Sudoku problem, and returns the solution.
def occursInRow(digit, row, problem)
Returns true if the given digit (which must be 1..9) occurs in the given row (rows are 0..8), and false otherwise.
def occursInColumn(digit, column, problem)
Returns 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)
Returns 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)
Returns 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)
Returns 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)
If the rules of Sudoku allow only one particular digit to be placed in the given (row, column) location, return that digit, else return zero.

Use exactly the function names and parameters as given--if 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.

Due date:

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 accepted--do not send your program by email. A late penalty of 5 points per day (out of 100 points) will apply.