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