N-queens problem

From CodeCodex

Revision as of 00:06, 6 January 2007 by WikiSysop (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_board n queens =
  let a = Array.make_matrix n n '.' in
  iter (fun (x, y) -> a.(y).(x) Array.iter print_char row; print_newline()) a;
  print_newline ();;

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

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