# [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
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
```