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

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) ();
    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 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 tracer

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:


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.


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) - 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 =
    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.


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

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 [];

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

Sep 27

Minimal DirectX demo

Minimal DirectX demo

With the advent of .NET, Managed DirectX makes graphical programming easy under Windows. This program is a minimal DirectX demo with several interesting features:

  • Lighting
  • Perspective
  • Mouse control
  • Mesh rendering

Despite having all of these features, the entire program requires only 100 lines of source code to render a 3D teapot that can be rotated with the mouse:

This example program is freely available in two forms:

The program has several interesting aspects:


This is a Windows application that uses WinForms to create a window containing a DirectX device.

The WinForms-related code is written in an object oriented style, forming a Viewer class:

type Viewer = class
  inherit Form

This class encapsulates the creation and handling of a window containing a DirectX device. The constructor for this class accepts the title of the window as a string and a rendering function:

new(title, render) as form = {device=null; render=render; world=Matrix.Identity; drag=None} then
form.SetStyle(Enum.combine [ControlStyles.AllPaintingInWmPaint; ControlStyles.Opaque], true);

Note that the ability to pass the rendering function as an argument to the constructor is functional programming.

Mouse control

Dragging is achieved by storing a mutable value in the Viewer object:

val mutable drag : (Matrix * int * int) option

When the scene is not being dragged, drag is None. During dragging, drag is Some(m, x, y) where m is the original world transformation matrix and x, y is the window coordinate where the drag started.

Inside the Viewer class, the OnMouseDown event is used to set drag:

override form.OnMouseDown e = form.drag 

and the OnMouseUp event is used to reset drag:

override form.OnMouseUp e = form.drag 

The OnMouseMove event uses drag to update the world transformation matrix during a drag and then force redraw:

override form.OnMouseMove e = match form.drag with
  | Some(world, x, y) ->
      let scale = 5.f / float32(min form.device.Viewport.Width form.device.Viewport.Height) in  ()

This is a very succinct way to handle the mouse control of a scene. Note the use of variant types (option) and pattern matching.


The OnPaint event of the window calls boiler-plate DirectX functions and uses the render function that the object was instantiated with to perform the actual rendering:

override form.OnPaint _ =
  if form.device = null then form.make_device();
    form.device.Clear(Enum.combine [ClearFlags.Target; ClearFlags.ZBuffer], Color.Black, 1.f, 0);
    form.device.Transform.World  form.make_device()

Note that this function is careful to replace the DirectX device if there is an error. This handles DirectX device loss and reset, although there are probably more elegant ways to do so. For example, if the render function threw one of our own exceptions, the device might not need replacing.

The render function, responsible for rendering the scene, is defined outside the Viewer class. The render function sets a light:


initialises the transformation matrices (representing perspective projection and the camera position and orientation relative to the scene):

let aspect = float32 device.Viewport.Width / float32 device.Viewport.Height in

sets materials propertes ready to render a red teapot with a white specular highlight:

let mutable material = new Material() in

and finally renders the built-in teapot mesh:

Idioms.using (Mesh.Teapot(device)) (fun teapot -> teapot.DrawSubset(0))

Note the use of Idioms.using to ensure that the teapot mesh is deallocated immediately. If the mesh is create and then left for garbage collection every frame, many meshes accumulate and stall the program when the garbage collector kicks in. In this case, a better practice is to store the mesh along with the device and invalidate it when the device is reset.

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