OCaml tutorials and examples 
Sudoku SolverUpdate: 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 19line (769byte) 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 higherorder functions, such as the builtin 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 semiinclusive 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 The 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. Further reading

© Flying Frog Consultancy Ltd., 2007  Contact the webmaster 