how do you solve n queen problem

• DSA for Beginners
• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching
• Write an Interview Experience
• Share Your Campus Experience

N Queen Problem | Backtracking-3

N-queen in different languages.

• Java Program for N Queen Problem | Backtracking-3
• Python Program for N Queen Problem | Backtracking-3
• C Program for N Queen Problem | Backtracking-3
• 4 Queens Problem
• 8 queen problem
• N Queen Problem using Branch And Bound
• N Queen in O(n) space
• Printing all solutions in N-Queen Problem
• Minimum queens required to cover all the squares of a chess board
• Number of cells a queen can move with obstacles on the chessboard
• N-Queen Problem | Local Search using Hill climbing with random neighbour
• Discuss(40+)

We have discussed Knight’s tour and Rat in a Maze problem earlier as examples of Backtracking problems. Let us discuss N Queen as another example problem that can be solved using backtracking. 

N-Queen Problem:

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, the following is a solution for the 4 Queen problem.

Solution for 4-Queen problem

The expected output is in the form of a matrix that has ‘ Q ‘s for the blocks where queens are placed and the empty spaces are represented by ‘.’ . For example, the following is the output matrix for the above 4-Queen solution.

. . Q .  Q . . .  . . . Q  . Q . . 

Naive Algorithm: Generate all possible configurations of queens on board and print a configuration that satisfies the given constraints.

while there are untried configurations {     generate the next configuration     if queens don’t attack in this configuration then     {         print this configuration;     } }

Time Complexity: O( N*N C N ) Auxiliary Space: O(N 2 )

Algorithm for N queen problem:

Following is the backtracking algorithm for solving the N-Queen problem

• Initialize an empty chessboard of size NxN.
• Start with the leftmost column and place a queen in the first row of that column.
• Move to the next column and place a queen in the first row of that column.
• Repeat step 3 until either all N queens have been placed or it is impossible to place a queen in the current column without violating the rules of the problem.
• If all N queens have been placed, print the solution.
• If it is not possible to place a queen in the current column without violating the rules of the problem, backtrack to the previous column.
• Remove the queen from the previous column and move it down one row.
• Repeat steps 4-7 until all possible configurations have been tried.

Pseudo-code implementation:

function solveNQueens(board, col, n):     if col >= n:         print board         return true     for row from 0 to n-1:         if isSafe(board, row, col, n):             board[row][col] = 1             if solveNQueens(board, col+1, n):                 return true             board[row][col] = 0     return false function isSafe(board, row, col, n):     for i from 0 to col-1:       if board[row][i] == 1:           return false     for i,j from row-1, col-1 to 0, 0 by -1:         if board[i][j] == 1:             return false     for i,j from row+1, col-1 to n-1, 0 by 1, -1:         if board[i][j] == 1:             return false     return true board = empty NxN chessboard solveNQueens(board, 0, N)

Backtracking Algorithm by placing queens in columns:

The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.

Follow the steps mentioned below to implement the idea:

• Start in the leftmost column
• If all queens are placed return true
• Then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.
• If placing the queen in [row, column] leads to a solution then return true.
• If placing queen doesn’t lead to a solution then unmark this [row, column] and track back and try other rows.
• If all rows have been tried and nothing worked return false to trigger backtracking.

Implementation of the above backtracking solution:

Time Complexity: O(N!) Auxiliary Space: O(N 2 )

Backtracking Algorithm by placing queens in rows:

The idea is to place queens one by one in different rows, starting from the topmost row. When we place a queen in a row, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.

• Make a recursive function that takes the state of the board and the current row number as its parameter.
• Start in the topmost row.
• If placing queen doesn’t lead to a solution then unmark this [row, column] and track back and try other columns.
• If all columns have been tried and nothing worked return false to trigger backtracking.

Below is the implementation of the above Backtracking solution:

Optimization in is_safe() function:

The idea is not to check every element in the right and left diagonal, instead use the property of diagonals:  The sum of i and j is constant and unique for each right diagonal, where i is the row of elements and j is the  column of elements.  The difference between i and j is constant and unique for each left diagonal, where i and j are row and column of element respectively.

Below is the implementation of the Backtracking solution(with optimization):

Time Complexity: O(N!)  Auxiliary Space: O(N)

