Intro — Python Algorithms: Eight Queens Problem | by David Liang

The 8 Queens Problem is a classic puzzle in the field of computer science and mathematics. It involves placing eight queens on an 8x8 chessboard such that no two queens threaten each other. This means that no two queens can be in the same row, column, or diagonal. The problem is a great example of a constraint satisfaction problem and has been used to teach various algorithms and problem-solving techniques.

Table of Contents

The History of the 8 Queens Problem

The 8 Queens Problem was first proposed by the German chess player Max Bezzel in 1848. However, it gained widespread attention when it was published in an article by Franz Nauck in 1850. Since then, it has been a popular topic in computer science and mathematics, serving as a benchmark for various algorithms and techniques.

Understanding the Problem

The 8 Queens Problem can be understood as a combinatorial problem where the goal is to find all possible solutions that satisfy the given constraints. The constraints are:

No two queens can be in the same row.
No two queens can be in the same column.
No two queens can be on the same diagonal.

Given these constraints, the problem can be solved using various algorithms, including backtracking, constraint propagation, and genetic algorithms.

Solving the 8 Queens Problem

There are several approaches to solving the 8 Queens Problem. Some of the most common methods include:

Backtracking Algorithm

The backtracking algorithm is one of the most straightforward methods to solve the 8 Queens Problem. It involves placing queens on the board one by one and removing them (backtracking) if a conflict is detected. The algorithm continues until a solution is found or all possibilities are exhausted.

Here is a step-by-step explanation of the backtracking algorithm:

Start with an empty board.
Place a queen in the first row and first column.
Move to the next row and place a queen in a column that does not conflict with any previously placed queens.
If a conflict is detected, backtrack to the previous row and try the next column.
Repeat the process until all queens are placed or all possibilities are exhausted.

This algorithm is efficient for small boards but can become computationally expensive for larger boards.

Constraint Propagation

Constraint propagation is another method to solve the 8 Queens Problem. It involves reducing the search space by eliminating impossible solutions early in the process. This method is more efficient than backtracking for larger boards.

Here is a step-by-step explanation of the constraint propagation method:

Start with an empty board.
Place a queen in the first row and first column.
Eliminate all columns in the same row and diagonal as the placed queen.
Move to the next row and place a queen in a column that does not conflict with any previously placed queens.
Repeat the process until all queens are placed or all possibilities are exhausted.

This method reduces the number of possible solutions to consider, making it more efficient than backtracking.

Genetic Algorithms

Genetic algorithms are a type of evolutionary algorithm that can be used to solve the 8 Queens Problem. They involve creating a population of possible solutions and evolving them over generations to find the optimal solution.

Here is a step-by-step explanation of the genetic algorithm method:

Create an initial population of possible solutions.
Evaluate the fitness of each solution based on the number of conflicts.
Select the fittest solutions to create the next generation.
Apply crossover and mutation to create new solutions.
Repeat the process until a solution with no conflicts is found or a maximum number of generations is reached.

Genetic algorithms are particularly useful for large and complex problems where traditional methods may not be efficient.

Applications of the 8 Queens Problem

The 8 Queens Problem has several applications in various fields, including:

Computer Science: It is used to teach algorithms and problem-solving techniques.
Mathematics: It is used to study combinatorial problems and constraint satisfaction.
Artificial Intelligence: It is used to develop and test AI algorithms.
Robotics: It is used to plan and optimize robot movements.

The problem serves as a benchmark for various algorithms and techniques, making it a valuable tool in these fields.

Variations of the 8 Queens Problem

There are several variations of the 8 Queens Problem that add additional constraints or modify the board size. Some of the most common variations include:

N Queens Problem

The N Queens Problem is a generalization of the 8 Queens Problem where the board size is NxN instead of 8x8. The constraints remain the same, but the problem becomes more complex as N increases.

Domino Tiling Problem

The Domino Tiling Problem is a variation of the 8 Queens Problem where the goal is to tile a board with dominoes instead of placing queens. The constraints are similar, but the problem involves finding a tiling pattern that covers the entire board without overlaps or gaps.

Knight’s Tour Problem

The Knight’s Tour Problem is another variation where the goal is to find a sequence of moves for a knight on a chessboard such that it visits every square exactly once. The constraints are different from the 8 Queens Problem, but the problem involves similar concepts of movement and constraint satisfaction.

Example Solutions

Here are some example solutions to the 8 Queens Problem using different algorithms:

Backtracking Solution

Here is an example of a backtracking solution in Python:


def is_safe(board, row, col):
    # Check this row on left side
    for i in range(col):
        if board[row][i] == 1:
            return False

# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
    if board[i][j] == 1:
        return False

