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.

---

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

We will see that these two encodings behave differently. In Vita 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);

vita::ga_problem prob(NQUEENS, {0, NQUEENS});

which is a short cut for:

const int NQUEENS(8);

vita::ga_problem prob;

for (int i(0): i < NQUEENS; ++i)
  prob.insert(range(0, 8));

Fitness function

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

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

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

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

auto f = [](const vita::i_ga &x) -> vita::fitness_t
{
  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

vita::ga_search<decltype(f)> search(prob, f);
auto result = search.run();

The ga_search class drives the evolution.

It's interesting to note the crossover operator depends on the encoding. If a 24-bit encoding is used instead of 8-numbers, then the crossover point has a change (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.

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 would be intractable for problems of $n ≥ 20$, as $20! = 2.433 × 1018$.