Difference between revisions of "N-queens problem"

From CodeCodex

Line 35: Line 35:
[[Category:Objective Caml]]

Revision as of 00:07, 6 January 2007


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