# 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.

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

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`