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.

Start by creating a new file called n_queens.exs in your scripts folder. In this file, you’ll write an encoding of the N-queens problem and run your algorithm to obtain a solution.

In n_queens.exs, define the module and specify the Problem behaviour, like this:

​ ​defmodule​ NQueens
​   @behaviour Problem
​   alias Types.Chromosome
​ 
​   ​# Rest goes here​
​ ​end​

Implementing the Genotype

Remember, you need to define three functions to correctly implement the Problem behaviour. The first function is genotype/0, which returns the genotype your algorithm will use. At first, you might be tempted to encode solutions using a binary genotype where each index represents whether a queen is present or not. However, it’s smarter to keep track of a permutation of size 8 representing the location of each queen on the board. For example, the solution [0, 2, 1, 3, 6, 4, 7, 5] represents the following configuration on the chess board:

To create a permutation genotype, add the following function to NQueens:

​ @impl true
​ ​def​ genotype ​do​
​   genes = Enum.shuffle(0..7)
​   %Chromosome{​genes:​ genes, ​size:​ 8}
​ ​end​

Enum.shuffle/1 scrambles the given enumerable. In this function, you pass the range 0..7 to represent a permutation of size 8.

Next, you need to define a fitness function.

Implementing the Fitness Function

Remember, the objective is to configure a chess board so that there are no conflicts between any of the pieces on the board. Your objective is to minimize these conflicts; therefore, your fitness function should measure the number of conflicts in some way.

To do this, you need to check solutions across each row and diagonally. Your genotype restricts queens from being in the same column; however, they can still be in the same row.

Your fitness function should look like this:

​ @impl true
​ ​def​ fitness_function(chromosome) ​do​
​   diag_clashes =
​     for i <- 0..7, j <- 0..7 ​do​
​       ​if​ i != j ​do​
​         dx = abs(i - j)
​         dy =
​           abs(
​             chromosome.genes
​             |> Enum.at(i)
​             |> Kernel.-(Enum.at(chromosome.genes), j)
​           )
​         ​if​ dx == dy ​do​
​           1
​         ​else​
​           0
​         ​end​
​       ​else​
​         0
​       ​end​
​     ​end​
​   length(Enum.uniq(chromosome.genes)) - Enum.sum(diag_clashes)
​ ​end​

First, you calculate the number of diagonal clashes in the solution. Next, you filter out duplicate values in the chromosome because those represent row clashes. Finally, you return the difference. The fitness function will return the number of non-conflicts or the number of pieces that don’t conflict with any others.

The final step is to define your termination criteria.

Defining Termination Criteria and Running

Because the fitness function returns the number of non-conflicts, your algorithm is complete when the maximum fitness of the population is 8. In other words, your algorithm is complete when there are no conflicts on the board.

Your termination criteria is:

​ @impl true
​ ​def​ terminate?(population, _generation), ​do​:
​   Enum.max_by(population, &NQueens.fitness_function/1).fitness == 8

To run your algorithm, add the following lines beneath your module definition:

​ soln = Genetic.run(NQueens)
​ 
​ IO.write(​"​​\n"​)
​ IO.inspect(soln)

Next, open a terminal and run mix run scripts/n_queens.exs:

​ ​$​ mix run scripts/n_queens.exs
​ Current ​Best:​ 5

What’s going on here? Your solution stagnates before ever reaching the maximum possible fitness.

The problem is your crossover function creates invalid chromosomes. Right now, your framework uses single-point crossover. Single-point crossover doesn’t preserve the integrity of the permutation — you need to implement a crossover strategy that works for permutations.

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

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.