Introducing N-Queens

Genetic Algorithms in Elixir — by Sean Moriarity (49 / 101)

👈 Chapter 6 Generating New Solutions | TOC | Solving N-Queens with Order-One Crossover 👉

Imagine your friend challenges you to array eight queens on a standard chess board so that none of the queens conflict with another. This problem, known as N-queens, is a fundamental constraint satisfaction problem, similar to the knapsack problem introduced in Chapter 4, ​Evaluating Solutions and Populations​. In N-queens, the objective is to configure N queens on a chess board so that no queen threatens another. In chess, a piece is “threatened” when another piece can move to the square it occupies to “capture” it. The queen is permitted to move horizontally, vertically, and diagonally any number of spaces on the board. Because queens can move in any direction horizontally or vertically, it’s only possible to create a correct configuration of N queens on an NxN chess board.

The following image illustrates a correct solution to the N-queens problem with eight queens on an 8x8 chess board:

N-queens is a combinatorial optimization problem — which, as you already know, genetic algorithms are well-suited for. You’ll attempt to solve N-queens to demonstrate the importance of using a good crossover strategy in your algorithms.