Printing all solutions in N-Queen Problem

Last Updated : 12 Feb, 2025

Given an integer n, the task is to find all distinct solutions to the n-queens
problem, where n queens are placed on an n * n chessboard such that no two
queens can attack each other.

Note: Each solution is a unique configuration of n queens, represented as a

permutation of [1,2,3,....,n]. The number at the ith position indicates the row of the
queen in the ith column. For example, [3,1,4,2] shows one such layout.

Example:

Input: n = 4
Output: [2, 4, 1, 3], [3, 1, 4, 2]

Explanation : These are the 2 possible solutions.

Input: n = 2
Output: []
Explanation: No solution, as queens can attack each other in all possible
configurations.

Table of Content
[Naive Approach] By Generating all Permutations using Recursion
[Expected Approach] Using Backtracking with Pruning

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 [Alternate Approach] Backtracking Using Bit-masking

[Naive Approach] - Using Recursion - O(n! * n) Time and O(n) Space

A simple idea to solve the N-Queens problem is to generate all possible

permutations of [1, 2, 3, ..., n] and then check if it represents a valid N-
Queens configuration. Since each queen has to be in a different row and
column, using permutations automatically takes care of those rules. But we
still need to check that no two queens are on the same diagonal.

Below is given the implementation:

C++ Java Python C# JavaScript

1 //C++ program to find all solution of N queen problem

2 //using recursion
3 #include <iostream>
4 #include<vector>
5 #include<algorithm>
6 using namespace std;
7
8 // Function to check if the current placement is safe
9 bool isSafe(vector<int>& board, int currRow,
10 int currCol) {
11
12 // Check all previously placed queens
13 for(int i = 0; i < board.size(); ++i) {
14 int placedRow = board[i];
15
16 // Columns are 1-based
17 int placedCol = i + 1;
18
19 // Check if the queen is on the same diagonal
20 if(abs(placedRow - currRow) == abs(placedCol -
currCol)) {
21 return false; // Not safe
22 }
23 }
24
25 // Safe to place the queen
26 return true;

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
27 }
28
29 // Recursive function to generate all possible permutations
30 void nQueenUtil(int col, int n, vector<int>& board,
31 vector<vector<int>>& res, vector<bool>& visited) {
32
33 // If all queens are placed, add into res
34 if(col > n) {
35 res.push_back(board);
36 return;
37 }
38
39 // Try placing a queen in each row
40 // of the current column
41 for(int row = 1; row <= n; ++row) {
42
43 // Check if the row is already used
44 if(!visited[row]) {
45
46 // Check if it's safe to place the queen
47 if(isSafe(board, row, col)) {
48
49 // Mark the row as used
50 visited[row] = true;
51
52 // Place the queen
53 board.push_back(row);
54
55 // Recur to place the next queen
56 nQueenUtil(col + 1, n, board,
57 res, visited);
58
59 // Backtrack: remove the queen
60 board.pop_back();
61
62 // Unmark row
63 visited[row] = false;
64 }
65 }
66 }
67 }
68

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
69 // Main function to find all distinct
70 // res to the n-queens puzzle
71 vector<vector<int>> nQueen(int n) {
72 vector<vector<int>> res;
73
74 // Current board configuration
75 vector<int> board;
76
77 // Track used rows
78 vector<bool> visited(n + 1, false);
79
80 // Start solving from the first column
81 nQueenUtil(1, n, board, res, visited);
82 return res;
83 }
84
85 int main() {
86 int n = 4;
87 vector<vector<int>> res = nQueen(n);
88
89 for(int i = 0;i < res.size(); i++) {
90 cout << "[";
91 for(int j = 0; j < n; ++j) {
92 cout << res[i][j];
93 if(j != n - 1) cout << " ";
94 }
95 cout << "]\n";
96 }
97 return 0;
98 }

Output

[2 4 1 3]
[3 1 4 2]

