Saturday, 13 January 2007

Solving the n-queens problem

The n-queens problem is one of the pedagogical example problems solved by computer scientists. The problem is easy to describe: enumerate all of the ways to place n queens on an nxn chessboard such that no queen is attacking any other.

As a functional programming language with list literals and pattern matching, OCaml can be used to solve this problem quickly and simply. The following OCaml code solves the problem by generating a list of all possible board positions and then searches by considering a queen at each position and filtering out the attacked squares from the remaining list:

open List

let rec safe (x1, y1) (x2, y2) =
x1 <> x2 && y1 <> y2 && x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1;;

let rec search f n qs ps accu = match ps with
| [] -> if length qs = n then f qs accu else accu
| q::ps -> search f n (q::qs) (filter (safe q) ps) (search f n qs ps accu)

let n = try int_of_string Sys.argv.(1) with _ -> 8

let rec init n f = if n=0 then [] else f(n-1) :: init (n-1) f

let ps = flatten (init n (fun i -> init n (fun j -> i, j)))

let print qs =
let a = Array.init n (fun _ -> String.make n '.') in
List.iter (fun (x, y) -> a.(y).[x] <- 'Q') qs;
Array.iter print_endline a;;

let sols = search (fun qs -> print qs; (+) 1) n [] ps 0;;

Cheers,
Jon.