# Check lower diagonal on left side
for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
    if board[i][j] == 1:
        return False

return True


def solve_n_queens(board, col):
    if col >= len(board):
        return True

for i in range(len(board)):
    if is_safe(board, i, col):
        board[i][col] = 1
        if solve_n_queens(board, col + 1):
            return True
        board[i][col] = 0  # backtrack

return False


def print_board(board):
    for row in board:
        print(” “.join(“Q” if cell == 1 else “.” for cell in row))

board = [[0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0]]

if solve_n_queens(board, 0):
    print_board(board)
else:
    print(“Solution does not exist”)

Constraint Propagation Solution

Here is an example of a constraint propagation solution in Python:


def is_safe(board, row, col):
    # Check this row on left side
    for i in range(col):
        if board[row][i] == 1:
            return False

# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
    if board[i][j] == 1:
        return False

# Check lower diagonal on left side
for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
    if board[i][j] == 1:
        return False

return True


def solve_n_queens(board, col):
    if col >= len(board):
        return True

for i in range(len(board)):
    if is_safe(board, i, col):
        board[i][col] = 1
        if solve_n_queens(board, col + 1):
            return True
        board[i][col] = 0  # backtrack

return False


def print_board(board):
    for row in board:
        print(” “.join(“Q” if cell == 1 else “.” for cell in row))

board = [[0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0]]

if solve_n_queens(board, 0):
    print_board(board)
else:
    print(“Solution does not exist”)

Genetic Algorithm Solution

Here is an example of a genetic algorithm solution in Python:


import random

def generate_individual(size):
    return random.sample(range(size), size)

def fitness(individual):
    horizontal_collisions = sum([individual.count(queen) - 1 for queen in individual]) / 2
    diagonal_collisions = 0

n = len(individual)
left_diagonal = [0] * 2*n
right_diagonal = [0] * 2*n
for i in range(n):
    left_diagonal[i + individual[i]] += 1
    right_diagonal[n - i + individual[i]] += 1

diagonal_collisions = sum([left_diagonal.count(x) - 1 for x in left_diagonal]) / 2
diagonal_collisions += sum([right_diagonal.count(x) - 1 for x in right_diagonal]) / 2
return int(horizontal_collisions + diagonal_collisions)


def select(population):
    return random.choices(population, weights=[1/fitness(ind) for ind in population], k=2)

def crossover(parent1, parent2):
    size = len(parent1)
    crossover_point = random.randint(1, size - 1)
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]
    return child1, child2

def mutate(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            individual[i] = random.randint(0, len(individual) - 1)
    return individual

def genetic_algorithm(size, population_size, generations, mutation_rate):
    population = [generate_individual(size) for _ in range(population_size)]
    for generation in range(generations):
        population = sorted(population, key=fitness)
        if fitness(population[0]) == 0:
            return population[0]
        new_population = population[:2]
        for _ in range(int(population_size / 2) - 1):
            parent1, parent2 = select(population)
            child1, child2 = crossover(parent1, parent2)
            new_population += [mutate(child1, mutation_rate), mutate(child2, mutation_rate)]
        population = new_population
    return population[0]

size = 8
population_size = 100
generations = 1000
mutation_rate = 0.01
solution = genetic_algorithm(size, population_size, generations, mutation_rate)
print(“Solution:”, solution)

📝 Note: The genetic algorithm solution may take longer to find a solution compared to backtracking or constraint propagation methods. However, it is more robust for larger and more complex problems.

Visualizing the 8 Queens Problem

Visualizing the 8 Queens Problem can help in understanding the solutions better. Here is an example of how the solutions can be visualized:

Challenges and Limitations

The 8 Queens Problem is a well-defined problem with clear constraints and solutions. However, there are several challenges and limitations to consider:

Computational Complexity: The problem can become computationally expensive for larger boards, making it challenging to find solutions efficiently.
Scalability: The problem does not scale well with increasing board size, making it difficult to solve for very large boards.
Heuristics: Finding effective heuristics to guide the search for solutions can be challenging, especially for larger boards.

Despite these challenges, the 8 Queens Problem remains a valuable tool for teaching algorithms and problem-solving techniques.

Conclusion

The 8 Queens Problem is a classic puzzle that has been studied extensively in the fields of computer science and mathematics. It involves placing eight queens on an 8x8 chessboard such that no two queens threaten each other. The problem can be solved using various algorithms, including backtracking, constraint propagation, and genetic algorithms. The 8 Queens Problem has several applications in different fields and serves as a benchmark for various algorithms and techniques. Understanding the 8 Queens Problem and its solutions can provide valuable insights into constraint satisfaction problems and algorithm design.

Related Terms: