Sep 27

Sudoku Solver

exampleNo Comments

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:

Windows executable (requires Microsoft .NET2)
Source code: sudoku.fs
Visual Studio 2005 project

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

Sep 27

Ray tracing is a simple way to create images of 3D scenes. The method casts rays from the camera into the 3D scene and determines which object the ray intersects first. This approach makes some problems easy to solve:

Shadows can be simulated by casting a ray from the intersection point towards the light to see if the intersection point has line-of-sight to the light.
Reflections can be simulated by casting a second ray off the surface in the reflected direction.

Read more about ray tracing in the current Wikipedia article

This ray tracer generates a scene composed of a floor with a procedural texture and a set of recursively nested spheres:

This example program is freely available in two forms:

The program has several interesting aspects:

Types

The main types used by the program are defined succinctly and elegantly in F# as records and variants:

type material = { color: vector; shininess: float }
type sphere = { center: vector; radius: float }
type obj = Sphere of sphere * material | Group of sphere * obj list
type ray = { origin: vector; direction: vector }

These types actually become .NET objects but the programmer is freed from having to define constructors, members and so on.

Intersection

The core of this ray tracer is a recursive intersection function that hierarchically decomposes the sphereflake into its constituent parts:

let rec intersect_spheres ray (lambda, _, _ as hit) = function
  | Sphere (sphere, material) ->
      let lambda' = ray_sphere ray sphere in
      if lambda' >= lambda then hit else
      let normal = unitise (ray.origin + (lambda' $* ray.direction) - sphere.center) in
      lambda', normal, material
  | Group (bound, scenes) ->
      let lambda' = ray_sphere ray bound in
      if lambda' >= lambda then hit else List.fold_left (intersect_spheres ray) hit scenes

This function leverages the benefits of functional programming in several ways:

Recursion is used to implement the core algorithm.
Pattern matching is used to decompose data structures and name their parts, e.g. lambda and hit.
Pattern matching is used to perform the equivalent of virtual function dispatch, e.g. handling Sphere or Group.
A higher-order function List.fold_left is used to apply the intersect_spheres function to the child spheres of a Group.

This design also leverages features seen in imperative languages:

Vector and matrix routines are provided by the standard library.
Operator overloading allows conventionally-named arithmetic operators to be applied to vectors and matrices.

Functional programming makes it easy to perform computations in parallel, on different CPUs.

Parallel processing

All of the rays used to trace the scene can be treated individually. This makes ray tracing ideally suited to parallel processing.

This ray tracer breaks the image down into horizontal runs of pixels called rasters. The set of rasters that make up the image are dispatched to a .NET threadpool which transparently farms out the work to any available CPUs.

As the image appears in a window that can be resized, it is important to quit computations early when their results will no longer be used because the image has been resized. This is achieved by having a list of completed rasters stored as a reference to a reference to a list:

let rasters = ref (ref [])

The first reference is used to replace the list of completed rasters with a new list and the second reference is used to prepend a new raster when it is completed.

A function raster computes a raster and pushes its result onto r but bails early if the current list of rasters rasters is no longer the one it is building:

let raster r w h y =
  try
    let data = Array.init w (fun x -> if !rasters != r then raise Exit; pixel w h x y) in
    Idioms.lock !rasters (fun () -> r := (h - 1 - y, data) :: !r)
  with Exit -> ()

This is an easy way to avoid wasted computation in the absence of an abort function for threads in a thread pool.

GUI

The object oriented parts of the F# language are mostly made redundant by the ability to do functional programming. However, interoperability with the rest of .NET is an important capability that is well suited to object oriented programming.

The GUI is created by deriving a class Form1 from the WinForms class Form:

type Form1 = class
  inherit Form
  ...
end

The Form1 class contains a bitmap for the current image and overrides the OnPaint and OnResize members.

The OnPaint member is made to copy all completed rasters into the form’s bitmap and then draw the bitmap into the window:

override form.OnPaint e =
  Idioms.lock !rasters (fun () ->
    let draw(y, data) = Array.iteri (fun x c -> try form.bitmap.SetPixel(x, y, c) with _ -> ()) data in
      List.iter draw (! !rasters);
      !rasters := []);
      let r = new Rectangle(0, 0, form.Width, form.Height) in
      e.Graphics.DrawImage(form.bitmap, form.ClientRectangle, r, GraphicsUnit.Pixel)

The OnResize member is made to replace the list of completed rasters with a new one (causing all outstanding threads to quit after their next pixel completes) and replaces the form’s bitmap with a new one before invalidating the form to force a redraw.

override form.OnResize e = rasters := ref []; form.bitmap

Despite the sophistication of this application, the entire program is tiny thanks to the expressiveness of the F# programming language

Sep 27