[Haskell-cafe] Sudoku Solver

Jon Harrop jon at ffconsultancy.com
Sat Aug 18 19:11:41 EDT 2007

On Saturday 18 August 2007 19:05:04 Wouter Swierstra wrote:
> I hacked up a parallel version of Richard Bird's function pearl solver:
> http://www.haskell.org/sitewiki/images/1/12/SudokuWss.hs
> It not really optimized, but there are a few neat tricks there.
> Rather than prune the search space by rows, boxes, and columns
> sequentially, it represents the sudoku grid by a [[TVar [Int]]],
> where every cell has a TVar [Int] corresponding to the list of
> possible integers that would 'fit' in that cell. When the search
> space is pruned, we can fork off separate threads to prune by
> columns, rows, and boxes -- the joy of STM!

Is it possible to write a shorter Haskell version, perhaps along the lines of 
this OCaml:

let invalid (i, j) (i', j') = i=i' || j=j' || i/n=i'/n && j/n=j'/n

let select p n p' ns = if invalid p p' then filter ((<>) n) ns else ns

let cmp (_, a) (_, b) = compare (length a) (length b)

let add p n sols = sort cmp (map (fun (p', ns) -> p', select p n p' ns) sols)

let rec search f sol = function
  | [] -> f sol
  | (p, ns)::sols ->
      iter (fun n -> search f (Map.add p n sol) (add p n sols)) ns

Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists

More information about the Haskell-Cafe mailing list