CIS 554 Clojure Assignment 2: Sudoku

Fall 2013, David Matuszek

- Give you experience writing a "real" program in Clojure

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.

The following two functions are required:

`(solve `

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*matrix*)

`[[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 `

takes a Sudoku puzzle in the above vector of vectors format, and replaces each integer with a *matrix*) **set** of integers, thus returning a vector of sets of integers. Zeros in the matrix are replaced by the set

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

- Repeatedly do the following:
- Find a location containing a singleton set (a set containing just one number).
- For every other set in the same row, the same column, or the same 3x3 box, remove that number (if present).

- Find a number in a set that does not occur in any other set in the same row (or column, or box).
- Reduce that set to a singleton containing that one number.

- Find a location containing a singleton set (a set containing just one number).
- Quit when every set is a singleton, or when no more numbers can be removed from any set.

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

* Zip* and turn in two files named

` sudoku.clj `

and` sudoku-test.clj `

files by **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.