Difference between revisions of "N-queens problem"

From CodeCodex

m
(OCaml)
Line 25: Line 25:
 
let ps = flatten (init n (fun i -> init n (fun j -> i, j)));;
 
let ps = flatten (init n (fun i -> init n (fun j -> i, j)));;
  
let print_board n queens =
+
let print qs =
   let a = Array.make_matrix n n '.' in
+
   let a = Array.init n (fun _ -> String.make n '.') in
   iter (fun (x, y) -> a.(y).(x) Array.iter print_char row; print_newline()) a;
+
   List.iter (fun (x, y) -> a.(y).[x] <- 'Q') qs;
  print_newline ();;
+
  Array.iter print_endline a;;
  
 
let sols = search (fun qs n -> print_board n qs; n + 1) n [] ps 0;;
 
let sols = search (fun qs n -> print_board n qs; n + 1) n [] ps 0;;

Revision as of 21:18, 13 January 2007

Description

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.

Implementations

OCaml

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

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