Home

 › 

Articles

 › 

Understanding the N-Queen Problem, With Examples

ai chatbot

Understanding the N-Queen Problem, With Examples

The N-Queen Problem is a classic puzzle that has been around for a long time but has experienced more attention since the development of computer science. Many algorithms have been developed to try to solve the problem as efficiently as possible, and it remains a point of fascination for many computer scientists. Discover how the problem is set up and common approaches to solving it in the rest of this article.

What Is the N-Queen Problem?

In a nutshell, the N-Queen Problem is a chess problem. The objective is to find all possible solutions for placing N number of queens on an N x N chessboard so that none of the queens can attack (or “clash”) with each other. Because queens can move in all possible directions, i.e. diagonally and orthogonally, this is a fairly complicated and intriguing problem to solve.

The origins of this well-studied problem are debated, but similar puzzles have been detailed as early as the 8th century. The current problem as we know it, however, became popular after the 19th century. Since the advent of computer science in the 70s, the problem has gained traction, and many algorithms have been designed in an attempt to solve the problem most optimally.

How Is the N-Queen Problem Solved?

Over the years, a lot of methods for solving the problem have been devised. The simplest, but most inefficient, approach is the brute force approach. This is where you simply go through all possible configurations on the board until you find all the solutions. Unsurprisingly, this is very impractical, especially for particularly large values of N. More popular techniques are the backtracking approach, minimum conflicts approach, genetic algorithm, constraint satisfaction, and symmetry reduction. We will cover these next.

Backtracking

Using a simple backtracking approach, the algorithm works by placing the first queen in the first row and column, and recursively exploring other rows and columns to find valid solutions. If a queen is placed and it violates the constraints of the problem, then the algorithm backtracks to the previous step and tries another position. This continues until all possible configurations have been tried and valid solutions have been found.

As an example, take a 4 x 4 chessboard, where we wish to place 4 queens. We can begin by placing a queen in the first row and column, which is fairly customary. This gives us constraints on the placement of the second queen, as can be seen in the illustration. Q represents a queen, and X represents a space where we can’t place a queen, i.e. where a violation would occur.

First placement for first queen in N-Queen Problem
Placing the first queen.

Next, we need to place our second queen. To begin with, we may place it in the first square we have available as such:

Placing the second queen in the N-Queen Problem
The second queen is placed, but we can’t proceed further.

This gives us further constraints. We can see that it’s impossible to place the third queen. Therefore, we must backtrack to the previous step.

We could proceed by choosing the next position for the second queen, but there’s no way to place the other queens without causing a violation. So, we must backtrack again, this time to the first placement.

It’s good to note that we’ve also learned that no solution here will involve a queen in a corner placement. Although we’ve only tried one corner, since the board is square, all corners are equivalent.

Finding a Solution

On our second try, let’s try moving the first queen down by one square. This gives us only one possibility for the second queen, as such:

Second attempt at N-Queen Problem
Alternative placements for first and second queens.

Likewise, we only have one possible position for the third queen. Placing it gives the following grid:

Third placement for second attempt at N-Queen Problem
Placing the third queen in our second attempt.

Yet again, we only have one choice for the fourth queen, which will give us our final grid as seen below.

First solution found in N-Queen Problem
We have found the first solution.

Luckily, we’ve been successful. We have placed all queens with no violations. Therefore, we can consider this a valid solution to the problem and can store it in our list of solutions.

Implementation

That example illustrates the basic idea behind backtracking. Now, it’s time to see how we can implement this approach using code. Consider this simple Python code for a 4 x 4 chessboard:

def solve_n_queens(n):
    def backtrack(row, queens):
        if row == n:
            solutions.append(queens)
        else:
            for col in range(n):
                if all(col != queens[j] and
                       col - queens[j] != row - j and
                       col - queens[j] != j - row
                       for j in range(row)):
                    backtrack(row + 1, queens + [col])

    solutions = []
    backtrack(0, [])
    return solutions


n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    print(solution)

Explanation of Code

