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)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 NoneWhenever 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 raise Exit) (); clear() with Exit -> Idioms.lock solution (fun () -> Array.iteri (fun y row -> Array.iteri (fun x n -> solution.(y).(x).TextThis 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