Sudoku Solver

The Japanese puzzle game Sudoku is all the rage at the moment. This web page describes a program written in Microsoft's F# programming language that solves Sudoku puzzles:

The entire program, including the solver, GUI and comments, fits in under 165 lines. The program has three main aspects:

Sudoku-solving function

The search function takes the simplest possible approach to solving Sudoku puzzles:

let rec search m x y f accu = match x, y with
  | x, y when x = size2 -> search m 0 (y + 1) f accu
  | 0, y when y = size2 -> f accu
  | x, y when m.(y).(x) <> 0 -> search m (x + 1) y f accu
  | x, y ->
      let aux accu n =
        if invalid m 0 x y n then accu else begin
          m.(y).(x) <- n;
          let accu = search m (x + 1) y f accu in
          m.(y).(x) <- 0;
          accu
        end in
      fold aux accu 1 10

A puzzle is represented by an int array array with empty puzzle entries represented by 0. The search function considers each entry in turn and tries the numbers 1..9, backtracking if the entry is invalid or accumulating a solution if the puzzle has been filled.

Threaded solving

The user interface is simplified at the expense of CPU time by firing off a new solver thread whenever the input is altered.

The currently running thread, if any, is kept in solver:

let solver : Thread option ref = ref None

Whenever the input is altered, a new solver thread is started using the solve function:

let solve() =
  Idioms.lock solver (fun _ -> !solver |> Option.iter (fun s -> s.Abort()); clear());
  Array.iteri (fun y row -> Array.iteri (fun x n -> solution.(y).(x).Text <- "") row) puzzle;
  let aux _ =
    let m = Array.map Array.copy puzzle in
    try
      search m 0 0 (fun s -> raise Exit) ();
      clear()
    with Exit ->
      Idioms.lock solution (fun () ->
        Array.iteri (fun y row ->
          Array.iteri (fun x n -> solution.(y).(x).Text <- string_of_int n) row) m);
      clear() in
  let thread = new Thread(new ThreadStart(aux)) in
  thread.Start();
  solver := Some thread

This approach obviates the need for user intervention via an explicit "Solve" button.

GUI

The GUI is implemented by classes derived from Label, TextBox and Form. These classes simply lay themselves out and detect key presses.

Two windows are created, instantiations of the derived class Window:

let input = new Window((fun(form, x, y) -> form.Controls.Add(new PuzzleEntry(x, y))), "Sudoku Puzzle")
let output = new Window((fun(form, x, y) -> form.Controls.Add(solution.(y).(x))), "Sudoku Solution")

A solver thread is started to solve the example puzzle:

do solve()

Finally, the programs runs until quit:

do while not quit && input.Created && output.Created do Application.DoEvents() done