Genetic Algorithm: 8 Queens Problem (2024)

In my recent lecture on AI (CS4100), I came across an interesting concept: a genetic algorithm. As described in “Artificial Intelligence: A Modern Approach” by Stuart et al., evolutionary algorithms can be seen as variants of the stochastic beam search that attempts to copy the metaphor of natural selection in biology. The textbook describes the algorithm as such: “there is a population of individuals (states), in which the fittest (highest value) individuals produce offspring (successor states) that populate the next generation, a process called recombination.” When I first heard of this concept, it reminded me of this video, a neural network learning to play Super Mario World using genetic algorithms, something that I still want to try and implement someday. This concept seemed so abstract yet it made perfect sense. After all, you could think of an algorithm working towards a solution as evolution. In this blog post, I will be applying a simple genetic algorithm to the classic 8 queens problem.

Genetic Algorithm: 8 Queens Problem (3)

The 8 queens problem is simple. On an 8x8 chess board, the queen can move any number of squares horizontally, vertically, and diagonally. Normally, there is one queen per side on the board but for this problem, there are 8. This can be generalized to N queens on an NxN board. The goal is to place 8 queens on the board such that every pair of queens aren’t attacking each other. In the picture above, you can see that every queen is not in the line of sight of another queen. Here’s an example of a board state that is not the solution:

Genetic Algorithm: 8 Queens Problem (4)

The pair of queens on the 4th and 7th columns are attacking each other diagonally.

To apply the genetic algorithm framework, we need to convert a board state into a viable input. In genetic algorithms, each individual in a population is a string over a finite alphabet, similar to that of a DNA sequence. We can convert a chessboard into a string of numbers so that the index of each number is the column number and the number at each index is the row number, starting from the bottom left. The picture above would convert to 16257483. In this experiment, I represented each string as a list, so [1, 6, 2, 5, 7, 4, 8, 3].

The visual below is a rundown of how the genetic algorithm will work:

Genetic Algorithm: 8 Queens Problem (5)

Starting off, I randomized a population of individuals with POPULATION_SIZE = 10. Then, I decided on a fitness function that would mimic the “natural selection” process of the algorithm. The simplest one would be the number of non-attacking pairs of queens. The solution to the problem would be the 8 choose 2, the possible number of pairs of queens. In the code below, I define NUM_QUEENS = 8.

def fitness_score(seq):
score = 0

for row in range(NUM_QUEENS):
col = seq[row]

for other_row in range(NUM_QUEENS):

#queens cannot pair with itself
if other_row == row:
continue
if seq[other_row] == col:
continue
if other_row + seq[other_row] == row + col:
continue
if other_row - seq[other_row] == row - col:
continue
#score++ if every pair of queens are non-attacking.
score += 1

#divide by 2 as pairs of queens are commutative
return score/2

Next is the selection process. We define a mixing number, ρ, which is the number of parents of an offspring. Normally, ρ = 2, (or ρ = 1 for asexual reproduction). However, as this is only a simulation, we can choose ρ > 2. For selecting the parents, one way to do it is to choose a random n number of individuals and have the top ρ fitness scoring individuals be the parents. For this experiment, I capped the number of parents to half the population size, and selected parents with probability proportional to their fitness score.

Then, we have the crossover. When ρ = 2, I randomly chose a crossing point (index in the list). The first part of the first parent is crossed with the second part of the second parent to produce an offspring. The process is repeated for the second offspring. A visual below shows what happens:

Genetic Algorithm: 8 Queens Problem (6)

For example, we have the parents 1234 and 5678 where the crossing point is 2, then the offspring produced is 1278 and 3456.

I wanted to also account for ρ > 2, so I decided to implement the crossover this way: generate ρ-1 random crossover points between [0, NUM_QUEENS]. Using these crossover points, we will generate permutations of offsprings that are combined from ρ parents. Given x parents, there would be x choose ρ * ρ! offsprings. In the code below, I defined MIXING_NUMBER = 2.

import itertoolsdef crossover(parents):

#random indexes to to cross states with
cross_points = random.sample(range(NUM_QUEENS), MIXING_NUMBER - 1)
offsprings = []

#all permutations of parents
permutations = list(itertools.permutations(parents, MIXING_NUMBER))

for perm in permutations:
offspring = []

#track starting index of sublist
start_pt = 0

