|OCaml tutorials and examples|
Update: Our Sudoku implementation has now been replaced with a shorter, faster and simpler implementation!
The Japanese puzzle game Sudoku is all the rage at the moment. This web page describes a 19-line (769-byte) OCaml program that solves Sudoku puzzles.
The board is represented by an array of strings, held in a global variable
let m = Array.init 9 (fun _ -> input_line stdin)
In functional programming languages, loops over data structures can be conveniently factored out into higher-order functions, such as the built-in
let print() = Array.iter print_endline m
The test for validity is performed by looping (using recursion) over
let rec invalid ?(i=0) x y n = i<9 && (m.(y).[i] = n || m.(i).[x] = n || m.(y/3*3 + i/3).[x/3*3 + i mod 3] = n || invalid ~i:(i+1) x y n)
Loops over a semi-inclusive range of consecutive integers [
let rec fold f accu l u = if l=u then accu else fold f (f accu l) (l+1) u
let rec search ?(x=0) ?(y=0) f accu = match x, y with 9, y -> search ~x:0 ~y:(y+1) f accu (* Next row *) | 0, 9 -> f accu (* Found a solution *) | x, y -> if m.(y).[x] <> '0' then search ~x:(x+1) ~y f accu else fold (fun accu n -> let n = Char.chr (n + 48) in if invalid x y n then accu else (m.(y).[x] <- n; let accu = search ~x:(x+1) ~y f accu in m.(y).[x] <- '0'; accu)) accu 1 10
Note that this
The main part of the program uses the
let () = Printf.printf "%d solutions\n" (search (fun i -> print(); i+1) 0)
This program can be compiled using:
$ ocamlopt sudoku.ml -o sudoku
The program can be executed and fed a Sudoku puzzle to be solved:
$ cat >puzzle 001005300 050490000 000102064 000000750 600000001 035000000 460903000 000024090 003600100 $ ./sudoku <puzzle 241865379 356497218 879132564 194386752 682579431 735241986 467913825 518724693 923658147
This is a very simple Sudoku solver. Nevertheless, this program can solve most puzzles in under one second. The performance of this program can be improved in many different ways but we shall now defer to other authors for faster and more complicated implementations.
|© Flying Frog Consultancy Ltd., 2007||Contact the webmaster|