CIT 591 Assignment 4: Sudoku
Fall 2011, 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. In other words, every row contains all nine digits, every column contains all nine digits, and every box contains all nine digits. Your assignment is to write a program to try to solve Sudoku puzzles. You won't be able to solve them all. This image is from http://www.sudoku.com/, which used to have additional explanations and puzzles, but I don't see them now. (Maybe I haven't looked hard enough.) The site seems to be much more commercial than it used to be. 

Your job is to write a program to try to solve Sudoku puzzles. If you write the program correctly, it should be able to solve easy puzzles. (If you are good at Sudoku, this program can be expanded to solve harder puzzles; but that's not part of the assignment!)
Think of each of the 81 locations in the puzzle as containing a set of possible numbers. If the number for a particular location is given (for example, row 0 column 1 in the above Sudoku is 6), you can represent that as {6}
, the "singleton" set containing only the number 6. If a location in the puzzle is blank, then any number might go there, and you can represent that as the set {1, 2, 3, 4, 5, 6, 7, 8, 9}
. As you begin to solve the puzzle, you remove elements from these sets of possible numbers.
For example, 6 occurs in row 0, so it can't occur anyplace else in row 0. You can remove the 6 from every other set in row 0 that contains a 6: locations (0, 0), (0, 2), (0, 4), (0, 6), and (0, 8). The 6 is in column 1, so you can remove the 6 from every other row in that column: locations (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1) and (7, 1). The 6 is in the top lefthand "box" (rows 0 to 2 and columns 0 to 2), so you can remove the 6 from every other location in that box: locations (0, 0), (0, 2), (1, 0), (1, 1), (2, 1), and (2, 2).
A Sudoku puzzle is "solved" if every location in the array contains a singleton set (a set containing only one element).
A set is like a list, with these differences:
{}
, rather than brackets, []
. in
the set or not in
the set; it can't be in twice or more.Here are some of the things you can do with a set:
x = {1, 2, 3, 4, 5, 6, 7, 8, 9}
.
set([])
or set({})
.list({1, 2, 3})
⇒ [1, 2, 3]
set(['a', 'b', 'c'])
⇒ {'a', 'c', 'b'}
in
or not in
a set: 3 not in {1, 2, 3, 4}
⇒ False
x = {1, 2}; x.add(3); print(x)
⇒ {1, 2, 3}
x = {1, 2, 3}; x.remove(2); print(x)
⇒ {1, 3}
union
of two sets: x = {1, 2}; y = {'a'}; z = x.union(y); print(z)
⇒ {'a', 1, 2}
union
, you can take the intersection
, difference
, or symmetric_difference
of two sets.issubset
or issuperset
of another: {1,2,3}.issuperset({1, 3})
⇒ True
==
, or unequal, !=
: {1, 2, 3} == {3, 1, 2}
⇒ True
x = {1, 2}; y = x.copy(); print(x == y, x is y)
⇒ True False
len({'a', 'b'})
⇒ 2
Your program should have exactly the following functions. You may have additional functions if you wish; all functions, except those that do I/O, must be unit tested.
def read_sudoku(file_name)

problem
, then problem[8]
is the list [9, 3, 0, 0, 0, 0, 7, 1, 0]
, while problem[8][0]
contains the integer 9
. You can find the number of rows in a twodimensional array problem
with len(problem)
, and you can find the number of columns with len(problem[0])
. For this assignment, represent a location in an array with a
(row, column)
def read_sudoku(file): stream = open(file) data = stream.readlines() stream.close() return eval("".join(data))
The read_sudoku
function is an input function, and so is exempt from unit testing. Most of the following functions should not do any input/output, and you must have unit tests for each. Please write the unit tests first! Please encourage your partner to write unit tests first! A lot of students in here are resistant to change, but you are supposed to be in here to learn new things. You won't be learning very much if you won't even try any new approach.
def convertToSets(problem)
problem
of integers, create and return a new twodimensional array of sets. For each location in problem
that contains an integer 1 to 9, create a set containing just that one integer. For each location in problem
that contains a zero, create a set containing the numbers 1 through 9. This function should work for any twodimensional array, not just a 9x9 array (this will make writing unit tests easier).def convertToInts(problem)
problem
of sets, create and return a new twodimensional array of integers. For each location in problem
that contains a singleton set (a set with only one element), the corresponding integer array location should contain that one element. For each location in problem
that contains a set with more than one element, the corresponding location in the result array should contain zero. This function should work for any twodimensional array, not just a 9x9 array (this will make writing unit tests easier). For completeness, if any location in problem
contains an empty set (this should never happen), put a 0
in the result array.def getRowLocations(rowNumber)
rowNumber
, return a list of all nine "locations"
(row, column)
def getColumnLocations(columnNumber)
columnNumber
, return a list of all nine "locations" (row, column)
def getBoxLocations(location)
(row, column)
location
.def eliminate(problem, location, listOfLocations)
location
in the array problem
should contain a set containing a single number. For each location in the listOfLocations
except location
, remove the number in location
from the set in each other location. This function changes the array problem
and returns a count of the number of eliminations (removals) actually made.This function should work for any twodimensional array, not just a 9x9 array (this will make writing unit tests easier).def isSolved(problem)
problem
of sets, return True
if the Sudoku problem has been solved (every set contains exactly one element), and False
otherwise.def solve(problem)
problem
of sets, try to solve it. This function changes the array problem
and returns True
if the problem has been solved, False
otherwise.eliminate
with row, column, and box locations. If any values have been eliminated (eliminate
returns something other than zero), repeat this procedure. When it is no longer possible to eliminate anything, return the boolean result.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 . 
++++
def main()
Use exactly the function names and parameters as givenif you don't, our tests will fail, and your functions will be considered incorrect. You can create additional functions, but you must also have the given ones as specified. Any additional functions should also have unit tests.
I have been asked if it is okay to write some functions to have default parameters (which I haven't yet talked about in class). Yes, so long as I can call and test each function with the required parameters as described above. My tests won't even know about your default parametersbut if you do this, your tests should test the functions both with and without the extra parameters.
The DRY principle in programming is: Don't Repeat Yourself. If one function can make use of another function in order to avoid duplicating code, it should do so.
One of the advantages of TDD (Test Driven Development) is that it leads you to write simpler functions. That doesn't apply here, because I've already told you exactly which functions to write. So you won't see that advantage, but trust me, it's real. In fact, probably the only advantage you will get is that you will get the program written and debugged fasterand you can always tell yourself that you would have gotten it done even faster if you didn't have to test everything. (In fact, if you get the program to work first and then write the tests, you would be right, because you gain nothing from the tests.)
I specified that some of the functions do not assume a 9x9 array. This doesn't make them any harder, and it lets you can test them with a smaller array, if you like (I probably will.)
Friday, October 7, before 6am. Create two files, named sudoku.py
and sudoku_test.py
, zip them together, and submit via Sakai. As this is a pair programming assignment, only one of you should submit the assignment, with both your names prominently displayed, as described above. As always, only assignments submitted via Sakai
will be accepteddo not send your program by
email. A late penalty of 5 points per day (out of 100 points) will apply.