Related Articles:

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.  

Please Login to comment...

• Shivam.Pradhan
• AniruddhaPandey
• ankita_saini
• harminder3027
• princi singh
• SHUBHAMSINGH10
• sahurasmita409
• adityakumar129
• devendrasalunke
• jaysheth5290
• sagartomar9927
• namananand891
• shinjanpatra
• meena13091999
• surajrasr7277
• user_7gr9iodclfx
• prajwalkandekar123
• laxmishinde5t82
• jaykush9161
• chessboard-problems
• MAQ Software

Improve your Coding Skills with Practice

PrepBytes Blog

ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING

Sign in to your account

Forgot your password?

Login via OTP

We will send you an one time password on your mobile number

An OTP has been sent to your mobile number please verify it below

Register with PrepBytes

How do you solve the n queen problem.

Last Updated on July 20, 2023 by Mayank Dham

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. The process is repeated until all N queens are placed on the board without conflict, or until all possible solutions are exhausted. The resulting board is a correct solution to the N queen problem.

What is Backtracking?

Backtracking is a problem-solving technique that involves recursively trying out different solutions to a problem, and backtracking or undoing previous choices when they don’t lead to a valid solution. It is commonly used in algorithms that search for all possible solutions to a problem, such as the famous eight-queens puzzle. Backtracking is a powerful and versatile technique that can be used to solve a wide range of problems.

Backtracking is often used in constraint satisfaction problems, such as the N Queen problem, where we need to find a solution that satisfies a set of constraints. In these problems, we start by choosing a value for one of the variables and checking if it satisfies the constraints. If it does, we move on to the next variable and repeat the process. If the current value does not satisfy the constraints, we backtrack to the previous variable and try a different value.

Backtracking is an effective technique for solving problems, as it allows us to incrementally build a solution and avoids the need to consider all possible solutions from scratch. However, it can also be time-consuming, as it requires many iterations and checks. To make backtracking more efficient, various optimization techniques, such as constraint propagation and heuristics, can be used.

What is N Queen Problem Algorithm?

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. The problem has a long history and practical applications in scheduling, data encryption, and pattern recognition.

For example, the two possible solutions to the 4 Queen problem are shown below:

The N Queen problem can be solved by using various approaches, such as brute force, backtracking, and genetic algorithms. Backtracking is one of the popular approaches for solving the N Queen problem, and it is simple to implement and can be made more efficient with optimization techniques.

N-Queen Algorithm

The complete algorithm for the N queen problem is discussed below :

• Start in the leftmost column
• If all queens are placed, return true
• Try all rows in the current column. For each row:
• a. If the queen can be placed safely in this row, mark this cell and recursively try placing the rest of the queen
• b. If placing the queen in this row leads to an unsafe configuration, unmark the cell and try the next row
• If all rows have been tried and nothing worked, return false to trigger backtracking

Approaches to Solve N Queen Problem

Below we have discussed approaches to solve the N Queen Problem

Approach 1: Naive Approach to Solve N Queen Problem

In this approach, we generate all possible queen configurations on board and print a configuration that satisfies the given constraints.

Below is the pseudo-code for Naive Approach

Approach 2: Solving N Queen Problem using backtracking

By using backtracking we position queens in different columns one by one, beginning with the leftmost column. When we position a queen in a column, we look for clashes with other queens that have already been placed. If we locate a row in the current column with no collision, we mark this row and column as part of the solution. We backtrack and return false if we cannot discover such a row due to clashes.

Algorithm: Here’s an algorithm to solve the n queen problem:

• Start with an empty chessboard of size n x n.
• Place the first queen in the top-left corner of the board (i.e., row 1, column 1).
• Move to the next row and try to place a queen in each column until a valid position is found or all columns have been tried.
• If a valid position is found, move to the next row and repeat step 3.
• If all columns have been tried in the current row without finding a valid position, backtrack to the previous row and move the queen to the next column in that row. Repeat step 3.
• If all rows have been tried without finding a solution, backtrack to the previous row and move the queen to the next column in that row. Repeat step 3.
• If a solution is found, print the positions of the queens on the board and exit the program.

Time Complexity: O(N * N!) Space Complexity: O(N^2)

Dry Run of Approach 2 N Queen Problem Let’s do a dry run of the N Queen problem for N=4

