Eight Queens Puzzle with Genetic Algorithms

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal.

Eight Queens Puzzle with (basic) Genetic Algorithms

NOTE. The following example is derived from Artificial Intelligence: A Modern Approach.

Individuals

Local search algorithms typically use a complete-state formulation, where each state has 8 queens on the board, one per column. The successors of a state are all possible states generated by moving a single queen to another square in the same column.

Classical GAs represent a state (here called chromosome or individual) with a string of 0s and 1s (it requires 24 bits to specify the position of 8 queens each in a column of 8 squares).

Alternatively each individual can be represented as an eight-numbers (in the [1,8] interval) vector.

These two encodings behave differently. In Ultra, we adopt the second representation (with the difference that, as usual in C/C++, the interval is [0,7] instead of [1,8]):

const int NQUEENS(8);

ga::problem prob(NQUEENS, {0, NQUEENS});

which is a short cut for:

const int NQUEENS(8);

ga::problem prob;

for (int i(0); i < NQUEENS; ++i)
  prob.insert({0, 8});

Fitness function

The starting point is the heuristic cost function h, which counts the number of pairs of queens attacking each other, either directly or indirectly.

The global minimum of this function is 0, which occurs only at perfect solutions.

The figure shows a state with h = 17. It also displays the values of all its successors, with the best successors having h = 12.

A fitness function should return higher values for better states, Thus, for this task, we use f = -h (in general minimizing a function g is equivalent to maximizing -g). The implementation is quite straightforward:

auto f = [](const ga::individual &x)
{
  double attacks(0);

  for (int queen(0); queen < NQUEENS - 1; ++queen)
  {
    const int row(x[queen]);

    for (int i(queen + 1); i < NQUEENS; ++i)  // skips the last queen
    {
      const int other_row(x[i]);

      if (other_row == row                            // same row
          || std::abs(other_row - row) == i - queen)  // or diagonal
        ++attacks;
    }
  }

  return -attacks;
};

Evolution

ga::search search(prob, f);
auto result = search.run();

The ga::search class drives the evolution.

It's interesting to note that the crossover operator depends on the encoding. If a 24-bit encoding is used instead of eight-numbers encoding, the crossover point has a chance (2/3 in case of one point crossover) of being in the middle of a digit, which results in an essentially arbitrary mutation of that digit.

The source code of the complete example is contained in the examples/8queens/8queens.cc file.

This is a quite trivial puzzle for GAs (indeed brute-force algorithms to count the number of solutions are computationally manageable for NQUEENS = 8), but it becomes rapidly intractable for problems with larger boards.

Eight Queens Puzzle with (heterogeneous) Genetic Algorithms

Here, the implementation of Heterogeneous Genetic Algorithms (HGA) provides a more efficient approach. The ga::individuals used earlier are well-suited for processing tasks involving continuous, mixed-integer, pure-integer, or combinatorial optimisation. However, for a combination of these optimisation areas, mapping them to simple strings of values becomes increasingly difficult, depending on the task. The hga::individual (hga stands for heterogeneous GA) extends the gene concept.

A gene represents an elementary trait of the phenotype, potentially having multiple parameters. For this purpose, gene types are defined, containing as many parameters of the appropriate data type as are required to describe the particular element of the phenotype. A chromosome now consists of genes as data objects of the gene types, whereby, depending on the application, each gene type occurs exactly once as a gene or can be contained in the chromosome any number of times.

Gene type definitions also specify valid value ranges for gene parameters. These constraints ensure that chromosome generation and mutation operations avoid lethal mutations. For tasks with a combinatorial component, specialized genetic operators can move or reposition genes while preserving their internal structure. We're going to use a hga::permutation gene:

hga::problem prob;
prob.insert<hga::permutation>(NQUEENS);

This defines a problem where an individual consists of a single gene of type hga::permutation; the parameter NQUEENS specifies the length of the permutation.

By using permutations, we effectively reduce the search space from \(NQUEENS^{NQUEENS}\) to \(NQUEENS!\). Permutation-type genes are handled by a specific algorithm (PMX).

There are no major modifications required beyond this. In the fitness function only a single line has been added for simplifying access to permutation elements:

const auto columns(std::get<D_IVECTOR>(x[0]));

and a line has been removed:

if (std::abs(other_row - row) == i - queen)  // diagonal
  ++attacks;

since checking for diagonal attacks is now enough (the permutation automatically ensures that no row attack is possible).

The final examples, modified for a 64-columns board, is contained in the examples/8queens/8queens02.cc file.

Brute force approach

A non naïve brute-force approach gives an interesting basis for comparison with the GA-based solution:

% Solves the 8-Queens problem, where 8 queens must be placed on a chessboard so
% that no two queens attack each other.

% takeout/3 removes an element X from a list.
% Many Prolog libraries already have the delete/3 predicate.
takeout(X, [X|R], R).
takeout(X, [F|R], [F|S]) :- takeout(X, R, S).

% safe/1 checks if a list of queens is in a safe configuration.
safe([]).
safe([Queen|Others]) :-
    safe(Others),
    no_attack(Queen, Others, 1).

% no_attack/3 ensures that a queen does not attack others diagonally.
no_attack(_, [], _).
no_attack(Y, [Y1|Ylist], Xdist) :-
    abs(Y1-Y) =\= Xdist,  % ensure no diagonal conflict
    Dist1 is Xdist + 1,   % move to the next column distance
    no_attack(Y, Ylist, Dist1).

% place_queens/3: Places queens one by one, ensuring safety at each step.
place_queens([], PlacedQueens, PlacedQueens).  % all queens placed safely
place_queens(AvailableQueens, PlacedQueens, Result) :-
    member(Queen, AvailableQueens),  % choose a valid row for the queen
    safe([Queen|PlacedQueens]),      % ensure it's a safe placement
    takeout(Queen, AvailableQueens, RemainingQueens),
    place_queens(RemainingQueens, [Queen | PlacedQueens], Result).

solution(Queens) :-
    place_queens([1,2,3,4,5,6,7,8], [], Queens).

This program constructs the search tree by considering one column of the board at a time. It eliminates most non-solution board positions at a very early stage in their construction by rejecting diagonal attacks even on incomplete boards.

Of course, constraint programming can be even more effective on this problem. Nevertheless this implementation is more than enough to understand the qualitative difference between the previous evolutionary-based approach and a simple brute force method.

Moreover it should be taken into account that: - a hyper-specific mutation operator could be written based on the min-conflicts algorithm and this is particularly effective; - if the goal is to find a single solution, one can show solutions exist for all \(NQUEENS ≥ 4\) with no search whatsoever (these solutions exhibit stair-stepped patterns).

The Prolog example is available in the examples/8queens/8queens.pl file.