CIS 554 Clojure Assignment 2: Sudoku
Fall 2013, David Matuszek

Purposes of this assignment

General idea

Write a program to solve easy Sudoku puzzles. A puzzle will be considered "easy" if it can be solved using the algorithm described below.

Here is an example of an easy Sudoku puzzle from yesterday's paper. (I worked this one very carefully to make sure it could be solved by the given algorithm.

puzzle

Details

The following two functions are required:

(solve matrix) accepts a Sudoku puzzle given as a vector of vectors, with each sub-vector representing one row of the puzzle. The elements of the sub-vector are the integers shown in the puzzle, but with 0 representing a blank space. Thus, the above puzzle would be represented as
[[0 2 5 0 0 1 0 0 0] ... [0 0 0 6 0 0 5 9 0]]. The value returned by solve will be a similar Vector of Vectors, but with all the zeros replaced by the appropriate numbers 1..9. (Any unsolved locations--there shouldn't be any--will be a set of the digits that might be there.)

(transform matrix) takes a Sudoku puzzle in the above vector of vectors format, and replaces each integer with a set of integers, thus returning a vector of sets of integers. Zeros in the matrix are replaced by the set #{1 2 3 4 5 6 7 8 9}, and each nonzero number is replaced by a set containing only that number. (You can think of these as the set of "possible" numbers for this location.)

You will probably find it most convenient to work with the vector of sets implementation, and in any case you are required to write the above two functions. If you prefer to work with some other implementation, you are free to transform the matrix internally to whatever form you choose.

The algorithm

Unit testing

Write, in a separate file, unit tests for all your methods. We will also use our own unit tests for the two required methods.

Due date:

Zip and turn in two files named sudoku.clj and sudoku-test.clj files by 6am, Wednesday October 2. As always, only files submitted to Canvas will be accepted. I do not accept assignments submitted by email.

Late penalties: There will be a 10 point penalty (out of 100 points) for programs between one minute and one week late, and a 25 point penalty for programs later than one week. At some unspecified time after one week we will stop accepting assignments.