N-queens problem

From CodeCodex

Revision as of 21:33, 13 January 2007 by Jdh30 (Talk | contribs)


Find all ways to position n queens on an n by n chessboard such that no queen attacks any other, print the boards and the number of solutions found for n=8.

Note that the programs must print the boards (there are algorithms that count the number of solutions without actually finding them) and must work for general n.



This implementation starts with a list of all board positions and recursively searches, filtering out unsafe board positions:

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 = 8;;

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

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 n -> print n qs; n + 1) n [] ps 0;;

Printf.printf "%d solutions.\n" sols;;