for parent_idx, cross_point in enumerate(cross_points): #doesn't account for last parent

#sublist of parent to be crossed
parent_part = perm[parent_idx][start_pt:cross_point]
offspring.append(parent_part)

#update index pointer
start_pt = cross_point

#last parent
last_parent = perm[-1]
parent_part = last_parent[cross_point:]
offspring.append(parent_part)

#flatten the list since append works kinda differently
offsprings.append(list(itertools.chain(*offspring)))

return offsprings

Lastly is mutation. For each number in a sequence, there is an arbitrary MUTATION_RATE = 0.05 of changing to a different number.

def mutate(seq):
for row in range(len(seq)):
if random.random() < MUTATION_RATE:
seq[row] = random.randrange(NUM_QUEENS)

return seq

Using the functions we wrote, I tested the algorithm on the parameters POPULATION_SIZE = 10, NUM_QUEENS = 8, MIXING_NUMBER = 2, and MUTATION_RATE = 0.05. Here is the initial population from a test run:

Genetic Algorithm: 8 Queens Problem (7)

When I was generating the random populations, I did not expect the fitness scores to be this high. The highest was a 22, only 6 away from the goal of 28. To check if I wasn’t just getting lucky, I generated 100,000 random board states and got a mean fitness score of 20.13518 and standard deviation of 2.3889, so 22 was normal.

After running the algorithm, the solution was found on the 162nd generation. This was unexpectedly fast, so I tried to run it again. This time, it took almost 3000 generations. My guess is a random positive mutation could’ve happened along the way to accelerate the evolution or lucky recombination.

Genetic Algorithm: 8 Queens Problem (8)

Running the algorithm 200 times, I obtained the following stats: a mean of 3813.53 generations with a standard deviation of 27558.146. Looking at the standard deviation, obviously, something went wrong. The highest generation was 377241 and the minimum was 10. As for the 377241 outlier, I would guess that there were individuals in the population with a high fitness score but with repetitive positions on the board, resulting in low variation with recombination, so the algorithm had to rely on a mutation to get out of the deadlock.

Genetic Algorithm: 8 Queens Problem (9)
Genetic Algorithm: 8 Queens Problem (10)

If we look at the results between the first and third quarter, our mean and standard deviation is not too far off. When I adjusted the results with an outlier removing function from Stack Overflow where the median of distances from the median is less than a value m=2, the stats look to be more promising.

Genetic Algorithm: 8 Queens Problem (11)

If we look at a pure brute force method of guessing the correct solution, assuming a normal distribution when generating an individual, the probability of getting the solution is about P(solution) = 0.0005. It would take about 1386 generations for a 0.5 chance of guessing the solution, or 5990 generations for a 0.95 chance. Compared to the mean of 280, on average, the genetic algorithm takes 21 times faster. In conclusion, using a genetic algorithm can be a way to solve the 8 queens problem.

Overall, this experiment was a fun way to explore the genetic algorithm. Objectively, I don’t think that a genetic algorithm would be the best way to solve the 8 queens problem, and I do suspect that a scholastic beam search would be much more efficient. If we look at recombination in the context of mixing board states with queens placed, it does seem like random offsprings are produced rather than “stronger” offsprings. I think some other experiments I could still further explore would be seeing the algorithm work for N queens or increasing the mixing number which would give even more randomized offsprings.

Code available at: https://github.com/chengxi600/RLStuff/blob/master/Genetic%20Algorithms/8Queens_GA.ipynb

Genetic Algorithm: 8 Queens Problem (2024)

FAQs

Is there a solution to the 8 queens problem? ›

"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. There are 92 solutions.

What is the best algorithm for the 8 queens problem? ›

Which algorithm is used to solve 8 queens problem? One common algorithm used to solve the 8 Queens Problem is the backtracking algorithm, which tries to place queens on the chessboard column by column, checking if each placement is valid and backtracking if it is not.

What is the genetic algorithm for the N queen problem? ›

Genetic Algorithm is used with a novel fitness function as the Meta-heuristic. The aim of N-Queens Problem is to place N queens on an N x N chessboard, in a way so that no queen is in conflict with the others. Chromosome representation and genetic operations like Mutation and Crossover are described in detail.

How many solutions are there to the N Queens problem? ›

