# N-Queens

In the N-queen problem, $N$ queens must be placed on an $N\times N$ chessboard without interfering with each other. There can never be more than one queen on a chess row, column or diagonal because of the queen's ability to move vertically, horizontally and diagonally.

## Solution Representation

A naive representation is to use a binary matrix to represent a chessboard $c_{ij}$ where $c_{ij}=1$ would indicate a queen in row $i$ and column $j$; however the search space cardinality (number of solutions) is huge for this representation. A permutation-based representation can be used instead. A permutation will contain in position $j$ the row $i$ where a queen is, removing a lot of infeasible solutions (queens attacking horizontally and vertically).

Let's compute the number of solutions (a.k.a. cardinality):

julia> using Metaheuristicsjulia> N = 8 # for 8-queens8julia> cardinality(BitArraySpace(N*N))18446744073709551616julia> cardinality(PermutationSpace(N))40320

## Objective Function

It is necessary to minimize the number of attacks, the following objective function is proposed to this end:

function attacks(chessboard)
N = length(chessboard)
n_attacks = 0
# check attack in both diagonas for each queen
for i = 1:N
Δrows = i + chessboard[i]
Δcols = i - chessboard[i]
for j = (i+1):N
# check diagonal [\]
n_attacks +=  j + chessboard[j] == Δrows ? 1 : 0
# check inverse diagonal [/]
n_attacks +=  j - chessboard[j] == Δcols ? 1 : 0
end
end
2n_attacks
end
attacks (generic function with 1 method)

It can observed that horizontal and vertical are not considered due to the adopted solution representation.

## Let's find a solution

To minimize the number of attacks, let's use a Genetic Algorithm:

N = 8
result = optimize(attacks, PermutationSpace(N), GA)
Optimization Result
===================
Iteration:       20
Minimum:         0
Minimizer:       [5, 7, 1, …, 3]
Function calls:  2000
Total time:      0.0053 s
Stop reason:     Due to Convergence Termination criterion.


It can be observed that the number of attacks is:

n_attacks = minimum(result)
0.0

The optimal permutation is:

perm = minimizer(result)
8-element Vector{Int64}:
5
7
1
4
2
8
6
3

Corresponding chessboard configuration:

chessboard = zeros(Bool, N, N)
for (i,j) = enumerate(perm); chessboard[i,j] = true;end
chessboard
8×8 Matrix{Bool}:
0  0  0  0  1  0  0  0
0  0  0  0  0  0  1  0
1  0  0  0  0  0  0  0
0  0  0  1  0  0  0  0
0  1  0  0  0  0  0  0
0  0  0  0  0  0  0  1
0  0  0  0  0  1  0  0
0  0  1  0  0  0  0  0

## The 20-queens case

N = 20
perm = optimize(attacks, PermutationSpace(N), GA, seed=1) |> minimizer
20-element Vector{Int64}:
7
4
13
8
18
5
15
19
1
3
14
9
2
12
20
17
11
6
10
16
attacks(perm)
0
chessboard = zeros(Bool, N, N)
for (i,j) = enumerate(perm); chessboard[i,j] = true;end
chessboard
20×20 Matrix{Bool}:
0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0
0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0
0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0
1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0
0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0
0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0
0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0
0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0