Sep 27

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