Firstly, we define the “solve_n_queens” function, which takes “n” as input. The “backtrack” function is defined second, which takes “row” and “queens” as parameters. The queens list stores the positions of placed queens. A DFS algorithm is used to explore the space on the board. We also use an if statement here, to check if the current row is equal to the row number. If so, then all queens have been placed, and the solution is added to the “solutions” list.

Otherwise, as indicated by the else statement, we need to explore more solutions. A for loop is initiated to iterate over each column, checking the placement. If a violation occurs, backtracking is used, and a queen is placed in the next row.

Lastly, the code creates a solutions list, assigns the value of 4 to n, and then calls the function to solve the problem. Each solution is printed, as can be seen in the image. The results are given as arrays, where each value represents the index of each row, beginning at 0.

Simple backtracking approach to N-Queen Problem
Backtracking approach to N-Queen Problem.

Minimum Conflicts

The minimum conflicts approach is an example of a local search technique, since it relies on improving the solution by making changes to local variables. The general idea is to start by randomly placing queens in columns, and then select the queen with the maximum number of conflicts, or violations. We then move this queen to the position that minimizes these conflicts. This process is repeated for each queen, minimizing conflicts until a solution is found. 

Implementation

Continuing with our n = 4 example, we can use minimum conflicts in Python as follows:

import random

def initialize_board(n):
    board = list(range(n))
    random.shuffle(board)
    return board

def count_conflicts(board, row, col):
    conflicts = 0
    for i in range(row):
        if board[i] == col or board[i] - col == i - row or board[i] - col == row - i:
            conflicts += 1
    return conflicts

def min_conflicts(board, n, max_iter):
    for _ in range(max_iter):
        conflicts = [count_conflicts(board, row, col) for row, col in enumerate(board)]
        if sum(conflicts) == 0:
            return board
        row = random.choice([i for i, c in enumerate(conflicts) if c > 0])
        min_conflicts = float('inf')
        min_col = -1
        for col in range(n):
            if col != board[row]:
                conflicts = count_conflicts(board, row, col)
                if conflicts < min_conflicts:
                    min_conflicts = conflicts
                    min_col = col
        board[row] = min_col
    return None

def print_solution(board):
    n = len(board)
    for i in range(n):
        row = ['.'] * n
        row[board[i]] = 'Q'
        print(' '.join(row))

n = 4
max_iter = 1000

board = initialize_board(n)
solution = min_conflicts(board, n, max_iter)
if solution:
    print_solution(solution)
else:
    print("No solution found.")

Explanation of Code

Since we need to generate our starting positions randomly, we must import the “random” module. We then initialize the board, randomly shuffle the positions, and receive the configuration.

Next, we define the “count_conflicts()” function, which takes “board”, “row” and “col” as parameters. The conflicts are counted for each position by iterating over the board and checking if queens violate the current position. Each time a conflict is found, the count is incremented by 1.

We then define the “min_conflicts()” function for implementing the algorithm. As well as the configuration, it takes the size, “n”, and maximum iterations, “max_iter”, as inputs. If no conflicts are found, the configuration is returned as a solution. Otherwise, we select a random row and iterate over each column, calculating the conflicts to find the minimum. The configuration is then updated to reflect this change, and the process is repeated until a solution is reached or the maximum number of iterations has been performed.

To finish, the “print()” function is defined, which prints the results in a grid format, where “.” indicates a space and “Q” indicates a queen placement. N and max_iter are then declared, followed by instructions for initializing the board and printing the solutions. We can see the solution reached in the image.

Minimum conflicts approach to N-Queen Problem
Minimum conflicts algorithm for a 4-Queen Problem.

It’s worth mentioning that, while minimum conflicts is efficient for large board sizes, it may not find the most optimal solution or even all of the possible solutions. Depending on the search path and original placement, it may miss some solutions. This can also occur due to solutions being symmetrical, which is true in the case of n = 4. Whereas we obtained both solutions using the backtracking approach, we only receive one using the minimum conflicts approach, since they’re symmetrical.

Genetic

