[Haskell-cafe] Norvig's Sudoku Solver in Haskell

[Jon Harrop]

On Monday 27 August 2007 09:09:17 manu wrote:
> Daniel Fischer's modifications to my original program lead to a 400 %
> speed boost !!!
> (It now runs in 22 seconds on my machine)
> He avoided unecessary calls to 'length', uses Array instead of Map,
> refactored 'search' function (details below)
>
> I've put up his version on hpaste : http://hpaste.org/2452#a1

You shouldn't have any problem writing a purely functional solver that is 
faster and much shorter than Norvig's Python without having to use arrays.

The following purely functional OCaml solver is faster than Norvig's, for 
example, and uses lists, tuples and maps:

open List

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

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

let cmp (_, l1) (_, l2) = compare (length l1) (length l2)

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

module Map = Map.Make(struct
			type t = int * int
			let compare = compare
		      end)

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