Edit on GitHub

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-queens8
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.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