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

What is the 8-queen problem using genetic algo? ›

8 queens is a classic computer science problem. To find possible arrangements of 8 queens on a standard 8 x 8 chessboard such that no queens every end up in an attacking configuration. Now, if one knows the basics of chess, one can say that a queen can travel either horizontally, vertically, or diagonally.

What is the algorithm for the 8 queens problem? ›

The algorithm starts by placing a queen on the first column, then it proceeds to the next column and places a queen in the first safe row of that column. If the algorithm reaches the 8th column and all queens are placed in a safe position, it prints the board and returns true.

Is the 8 queens problem solvable? ›

There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques."

How many possible solutions do you get for an 8-queen 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 main idea of the genetic algorithm? ›

The genetic algorithm is a method for moving from one population of chromosomes (encoded solution) to a new population by using a kind of natural selection together with the genetics-inspired operators of crossover, mutation, and inversion.

What is the fitness function for the 8-queen problem? ›

The proposed fitness function is based on the chessboard arrangement, and in particular, it is inversely proportional to the number of clashes amongst attacking positions of queens; thus, a high fitness value implies a low number of clashes. This can be calculated quite easily in the context of 8-queen problem.

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 objective function in 8 queens problem? ›

The objective function will count the number of queens that are positioned in a place where they cannot be attacked. Given that queens move vertically, it's reasonable to say that no queen should be placed in the same vertical and thus we can represent the position of each queen in a simple array of 8 positions.

What is the time complexity of the 8 queens problem? ›

Space and Time Complexity

In the worst case, the algorithm tries to place a queen in each of the N rows in the first column, then in each of the remaining N-1 rows in the second column, and so on. This leads to a time complexity of O(N * (N-1) * (N-2) * … * 1) = O(N!) .

Which technique is commonly used to solve the n-queens problem? ›

The backtracking algorithm is used to solve the N queen problem, in which the board is recursively filled with queens, one at a time, and backtracked if no valid solution is found. At each step, the algorithm checks to see if the newly placed queen conflicts with any previously placed queens, and if so, it backtracks.

Which of the following searching mechanism is associated with the 8 queen problem? ›

8 - queen's problem:

It is the backtracking approach. In backtracking approach, all the possible configurations are checked and check whether result is obtained or not. A queen can only be attacked if it is in the same row or column or diagonal of another queen.

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.

What is the 8 queen puzzle problem in AI? ›

The 8 Queen Problem is a puzzle in which 8 queens must be placed on an 8x8 chessboard so that no two queens threaten each other. It is a classic problem in computer science and mathematics. There are 92 solutions to this problem. The eight queens puzzle problem was first posed in the mid-19th century.

What are the problems with genetic algorithm? ›

Genetic algorithms do not scale well with complexity. That is, where the number of elements which are exposed to mutation is large there is often an exponential increase in search space size. This makes it extremely difficult to use the technique on problems such as designing an engine, a house or a plane.

What is n queens problem in design and analysis of algorithms? ›

The N-Queens Problem is a chess puzzle in which N chess queens must be placed on a NxN chessboard so that no two queens threaten each other. It has received extensive research in computer science and mathematics, and it is frequently used as a standard for evaluating algorithms and heuristics.

Top Articles
Latest Posts
Article information

Author: Jerrold Considine

Last Updated:

Views: 6086

Rating: 4.8 / 5 (78 voted)

Reviews: 85% of readers found this page helpful

Author information

Name: Jerrold Considine

Birthday: 1993-11-03

Address: Suite 447 3463 Marybelle Circles, New Marlin, AL 20765

Phone: +5816749283868

Job: Sales Executive

Hobby: Air sports, Sand art, Electronics, LARPing, Baseball, Book restoration, Puzzles

Introduction: My name is Jerrold Considine, I am a combative, cheerful, encouraging, happy, enthusiastic, funny, kind person who loves writing and wants to share my knowledge and understanding with you.