# 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

### Erlang

```-export([queen/1]).

queen(N) ->
IJ = [{I, J} || I <- lists:seq(1, N), J <- lists:seq(1, N)],
lists:foreach(fun({I, J}) -> put_data(I, J, true) end, IJ),
solve(N, 1, [], 0).

solve(N, J, Board, Count) when N < J ->
print(N, Board),
Count + 1;
solve(N, J, Board, Count) ->
F = fun(I, Cnt) ->
case get_data(I, J) of
true  ->
put_data(I, J, false),
Cnt2 = solve(N, J+1, [I|Board], Cnt),
put_data(I, J, true),
Cnt2;
false -> Cnt
end
end,
lists:foldl(F, Count, lists:seq(1, N)).

put_data(I, J, Bool) ->
put({row, I  }, Bool),
put({add, I+J}, Bool),
put({sub, I-J}, Bool).

get_data(I, J) ->
get({row, I}) andalso get({add, I+J}) andalso get({sub, I-J}).

print(N, Board) ->
Frame = "+-" ++ string:copies("--", N) ++ "+",
io:format("~s~n", [Frame]),
lists:foreach(fun(I) -> print_line(N, I) end, Board),
io:format("~s~n", [Frame]).

print_line(N, I) ->
F = fun(X, S) when X == I -> "Q " ++ S;
(_, S)             -> ". " ++ S
end,
Line = lists:foldl(F, "", lists:seq(1, N)),
io:format("| ~s|~n", [Line]).
```

### F#

Much like the OCaml but uses list comprehensions and avoids string mutation:

```let n = 8;;

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 nqs qs ps accu = match ps with
| [] -> if nqs = n then f qs accu else accu
| q::ps -> search f n (nqs+1) (q::qs) (filter (safe q) ps) (search f n nqs qs ps accu)

let ps = [for i in 1 .. n for j in 1 .. n -> 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 0 [] ps 0;;

do Printf.printf "%d solutions for n=%d.\n" sols n;;
```

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

### Ruby

```class Queen
def initialize(num = 8)
@size  = num
@board = Array.new(num)
@row   = Array.new(num)
@add   = Array.new(2 * num - 1)
@sub   = Array.new(2 * num - 1)
@line  = "+-" + "--" * num + "+"
@count = 0
end

def print_out
puts @line
@board.each do |i|
print "| "
@size.times {|j| print j==i ? "Q " : ". "}
puts "|"
end
puts @line
end

def solve(y = 0)
if y == @size
print_out
@count += 1
else
@size.times do |x|
unless @row[x] || @add[x+y] || @sub[x-y]
@row[x] = @add[x+y] = @sub[x-y] = true
@board[y] = x
solve(y + 1)
@row[x] = @add[x+y] = @sub[x-y] = nil
end
end
end
@count
end
end

pzl = Queen.new(8)
puts pzl.solve
```