Sudoku Solver

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 m. The program begins by reading 9 lines of input to fill the board:

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 Array.iter function used by our print function:

let print() = Array.iter print_endline m

The test for validity is performed by looping (using recursion) over i=0..8 and testing the row, column and 3x3 square containing the given coordinate:

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 [l..u) are factored out into a higher-order fold function:

let rec fold f accu l u = if l=u then accu else fold f (f accu l) (l+1) u

The search function simply examines each position on the board in turn, trying the number 1..9 in each unfilled position:

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 search function is itself a higher-order fold, accumulating the value accu by applying the given function f to it whenever a solution m is found.

The main part of the program uses the search function to accumulate the total number of solutions:

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.

Sudoku Solver

Further reading