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

Jon Harrop jon at ffconsultancy.com
Mon Aug 27 05:24:47 EDT 2007

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

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