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