It has long been known that there are 92 solutions to the problem. Of these 92, there are 12 distinct patterns. All of the 92 solutions can be transformed into one of these 12 unique patterns using rotations and reflections. The 12 basic solutions can be constructed using the following table.

How many possible solutions exist for an 8 queen problem 100? ›

The eight queens puzzle has 92 distinct solutions. If solutions that differ only by the symmetry operations of rotation and reflection of the board are counted as one, the puzzle has 12 solutions. These are called fundamental solutions; representatives of each are shown below.

What is the prize for the 8 queens problem? ›

The underlying problem is one of the most major unsolved problems in computer science and mathematics. Known as P versus NP, it is one of the seven Millennium Prize Problems which carry the million dollar reward for their first correct solution.

What is the complexity of the 8 queens problem? ›

Approach: Bruteforce

A simple brute-force solution would be to generate all possible chess boards with 8 queens. Accordingly, there would be N^2 positions to place the first queen, N^2 – 1 position to place the second queen and so on. The total time complexity, in this case, would be O(N^(2N)), which is too high.

What is the best heuristic for the 8 puzzle? ›

A good heuristic for the 8-puzzle is the number of tiles out of place. A better heuristic is the sum of the distances of each tile from its goal position ("Manhattan distance"). An even better heuristic takes into account the number of direct adjacent tile reversals present.

Which algorithm is used in 8 puzzle problem? ›

8 puzzle Problem using BFS (Brute-Force)

We can perform a Breadth-first search on the state space tree. This always finds a goal state nearest to the root. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS. Breadth-first search on the state-space tree.

Is genetic algorithm difficult? ›

Genetic algorithms are simple to implement, but their behavior is difficult to understand.

How good is genetic algorithm? ›

Genetic algorithms that belong to the family of biological algorithms can also solve highly complex problems that are otherwise too difficult to solve using traditional optimization algorithms. It has a high probability of finding the global minima and not getting stuck to local minima.

What is the optimal solution for N Queen problem? ›

There are N rows, so we will place one queen in each row(as no two queens can be in the same column) such that they all are safe from each other. We will use backtracking to solve the problem. It is a recursive approach in which we place the queen at a safe position and then recur for the remaining queens.

How many solutions are there to 8 queens? ›

Altogether, this page represents 92 solutions to the problem of eight queens; brute force shows that no other solutions exist.

Is 8 queens problem NP-Complete? ›

The problem of putting eight queens on the chess board so as no queen attacks another is a solved problem, as is placing n queens on an nxn board. However if you place some queens on the board and ask for a completion then the problem is NP complete.

How many possible solutions exist for an 6 queen problem? ›

N-queens is a problem to place N queens on an N ¢ N chess board such that no queen can attack another. For ex- ample, the 6-queens problem has four solutions, as shown in Figure 1. This problem is commonly used as a benchmark program [1,2] for computer systems and as an example in computer science. ...

Is 8 queens problem np complete? ›

The problem of putting eight queens on the chess board so as no queen attacks another is a solved problem, as is placing n queens on an nxn board. However if you place some queens on the board and ask for a completion then the problem is NP complete.

What is the best way to solve N Queen problem? ›

Solution to the N-Queens Problem

The way we try to solve this is by placing a queen at a position and trying to rule out the possibility of it being under attack. We place one queen in each row/column. If we see that the queen is under attack at its chosen position, we try the next position.

How many solutions are there for 8 queens on 8 * 8 board 91 93 92 90? ›

How many solutions are there for 8 queens on 8*8 board? Explanation: For 8*8 chess board with 8 queens there are total of 92 solutions for the puzzle.

Top Articles
Latest Posts
Recommended Articles
Article information

Author: Nicola Considine CPA

Last Updated:

Views: 6013

Rating: 4.9 / 5 (49 voted)

Reviews: 88% of readers found this page helpful

Author information

Name: Nicola Considine CPA

Birthday: 1993-02-26

Address: 3809 Clinton Inlet, East Aleisha, UT 46318-2392

Phone: +2681424145499

Job: Government Technician

Hobby: Calligraphy, Lego building, Worldbuilding, Shooting, Bird watching, Shopping, Cooking

Introduction: My name is Nicola Considine CPA, I am a determined, witty, powerful, brainy, open, smiling, proud person who loves writing and wants to share my knowledge and understanding with you.