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