DM22, Spring 2007 - Weekly Note 8

Lecture March 19

More on the project. Haskell evaluation details.

Reading

Sections 7.1 and 7.5 in Bird.

Lecture March 26 (Expected Contents)

More Haskell evaluation details. Cyclic structures. The undefined value. Strict and non-strict functions. Proofs of properties of code.

Reading

Sections 7.5 and 9.4 in Bird. Chapters 1 and 2 in Bird again, now with a focus on the undefined value, and on proofs.

Exercises March 28

Exam of summer 2002 (pdf), exercise 3, question b.

[Hint: for the space reduction question, think accumulator and seq (or strict from the book, which in the Prelude appears as the (infix) operator $!, and which also can be defined by strict f x = seq x (f x)). Note: correctness of the "Russian peasant algorithm" follows from the fact that for odd m = 2m' + 1 we have nm = n(2m' + 1) = (n+n)m' + n, and similarly (but simpler) for even m = 2m'.]

The following set of exercises, the goal of which is to make a Sudoku solver in Haskell:

A Sudoku is a number puzzle where the objective is to complete a partially filled 9-by-9 table of numbers. Only the integers from 1 to 9 is to be used, and each number must appear exactly once in each row, in each column, and in each of the nine non-overlapping 3-by-3 sub-tables inside the main table. A Sudoku is supposed to have only one possible solution/completion.

An obvious representation of a Sudoku is by using a two-dimensional array. It was an exercise of the previous weekly note to create a Haskell module implementing a two-dimensional array efficiently (using balanced trees), and we here assume the availability of this. [If you did not complete this exercise, you may look at the Array package in the standard library instead (which you may want to do anyway, to benchmark the running time of your own implementation)].

Hence, we make the following type definition:

type Sudoku = Array2D Int

As input representation for Sudokus, we choose a list of 9 lists of 9 integers, giving the Sudokus in row-major mode, with empty entries represented by 0. Some examples appear in this file.

One idea for solving a Sudoku is to try to expand all positions of the partially filled 9-by-9 table one by one in all possible ways allowed by the rules (i.e. that each number must appear exactly once in each row, in each column, and in each of the 3-by-3 sub-tables). This is the idea followed here.

1. Make a function

   readSudoku :: [[Int]] -> Sudoku
   

   which converts the input representation to an array representation of a Sudoku.

2. Make a function

   printSudoku :: Sudoku -> String
   

   which converts an array representation of a Sudoku to something more readable (of your choice).

3. Make a function

   expandSudoku :: Sudoku -> (Int,Int) -> [Sudoku]
   

   which is the list of Sudokus obtained by expanding (i.e., inserting a number), in all possible ways allowed by the rules, the Sudoku given as first argument at the index given as second argument. If the given index is already filled, the list just contains the input Sudoku.

4. Make a function

   solveSudoku :: Sudoku -> [Sudoku]
   

   which is the list of all possible solutions of the given Sudoku. In particular, head (solveSudoku s) is one (normally, the only) solution of a Sudoku s.

Note: you will most likely want to define a number of auxiliary functions when creating the functions above.