Time Complexity: O(n!*n), n! for generating all permutations and O(n) for
validation of each permutation.
Auxiliary Space: O(n)

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
[Expected Approach] - Using Backtracking with Pruning - O(n!) Time and
O(n) Space

To optimise the above approach, we can use backtracking with pruning.

Instead of generating all possible permutations, we build the solution
incrementally, while doing this we can make sure at each step that the partial
solution remains valid. If a conflict occur then we'll backtrack immediately,
this helps in avoiding unnecessary computations.

Step-by-step implementation:

Start from the first column and try placing a queen in each row.
Keep arrays to track which rows are already occupied. Similarly, for tracking
major and minor diagonals are already occupied.
If a queen placement conflicts with existing queens, skip that row and
backtrack the queen to try the next possible row (Prune and backtrack during
conflict).

C++ Java Python C# JavaScript

1 // C++ program to find all solution of N queen problem by

2 // using backtracking and pruning
3
4 #include <algorithm>
5 #include <iostream>
6 #include <vector>
7
8 using namespace std;
9
10 // Utility function for solving the N-Queens
11 // problem using backtracking.
12 void nQueenUtil(int j, int n, vector<int> &board, vector<bool>
&rows,
13 vector<bool> &diag1, vector<bool> &diag2,
vector<vector<int>> &res) {
14
15 if (j > n) {
16 // A solution is found
17 res.push_back(board);
18 return;

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
19 }
20 for (int i = 1; i <= n; ++i) {
21 if (!rows[i] && !diag1[i + j] && !diag2[i - j + n]) {
22
23 // Place queen
24 rows[i] = diag1[i + j] = diag2[i - j + n] = true;
25 board.push_back(i);
26
27 // Recurse to the next column
28 nQueenUtil(j + 1, n, board, rows, diag1, diag2,
res);
29
30 // Remove queen (backtrack)
31 board.pop_back();
32 rows[i] = diag1[i + j] = diag2[i - j + n] = false;
33 }
34 }
35 }
36
37 // Solves the N-Queens problem and returns
38 // all valid configurations.
39 vector<vector<int>> nQueen(int n) {
40 vector<vector<int>> res;
41 vector<int> board;
42
43 // Rows occupied
44 vector<bool> rows(n + 1, false);
45
46 // Major diagonals (row + j) and Minor diagonals (row - col
+ n)
47 vector<bool> diag1(2 * n + 1, false);
48 vector<bool> diag2(2 * n + 1, false);
49
50 // Start solving from the first column
51 nQueenUtil(1, n, board, rows, diag1, diag2, res);
52 return res;
53 }
54
55 int main() {
56 int n = 4;
57 vector<vector<int>> res = nQueen(n);
58

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
59 for (int i = 0; i < res.size(); i++) {
60 cout << "[";
61 for (int j = 0; j < n; ++j) {
62 cout << res[i][j];
63 if (j != n - 1)
64 cout << " ";
65 }
66 cout << "]\n";
67 }
68 return 0;
69 }

Output

[2 4 1 3]
[3 1 4 2]

Time complexity: O(n!) For generating all permutations.

Auxiliary Space: O(n)

[Alternate Approach] - Backtracking Using Bit-masking

To further optimise the backtracking approach, especially for larger values of

n, we can use bit-masking to efficiently track occupied rows and diagonals.
Bit-masking lets us to use integers (rows, ld, rd) to track which rows and
diagonals are occupied, making use of fast bitwise operations for quicker
calculations. The approach remains the same as above.

Below is given the implementation:

C++ Java Python C# JavaScript

1 //C++ program to find all solution of N queen problem

