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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe