# Difference between revisions of "N-queens problem"

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