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:
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 arraywith empty puzzle entries represented by
searchfunction 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
solvefunction: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.
The GUI is implemented by classes derived from
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