1 (* Jon Harrop's Sudoku Solver in 19 lines of code, from:
2 * http://www.ffconsultancy.com/ocaml/sudoku/index.html
5 let m = Array.init 9 (fun _ -> input_line stdin)
7 let print() = Array.iter print_endline m
9 let rec invalid ?(i=0) x y n =
10 i<9 && (m.(y).[i] = n || m.(i).[x] = n ||
11 m.(y/3*3 + i/3).[x/3*3 + i mod 3] = n || invalid ~i:(i+1) x y n)
14 let rec fold f accu l u = if l=u then accu else fold f (f accu l) (l+1) u
16 let rec search ?(x=0) ?(y=0) f accu = match x, y with
17 9, y -> search ~x:0 ~y:(y+1) f accu (* Next row *)
18 | 0, 9 -> f accu (* Found a solution *)
20 if m.(y).[x] <> '0' then search ~x:(x+1) ~y f accu else
22 let n = Char.chr (n + 48) in
23 if invalid x y n then accu else
25 let accu = search ~x:(x+1) ~y f accu in
29 let () = Printf.printf "%d solutions\n" (search (fun i -> print(); i+1) 0)