A rather novel approach to the problem is by using genetic algorithms, mimicking the process of natural selection. We begin with all possible configurations, with queens in different positions. We evaluate each configuration according to its “fitness”, meaning its number of conflicts. Configurations with higher fitness are then selected, much like with natural selection. After this, two approaches are generally used: crossover and mutation. In genetics, these involve combining genetic materials from the parents or introducing a random mutation, respectively. For the N-Queen Problem, crossover involves combining two configurations so that we produce new combinations, with each queen placement being inherited from one parent like chromosomes are genetically. Mutation involves introducing a random placement, which can be useful for exploring the space.

Implementation

We can gain a better understanding of how this works by considering the following genetic approach in Python.

import random

def initialize_population(population_size, n):
    population = []
    for _ in range(population_size):
        board = list(range(n))
        random.shuffle(board)
        population.append(board)
    return population

def count_conflicts(board):
    n = len(board)
    conflicts = 0
    for i in range(n):
        for j in range(i + 1, n):
            if board[i] == board[j] or abs(board[i] - board[j]) == abs(i - j):
                conflicts += 1
    return conflicts

def selection(population, fitness):
    selected = random.choices(population, weights=fitness, k=2)
    return selected[0], selected[1]

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

def mutation(individual):
    n = len(individual)
    index = random.randint(0, n - 1)
    new_position = random.randint(0, n - 1)
    individual[index] = new_position
    return individual

