[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
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
More information about the Haskell-Cafe
mailing list