• Place the queen in the leftmost column.

• Place the second queen in the second column such that it cannot attack the queen in the first column.

Place the third queen in the third column so that it cannot attack the queen in the first two columns. No such placement is possible, so backtrack to the second column.

Place the second queen in another safe cell in the second column.

• Place the third queen in a safe cell in the third column.

Place the fourth queen in the adjacent columns so that it cannot attack the queen in the first three columns. No such placement is possible, so backtrack to the third column.

Place the third queen in another safe cell in the third column. There is no other safe cell for the queen in column 3, so backtrack.

There is no other safe cell for the queen in column 2, so backtrack to the first column.

Place the first queen in the next safe cell in the first column.

• Place the second queen in a safe cell in the second column.

Place the fourth queen in a safe cell in the fourth column.

Finally, we have our solution!

Approach 3: Backtracking with optimization

The reason behind the N queen problem approach is that instead of checking every element in the right and left diagonals, we can use the property of diagonals:

• For each right diagonal, the sum of I and j is constant and unique, where i represents row and j represents a column in the chess board.
• The difference between i and j is constant and unique for each left diagonal, where i and j represent the row and column of the chess board, respectively.

Time Complexity: O(N * N!) Space Complexity: O(N)

Conclusion The N queen problem is a difficult one that can be solved with a backtracking algorithm. The problem necessitates careful consideration of the rules governing queen placement on a chessboard, and the backtracking algorithm provides an efficient method of searching for all possible solutions. The N queen problem has real-world applications in computer vision, where it can be used to solve problems like object recognition and tracking. As a result, knowing how to solve the N queen problem using backtracking is a valuable skill for any programmer.

FAQs(Frequently Asked Questions) on N Queen Problem

Here are some frequently asked questions (FAQs) and their answers on the N Queen problem:

Q1. What is the goal of the N Queen problem? Ans: The goal of the N Queen problem is to find a configuration of the N queens on an NxN chessboard such that no two queens are attacking each other.

Q2. What is a valid solution to the N Queen problem? Ans: A valid solution to the N Queen problem is a configuration of the N queens on an NxN chessboard such that no two queens are in the same row, column, or diagonal.

Q3. What is the brute force approach to solving the N Queen problem? Ans: The brute force approach to solving the N Queen problem involves trying all possible combinations of placing the N queens on the chessboard and checking if each combination satisfies the constraints (i.e., no two queens are in the same row, column, or diagonal).

Q4. What is the backtracking approach to solving the N Queen problem? Ans: The backtracking approach to solving the N Queen problem is a more efficient solution compared to the brute force approach. In this approach, we start by placing the first queen in the first row, then move to the next row and try to place the next queen, and so on. If we reach a point where it is not possible to place a queen, we backtrack and try a different position for the previous queen. We continue this process until we find a valid solution or all possibilities have been exhausted.

Q5. How can I solve the n-Queen problem? Ans: There are several algorithms to solve the n-Queen problem, such as backtracking, genetic algorithms, and simulated annealing. The most common algorithm is backtracking, which involves trying to place queens on the board row by row, backtracking when a conflict is found, and continuing until a solution is found.

Q6. Can the n-Queen problem be solved for all values of n? Ans: The n-Queen problem can be solved for all values of n, but the computational complexity of finding a solution increases rapidly as n increases. For large values of n, it may not be practical to find a solution using a brute-force algorithm.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

• Linked List
• Segment Tree
• Backtracking
• Dynamic Programming
• Greedy Algorithm
• Operating System
• Company Placement
• Interview Tips
• General Interview Questions
• Data Structure
• Other Topics
• Computational Geometry
• Game Theory

Related Post

Backtracking algorithm with example.

• Google OR-Tools
• Bahasa Indonesia
• Español – América Latina
• Português – Brasil
• Tiếng Việt

The N-queens Problem

In the following sections, we'll illustrate constraint programming (CP) by a combinatorial problem based on the game of chess. In chess, a queen can attack horizontally, vertically, and diagonally. The N-queens problem asks:

How can N queens be placed on an NxN chessboard so that no two of them attack each other?

Below, you can see one possible solution to the N-queens problem for N = 4.

No two queens are on the same row, column, or diagonal.

Note that this isn't an optimization problem: we want to find all possible solutions, rather than one optimal solution, which makes it a natural candidate for constraint programming. The following sections describe the CP approach to the N-queens problem, and present programs that solve it using both the CP-SAT solver and the original CP solver.

CP approach to the N-queens problem

A CP solver works by systematically trying all possible assignments of values to the variables in a problem, to find the feasible solutions. In the 4-queens problem, the solver starts at the leftmost column and successively places one queen in each column, at a location that is not attacked by any previously placed queens.

Propagation and backtracking

There are two key elements to a constraint programming search:

• Propagation — Each time the solver assigns a value to a variable, the constraints add restrictions on the possible values of the unassigned variables. These restrictions propagate to future variable assignments. For example, in the 4-queens problem, each time the solver places a queen, it can't place any other queens on the row and diagonals the current queen is on. Propagation can speed up the search significantly by reducing the set of variable values the solver must explore.
• Backtracking occurs when either the solver can't assign a value to the next variable, due to the constraints, or it finds a solution. In either case, the solver backtracks to a previous stage and changes the value of the variable at that stage to a value that hasn't already been tried. In the 4-queens example, this means moving a queen to a new square on the current column.

Next, you'll see how constraint programming uses propagation and backtracking to solve the 4-queens problem.

Let's suppose the solver starts by arbitrarily placing a queen in the upper left corner. That's a hypothesis of sorts; perhaps it will turn out that no solution exists with a queen in the upper left corner.

Given this hypothesis, what constraints can we propagate? One constraint is that there can be only one queen in a column (the gray Xs below), and another constraint prohibits two queens on the same diagonal (the red Xs below).

Our third constraint prohibits queens on the same row:

Our constraints propagated, we can test out another hypothesis, and place a second queen on one of the available remaining squares. Our solver might decide to place in it the first available square in the second column:

After propagating the diagonal constraint, we can see that it leaves no available squares in either the third column or last row:

With no solutions possible at this stage, we need to backtrack. One option is for the solver to choose the other available square in the second column. However, constraint propagation then forces a queen into the second row of the third column, leaving no valid spots for the fourth queen:

And so the solver must backtrack again, this time all the way back to the placement of the first queen. We have now shown that no solution to the queens problem will occupy a corner square.

Since there can be no queen in the corner, the solver moves the first queen down by one, and propagates, leaving only one spot for the second queen:

Propagating again reveals only one spot left for the third queen:

And for the fourth and final queen:

We have our first solution! If we instructed our solver to stop after finding the first solution, it would end here. Otherwise, it would backtrack again and place the first queen in the third row of the first column.

Solution using CP-SAT

The N-queens problem is ideally suited to constraint programming. In this section we'll walk through a short Python program that uses the CP-SAT solver to find all solutions to the problem.

Import the libraries

The following code imports the required library.

Declare the model

The following code declares the CP-SAT model.

Create the variables

The solver's creates the variables for the problem as an array named queens .

Here we assume that queens[j] is the row number for the queen in column j . In other words, queens[j] = i means there is a queen in row i and column j .

Create the constraints

Here's the code that creates the constraints for the problem.

The code uses the AddAllDifferent method, which requires all the elements of a variable array to be different.

Let's see how these constraints guarantee the three conditions for the N-queens problem (queens on different rows, columns, and diagonals).

No two queens on the same row

Applying the solver's AllDifferent method to queens forces the values of queens[j] to be different for each j , which means that all queens must be in different rows.

No two queens on the same column

This constraint is implicit in the definition of queens . Since no two elements of queens can have the same index, no two queens can be in the same column.

No two queens on the same diagonal

The diagonal constraint is a little trickier than the row and column constraints. First, if two queens lie on the same diagonal, one of the following conditions must be true:

• The row number plus the column number for each of the two queens are equal. In other words, queens(j) + j has the same value for two different indices j .
• The row number minus the column number for each of the two queens are equal. In this case, queens(j) - j has the same value for two different indices j .

One of these conditions means the queens lie on the same ascending diagonal ( going from left to right), while the other means they lie on the same descending diagonal. Which condition corresponds to ascending and which to descending depends on how you order the rows and columns. As mentioned in the previous section , the ordering has no effect on the set of solutions, just on how you visualize them.