def genetic_algorithm(population_size, n, max_generations):
    population = initialize_population(population_size, n)

    for generation in range(max_generations):
        fitness = [1 / (count_conflicts(board) + 1) for board in population]

        if 1 in fitness:
            index = fitness.index(1)
            return population[index]

        new_population = []
        for _ in range(population_size // 2):
            parent1, parent2 = selection(population, fitness)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutation(child1)
            child2 = mutation(child2)
            new_population.extend([child1, child2])

        population = new_population

    return None

def print_solution(board):
    n = len(board)
    for i in range(n):
        row = ['.'] * n
        row[board[i]] = 'Q'
        print(' '.join(row))

n = 4
population_size = 100
max_generations = 1000

solution = genetic_algorithm(population_size, n, max_generations)
if solution:
    print_solution(solution)
else:
    print("No solution found.")

Explanation of Code

As before, we import the “random” module. We then define the “initialize_population()” function, taking the “population_size” and “n” parameters. This returns the population of possible configurations.

Next, we create a “population” list to store this population, then initiate a for loop to create the configurations, adding them to the list. After, we define the “count_conflicts()” function as before, to count the conflicts.

The next step is to define the “selection()” function, which selects parents based on fitness. Parents with higher fitness have a greater possibility of being chosen.

The “crossover()” function is defined after this, which takes two parents as input and performs the crossover. The child is created by taking the genetic material from the first parent up to the chosen crossover point, and the remaining material from the other parent.

We define the “mutation()” function next, which randomly selects a position for a queen. The next function to be defined is the “genetic_algorithm()” function, which calculates the fitness for each configuration. If a perfect solution is found, it’s returned.

Another list, “new_population” is created to store the new population after the genetic functions have been performed. Each genetic function is called, and the children are added to the new population. Similar to before, the print function is used to print the results as a board configuration. We can see we’ve received the same result in the images.

First photo of genetics approach to N-Queen Problem
First part of genetics approach to the 4-Queen Problem.
Second photo of genetics approach to N-Queen Problem
Second part of the genetics approach to the 4-Queen Problem.

How Can We Optimize Our Approach to the N-Queen Problem?

There are various ways to optimize our technique for solving the problem. Some major techniques are symmetry reduction and constraint propagation. We’ll cover these next.

Constraint Propagation

This is a technique that aims to reduce our searchable space by taking advantage of the constraints. Since we know we can’t have any queens clashing with each other, we can eliminate potential conflicts early. One such example is forward checking, which is often used in conjunction with backtracking. Forward checking works by looking ahead to check that a placement allows for valid future placements. If not, this configuration is removed early on to improve the efficiency of the algorithm.

Implementation

We can modify our example from earlier to incorporate forward checking as follows:

def solve_n_queens(n):
    def backtrack(row, queens, domains):
        if row == n:
            solutions.append(queens)
        else:
            for col in range(n):
                if is_valid(row, col, queens, domains):
                    updated_domains = update_domains(row, col, queens, domains)
                    backtrack(row + 1, queens + [col], updated_domains)

    def is_valid(row, col, queens, domains):
        for i in range(row):
            if queens[i] == col or abs(queens[i] - col) == abs(i - row):
                return False
        return True

    def update_domains(row, col, queens, domains):
        updated_domains = domains.copy()
        for i in range(row + 1, n):
            updated_domains[i] = updated_domains[i] - {col, col - (i - row), col + (i - row)}
        return updated_domains

    solutions = []
    initial_domains = [set(range(n)) for _ in range(n)]
    backtrack(0, [], initial_domains)
    return solutions


n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    print(solution)

Explanation of Code

The main difference here is that we include the “domain” parameter in the backtrack function, which allows us to update the domains, which represent the valid options for queen placement. The “update_domains()” function is used to remove conflicting configurations.

Backtrack approach with forward checking
Forward checking is used to optimize the backtracking approach.

Symmetry Reduction

Symmetry reduction can be used to make many N Queen algorithms more efficient in solving the problem. The basic principle is that, by accounting for symmetries, we can avoid duplicate solutions and thus make the process more efficient. We can reduce symmetrical rows, columns, and diagonals to single representations, minimizing the space we have to search over.

Implementation

We can incorporate this technique into our backtracking example by including the following code:

    reduced_solutions = []
    for solution in solutions:
        symmetrical_solutions = get_symmetrical_solutions(solution)
        is_unique = True
        for sym_solution in symmetrical_solutions:
            if sym_solution in reduced_solutions:
                is_unique = False
                break
        if is_unique:
            reduced_solutions.append(solution)

    return reduced_solutions

def get_symmetrical_solutions(solution):
    n = len(solution)
    symmetrical_solutions = []

    symmetrical_solutions.append(tuple(solution))

    return symmetrical_solutions

Explanation of Code

To start, we create an empty list, “reduced_solutions”, to store the solutions. The for loop iterates over each solution and the “get_symmetrical_solutions()” function is called to return symmetrical solutions of the current solution. We then check if this solution is unique, and if not, it’s removed from the list to reduce the number of solutions. To finish, we return the symmetry-free solutions and define the get function previously described. We can see in the image that we’ve only received 1 solution this time, which is correct since both of the possible solutions are symmetrical.

Symmetry reduction used with backtracking approach
Symmetry reduction used with the backtracking approach.

Wrapping Up

We’ve covered several popular approaches to the N-Queen Problem here, as well as some optimization methods. The problem remains an interesting puzzle, and algorithms are constantly being improved to try to solve the problem more easily, as well as to try to calculate the number of solutions for a given board. N-Queen provides a fantastic opportunity for improving approaches to constraint satisfaction challenges and serves as an analogy to real-world configuration and scheduling problems.

Summary Table

MethodDescription
BacktrackingRecursive exploration of rows and columns, backtracks when a violation occurs.
Minimum ConflictsLocal search technique, minimizes conflicts by moving queens to positions with fewer violations.
Genetic AlgorithmMimics natural selection, combines and mutates configurations to find solutions.
Constraint PropagationReduces searchable space by taking advantage of constraints, e.g., forward checking.
Symmetry ReductionAccounts for symmetries to avoid duplicate solutions and improve efficiency.

Frequently Asked Questions

What is the N-Queen problem?

The N-Queen problem is a puzzle that demands we place N queens on an N x N board where they can’t attack each other.

What possible solutions are there?

There are many solutions, which increase drastically in number as board size increases. This is known as a combinatorial problem, and no algorithms currently exist to determine a solution number for a given n accurately.

What approaches are there to solve the problem?

Common techniques include backtracking, genetic algorithms, the minimum conflicts approach, and constraint satisfaction.

How can we optimize our approach?

By using constraint propagation, such as forward checking and symmetry reduction, we can reduce computation time. The problem can also be parallelized, meaning the search space is shared among multiple threads to speed up the process.

What applications does the problem have?

The problem is mostly used as a benchmark for algorithm performance, but also has applications in scheduling, DNA sequencing, and resource allocation.

To top