2 //using recursion
3 #include <iostream>
4 #include <vector>
5 using namespace std;
6
7 // Function to check if the current placement is safe

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 8 bool isSafe(int row, int col, int rows, int ld, int rd, int n)
{
9 return !((rows >> row) & 1) && !((ld >> (row + col)) & 1)
&& !((rd >> (row - col + n)) & 1);
10 }
11
12 // Recursive function to generate all possible permutations
13 void nQueenUtil(int col, int n, vector<int>& board,
14 vector<vector<int>>& res, int rows, int ld, int rd) {
15
16 // If all queens are placed, add into res
17 if(col > n) {
18 res.push_back(board);
19 return;
20 }
21
22 // Try placing a queen in each row
23 // of the current column
24 for(int row = 1; row <= n; ++row) {
25
26 // Check if it's safe to place the queen
27 if(isSafe(row, col, rows, ld, rd, n)) {
28
29 // Place the queen
30 board.push_back(row);
31
32 // Recur to place the next queen
33 nQueenUtil(col + 1, n, board,
34 res, rows | (1 << row),
35 (ld | (1 << (row + col))),
36 (rd | (1 << (row - col + n))));
37
38 // Backtrack: remove the queen
39 board.pop_back();
40 }
41 }
42
43 }
44
45 // Main function to find all distinct
46 // res to the n-queens puzzle
47 vector<vector<int>> nQueen(int n) {

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
48 vector<vector<int>> res;
49
50 // Current board configuration
51 vector<int> board;
52
53 // Start solving from the first column
54 nQueenUtil(1, n, board, res, 0, 0, 0);
55 return res;
56 }
57
58 int main() {
59 int n = 4;
60 vector<vector<int>> res = nQueen(n);
61
62 for(int i = 0;i < res.size(); i++) {
63 cout << "[";
64 for(int j = 0; j < n; ++j) {
65 cout << res[i][j];
66 if(j != n - 1) cout << " ";
67 }
68 cout << "]\n";
69 }
70 return 0;
71 }

Output

[2 4 1 3]
[3 1 4 2]

Time Complexity: O(n!), for generating all permutations.

Space Complexity: O(n)

N-Queens Problem Visit Course

Comment More info Advertise with us Next Article

Minimum queens required to cover all
the squares of a chess board

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Similar Reads
N Queen Problem
Given an integer n, the task is to find the solution to the n-queens problem, where n queens are
placed on an n*n chessboard such that no two queens can attack each other. The N Queen is the…
   à Â
15+ min read

N-Queen in Different languages

4 Queens Problem
The 4 Queens Problem consists in placing four queens on a 4 x 4 chessboard so that no two queens
attack each other. That is, no two queens are allowed to be placed on the same row, the same column o…

15 min read

8 queen problem
Given an 8x8 chessboard, the task is to place 8 queens on the board such that no 2 queens threaten each
other. Return a matrix of size 8x8, where 1 represents queen and 0 represents an empty position.…

9 min read

N Queen Problem using Branch And Bound

The N queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two
queens threaten each other. Thus, a solution requires that no two queens share the same row, column, o…

15+ min read

N Queen in O(n) space

Given an integer n, the task is to find the solution to the n-queens problem, where n queens are placed on
an n*n chessboard such that no two queens can attack each other.The N Queen is the problem of placin…
Ã
7 min read

Printing all solutions in N-Queen Problem

Given an integer n, the task is to find all distinct solutions to the n-queens problem, where n queens are
placed on an n * n chessboard such that no two queens can attack each other. Note: Each solution is a…

15+ min read

Minimum queens required to cover all the squares of a chess board

Given the dimension of a chess board (N x M), determine the minimum number of queens required to
cover all the squares of the board. A queen can attack any square along its row, column or diagonals.…

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 14 min read
Number of cells a queen can move with obstacles on the chessboard
Consider a N X N chessboard with a Queen and K obstacles. The Queen cannot pass through obstacles.
Given the position (x, y) of Queen, the task is to find the number of cells the queen can move. Examples:…

15+ min read

N-Queen Problem | Local Search using Hill climbing with random neighbour
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 8 Queen problem. Input: N = 4 Output: 0 1…

15+ min read

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF