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

`julia> N = 8 # for 8-queens`

`8`

`julia> cardinality(BitArraySpace(N*N))`

`18446744073709551616`

`julia> 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.0078 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
```