Solving the 8 queen problem using genetic algorithm

The 8 queen problem is a classic, well-known problem in artificial intelligence and combinatorial optimizationImprove an algorithm by using mathematical methods either to reduce the size of the set of possible solutions or to make the search itself faster..

Objective

The goal is to place eight queens on an 8x8 chessboard so that no two queens threaten or attack each other. To prevent the queens from attacking one another, no two queens should be in the same row, column, or diagonal.

Approach

One approach to solving this problem is using a genetic algorithm (GA). A genetic algorithm is an informed search heuristic greatly inspired by the biological principles of natural selection and genetics.

It iteratively enhances a population of potential solutions by simulating the natural evolution process, which includes mutation, crossover, and selection. The process continues until a satisfactory solution or the maximum number of generations is reached.

Steps in the Genetic Algorithm:

Initialization: Create a randomized population of potential solutions (board states). These arrays represent the queen's positions on the chessboard. The index represents the column, and the row represents the value.

The fitness is calculated by adding the number of non-attacking pairs for each queen. For instance, for board A, the queen positions are [3, 2, 7, 5, 2, 4, 1, 1] , the queen at index 1, value 3 has 6 non-attacking pairs, the queen at index 2, value 2 has 5 non-attacking pairs, the queen at index 3, value 7 has 4 non-attacking pairs and it goes on for the remaining queens till the 8th index. The number of non-attacking pairs for each queen in the board is added and fitness is evaluated.

Selection: Select parents from the current population to create the next generation. Standard selection methods include:

Tournament selection
Roulette wheel selection
Rank-based selection

Crossover: Perform crossover between pairs of parents to create new offspring. Crossover involves exchanging genetic information to create a child solution.

Note: In case of the 8 queen problem, typically a single-point crossoverA random crossover point is selected, and the parts beyond that point are exchanged between parents. is employed.

Before crossover:

The third element of the array is set as the crossover point. It means all the elements highlighted in blue will remain the same whereas the grey color of both arrays, A and B will exchange the rest of the elements with one another to produce diverse offspring.

Replacement: Replace the current population with the new generation of offspring solutions.
Termination: Repeat steps 2 to 6 until a termination condition is met, such as finding a satisfactory solution or reaching a maximum number of generations.

Code example

Let’s look at an example with a population size of 50, a mutation rate of 0.1, and a maximum of 100 generations. The initial population is randomly generated, and fitness is evaluated for each candidate solution. Selection is performed using tournament selection, and crossover involves single-point crossover. Mutation randomly swaps two positions in a board state.

Here is a Python implementation of the genetic algorithm-based 8 queen problem:

import random
# Genetic Algorithm parameters
POPULATION_SIZE = 50
MUTATION_RATE = 0.1
MAX_GENERATIONS = 100
# Generate a random board state
def generate_board_state():
    board_state = [random.randint(0, 7) for _ in range(8)]
    return board_state
# Calculate the fitness of a board state
def calculate_fitness(board_state):
    conflicts = 0
    for i in range(8):
        for j in range(i + 1, 8):
            if board_state[i] == board_state[j] or abs(board_state[i] - board_state[j]) == j - i:
                conflicts += 1
    return 28 - conflicts  # Max fitness = 28 (no conflicts)
# Select parents for crossover using tournament selection
def tournament_selection(population):
    tournament_size = 5
    tournament = random.sample(population, tournament_size)
    return max(tournament, key=lambda x: x[1])
# Crossover operation (single-point crossover)
def crossover(parent1, parent2):
    crossover_point = random.randint(1, 7)
    child = parent1[:crossover_point] + parent2[crossover_point:]
    return child
# Mutation operation (swap two positions)
def mutate(board_state):
    pos1, pos2 = random.sample(range(8), 2)
    board_state[pos1], board_state[pos2] = board_state[pos2], board_state[pos1]
    return board_state
# Generate the initial population
population = [(generate_board_state(), 0) for _ in range(POPULATION_SIZE)]
# Main Genetic Algorithm loop
for generation in range(MAX_GENERATIONS):
    # Calculate fitness for each board state
    population = [(board_state, calculate_fitness(board_state)) for board_state, _ in population]
    # Check if solution is found
    best_board_state = max(population, key=lambda x: x[1])[0]
    if calculate_fitness(best_board_state) == 28:
        print("Solution found in generation", generation)
        break
    # Create the next generation
    new_population = []
    # Elitism: Keep the best board state from the previous generation
    new_population.append(max(population, key=lambda x: x[1]))
    # Perform selection, crossover, and mutation
    while len(new_population) < POPULATION_SIZE:
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        child = crossover(parent1[0], parent2[0])
        if random.random() < MUTATION_RATE:
            child = mutate(child)
        new_population.append((child, 0))
    # Update the population
    population = new_population
# Print the best solution
print("Best solution:", best_board_state)

# Select parents for crossover using roulette wheel selection selection
def roulette_wheel_selection(population):
    # Calculate total fitness sum of the population
    total_fitness = sum(individual[1] for individual in population)
    # Generate a random number between 0 and the total fitness sum
    spin = random.uniform(0, total_fitness)
    # Iterate through the population and sum fitness values until the spin value is reached
    fitness_sum = 0
    for individual in population:
        fitness_sum += individual[1]
        if fitness_sum >= spin:
            return individual

Solving the 8 queen problem using genetic algorithm

Objective

Approach

Steps in the Genetic Algorithm:

Code example

Output

Conclusion