So the diagonal constraint is that the values of queens(j) + j must all be different, and the values of queens(j) - j must all be different, for different j .

To apply the AddAllDifferent method to queens(j) + j , we put the N instances of the variable, for j from 0 to N-1 , into an array, diag1 , as follows:

Then we apply AddAllDifferent to diag1 .

The constraint for queens(j) - j is created similarly.

Create a solution printer

To print all solutions to the N-queens problem, you need to pass a callback, called a solution printer , to the CP-SAT solver. The callback prints each new solution as the solver finds it. The following code creates a solution printer.

Note that the solution printer must be written as a Python class, due to the Python interface to the underlying C++ solver.

The solutions are printed by the following lines in the solution printer.

In this example, self.__variables is the variable queens , and each v corresponds to one of the eight entries of queens . This prints a solution in the following form: x0 = queens(0) x1 = queens(1) ... x7 = queens(7) where xi is the column number of the queen in row i .

The next section shows an example of a solution.

Call the solver and display the results

The following code runs the solver and displays the solutions.

The program finds 92 different solutions for an 8x8 board. Here's the first one.

You can solve the problem for a board of a different size by passing in N as a command-line argument. For example, if the program is named queens , python nqueens_sat.py 6 solves the problem for a 6x6 board.

The entire program

Here is the entire program for the N-queens program.

Solution using the original CP solver

The following sections present a Python program that solves N-queens using the original CP solver. (However, we recommend using the newer CP-SAT solver )

Declare the solver

The following code declares the original CP solver.

The solver's IntVar method creates the variables for the problem as an array named queens .

For any solution, queens[j] = i means there is a queen in column j and row i .

These constraints guarantee the three conditions for the N-queens problem ( queens on different rows, columns, and diagonals).

The diagonal constraint is a little trickier than the row and column constraints. First, if two queens lie on the same diagonal, one of the following must be true:

• If the diagonal is descending (going from left to right), the row number plus column number for each of the two queens are equal. So queens(i) + i has the same value for two different indices i .
• If the diagonal is ascending, the row number minus the column number for each of the two queens are equal. In this case, queens(i) - i has the same value for two different indices i .

So the diagonal constraint is that the values of queens(i) + i must all be different, and likewise the values of queens(i) - i must all be different, for different i .

The code above adds this constraint by applying the AllDifferent method to queens[j] + j and queens[j] - j , for each i .

Add the decision builder

The next step is to create a decision builder, which sets the search strategy for the problem. The search strategy can have a major impact on the search time, due to propagation of constraints, which reduces the number of variable values the solver has to explore. You have already seen an example of this in the 4-queens example .

The following code creates a decision builder using the solver's Phase method.

See Decision builder for details on the input arguments to the Phase method.

How the decision builder works in the 4-queens example

Let's take a look at how decision builder directs the search in the 4-queens example . The solver begins with queens[0] , the first variable in the array, as directed by CHOOSE_FIRST_UNBOUND . The solver then assigns queens[0] the smallest value that hasn't already been tried, which is 0 at this stage, as directed by ASSIGN_MIN_VALUE . This places the first queen in the upper left corner of the board.

Next, the solver selects queens[1] , which is now the first unbound variable in queens . After propagating the constraints, there are two possible rows for a queen in column 1: row 2 or row 3. The ASSIGN_MIN_VALUE option directs the solver to assign queens[1] = 2 . (If instead, you set IntValueStrategy to ASSIGN_MAX_VALUE , the solver would assign queens[1] = 3 .)

You can check that the rest of the search follows the same rules.

The following code runs the solver and displays the solution.

Here's the first solution found by the program for an 8x8 board.

You can solve the problem for a board of a different size by passing in N as a command-line argument. For example, python nqueens_cp.py 6 solves the problem for a 6x6 board.

The complete program is shown below.

Number of solutions

The number of solutions goes up roughly exponentially with the size of the board:

Many solutions are just rotations of others, and a technique called symmetry breaking can be used to reduce the amount of computation needed. We don't use that here; our solution above isn't intended to be fast, just simple. Of course, we could make it much faster if we wanted to only find one solution instead of all of them: no more than a few milliseconds for board sizes up to 50.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2023-04-11 UTC.