Solving the 5-Queens Problem Using Genetic Algorithm

Last Updated on March 18, 2021 by Editorial Team

Author(s): Arman Assankhanov

Computer Science

What is the N-Queen problem?

First of all N-Queen problem is the problem where we need to find an arrangement of N queens on the chessboard, such that no queen can attack any other queens on the board. So in our 5-Queens problem we need to placing 5 chess queens on a 5×5 chessboard so that no two queens attack each other. When we find all possible cases, it would look like the following:

Steps which we need to do

In our task, we need to solve the 5-Queen problem using a Genetic Algorithm. We need to use the principle of evolution to find a solution to a problem.

In order to solve the 5-Queen problem the following steps are needed:

1) Chromosome design
2) Initialization
3) Fitness evaluation
4) Selection
5) Crossover
6) Mutation
7) Update generation
8) Go back to 3)

Let’s briefly explain each step of solving the 5-Queens problem using a Genetic Algorithm.

1) Chromosome design

Firstly, we need to create a chromosome representation. For showing a chromosome, the best way is to represent it as a list of length N where in our case N=5. The value of each index shows the row of the queen in a column. The value of each index is from 1 to 5.

2) Initialization

In the initialization process, we need to arrange a random population of chromosomes (potential solutions) are created. Here is the initial population, I took 4 chromosomes, each of which has a length 5. They are

[5 2 4 3 5]

[4 3 5 1 4]

[2 1 3 2 4]

[5 2 3 4 1]

In particular, these chromosomes can be shown as the following on the chessboard:

3) Fitness evaluation

First of all, the fitness function is pairs of non-attacking queens. So, higher scores are better is better for us. In order to solve the fitness function for the chromosome [5 2 4 3 5], I assigned each queen uniquely as Q1, Q2, Q3, Q4 and Q5. And to find the fitness function value I made the following equation:

Fitness function = F1+F2+F3+F4+F5

where:

F1 = number of pairs of nonattacking queens with queen Q1.

F2 = number of pairs of nonattacking queens with queen Q2.

F3 = number of pairs of nonattacking queens with queen Q3.

F4 = number of pairs of nonattacking queens with queen Q4.

F5 = number of pairs of nonattacking queens with queen Q5.

Here for example if we already counted pair Q1 and Q2 to F1, we should not count the same pair Q2 and Q1 to F2.

So we found that for chromosome [5 2 4 3 5] the fitness function will be equal to 7.

We should evaluate all of our population individuals(chromosomes) using the fitness function. So fitness functions will be the following:

[5 2 4 3 5] fitness function=7

[4 3 5 1 4] fitness function=6

[2 1 3 2 4] fitness function=6

[5 2 3 4 1] fitness function=5

Then we need to compute the probability of being chosen from the fitness function. This will be needed for the next selection step. First, we need to add all fitness functions which will be equal as the following:

7+6+6+5=24

Then we need to compute the probability of being chosen from the fitness function. We need to divide the fitness function by the sum of the fitness function and multiply it to 100%.

[5 2 4 3 5] probability of being chosen = 7/24 *100% = 29%

[4 3 5 1 4] probability of being chosen =6/24 * 100% = 25%

[2 1 3 2 4] probability of being chosen =6/24 * 100% = 25%

[5 2 3 4 1] probability of being chosen =5/24 * 100% = 21%

4) Selection

In the next step, we randomly choose the two pairs to reproduce based on probabilities which we counted on the previous step. In other words, a certain number of chromosomes will survive into the next generator using a selection operator. Here selected chromosomes to act as parents that are combined using crossover operator to make children. In addition to this, we pick a crossover point per pair.

Here we took randomly following chromosomes based on their probabilities:

[4 3 5 1 4]

[5 2 4 3 5]

[4 3 5 1 4]

[2 1 3 2 4]

We can notice that we did not take the chromosome [5 2 3 4 1] because its probability of being chosen is the least among chromosomes.

For the first pair

[4 3 5 1 4]

[5 2 4 3 5]

The crossover point will be picked after two genes.

In the case of the second pair

[4 3 5 1 4]

[2 1 3 2 4]

The crossover point will be picked after three genes.

Here we go to the next step because our fitness value is not equal to Fmax which is the maximum number fitness value in the chromosome that satisfies the condition of the solution of the 5-Queen problem. Fmax is equal to 10.

5) Crossover

In the crossover, selected chromosomes act as parents that are combined using crossover operator to make children. In other words, it combines the genetic information of two parents to generate new offspring.

Here we can see that children generated from the first pair ([4 3 5 1 4] and [5 2 4 3 5]) are the following:

[4 3 4 3 5]

[5 2 5 1 4]

From the second pair ([4 3 5 1 4] and [2 1 3 2 4]) the children are the following:

[4 3 5 2 4]

[2 1 3 1 4]

In other words, in order to create the first child from pair in crossover process, we took the parent #1 chromosome first part and parent #2 chromosome second part which makes the new individual which consists of

[(first part of parent #1 chromosome) [(second part of parent #2 chromosome)]

In order to create the second child from the same pair we took the parent #1 chromosome second part and parent #2 chromosome first part which makes the new individual which consists of

[(second part of parent #1 chromosome) [(first part of parent #2 chromosome)]

So in our case when we create the children of pair [4 3 5 1 4] and [5 2 4 3 5], for producing the first child, we took [(first part of parent #1 chromosome) [(second part of parent #2 chromosome)] = [ 4 3 4 3 5]

For producing second child, we took [(second part of parent #1 chromosome) [(first part of parent #2 chromosome)] = [5 2 5 1 4]

The same process we will do to the second pair ([4 3 5 1 4] and [2 1 3 2 4]).

6) Mutation

The next step is mutation. In the mutation process, we alter one or more gene values in chromosomes which we found after crossover. So it randomly changes a few gens and the mutation probability is low. So in our example, our mutation will look like the following:

[4 3 4 3 5] →[4 3 1 3 5]

[5 2 5 1 4] →[5 2 3 1 4]

[4 3 5 2 4] →[4 3 5 2 4]

[2 1 3 1 4] →[2 1 3 5 4]

where we can notice that the third gene in the chromosome [4 3 4 3 5] changed from 4 to 1.

Also the third gene in the chromosome [5 2 5 1 4] changed from 5 to 3. In addition to this, the fourth gene in the chromosome [2 1 3 1 4] changed from 1 to 5.

So until this, the genetic algorithm to solve the 5-Queen algorithm will look like the following:

7) Update generation

In the next step, we need to update the generation. New chromosomes will update the population but the population number will not change. So the chromosomes

[4 3 1 3 5]

[5 2 3 1 4]

[4 3 5 2 4]

[2 1 3 5 4]

Will be our new population.

8) Go back to step 3

So on the next step, we need to come back to step 3 (fitness evaluation) to find the fitness function of our updated population.

Steps 3–7 are repeated until chromosome (solution) will satisfy the following:

Fitness value == Fmax

Where Fmax is equal to 10

References:

[1]Solving N Queen Problem using Genetic Algorithm

[2] Video explanation of solving 5 Queen Problem using Genetic Algorithm

Post also was published at:

Github repository

If you have questions, suggestions or a compliment, clap or hit the section below😁👇

---

Solving the 5-Queens Problem Using Genetic Algorithm was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Published via Towards AI