Printing all solutions in N-Queen Problem
Last Updated :
01 Oct, 2024
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.
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: 4
Output: [2, 4, 1, 3 ], [3, 1, 4, 2]
Explaination: These are the 2 possible solutions.
Input: 1
Output: [1]
Explaination: Only one queen can be placed in the single cell available.
Naive Recursive Approach
The most simple way 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.
Steps-by-step approach:
- Generate all possible permutations of [1, 2, 3, …, n] using Use backtracking
- For each permutation, check if any two queens are placed on the same diagonal.
- If a permutation is valid during diagonal check, add it to our result.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to check if the current placement is safe
bool isSafe(const vector<int>& board, int currRow,
int currCol) {
// Check all previously placed queens
for(int i = 0; i < board.size(); ++i) {
int placedRow = board[i];
// Columns are 1-based
int placedCol = i + 1;
// Check if the queen is on the same diagonal
if(abs(placedRow - currRow) ==
abs(placedCol - currCol)) {
return false; // Not safe
}
}
// Safe to place the queen
return true;
}
// Recursive function to generate all possible permutations
void nQueenUtil(int col, int n, vector<int>& board,
vector<vector<int>>& result, vector<bool>& visited) {
// If all queens are placed, add into result
if(col > n) {
result.push_back(board);
return;
}
// Try placing a queen in each row
// of the current column
for(int row = 1; row <= n; ++row) {
// Check if the row is already used
if(!visited[row]) {
// Check if it's safe to place the queen
if(isSafe(board, row, col)) {
// Mark the row as used
visited[row] = true;
// Place the queen
board.push_back(row);
// Recur to place the next queen
nQueenUtil(col + 1, n, board,
result, visited);
// Backtrack: remove the queen
board.pop_back();
visited[row] = false; // Unmark row
}
}
}
}
// Main function to find all distinct
// result to the n-queens puzzle
vector<vector<int>> nQueen(int n) {
vector<vector<int>> result;
// Current board configuration
vector<int> board;
// Track used rows
vector<bool> visited(n + 1, false);
// Start solving from the first column
nQueenUtil(1, n, board, result, visited);
return result;
}
int main() {
int n = 4;
vector<vector<int>> result = nQueen(n);
for(auto &res : result) {
cout << "[";
for(int i = 0; i < n; ++i) {
cout << res[i];
if(i != n - 1) cout << ", ";
}
cout << "]\n";
}
return 0;
}
import java.util.ArrayList;
import java.util.List;
class GfG {
// Check if placement is safe
static boolean isSafe(List<Integer> board,
int currRow, int currCol) {
for(int i = 0; i < board.size(); i++) {
int placedRow = board.get(i);
int placedCol = i + 1;
// Check diagonals
if(Math.abs(placedRow - currRow) ==
Math.abs(placedCol - currCol)) {
return false; // Not safe
}
}
return true; // Safe to place
}
// Recursive utility to solve
static void nQueenUtil(int col, int n,
List<Integer> board,
List<List<Integer>> result,
boolean[] visited) {
// If all queens placed, add to result
if(col > n) {
result.add(new ArrayList<>(board));
return;
}
// Try each row in column
for(int row = 1; row <= n; row++) {
// If row not used
if(!visited[row]) {
// Check safety
if(isSafe(board, row, col)) {
// Mark row
visited[row] = true;
// Place queen
board.add(row);
// Recur for next column
nQueenUtil(col + 1, n, board,
result, visited);
// Backtrack
board.remove(board.size()-1);
visited[row] = false;
}
}
}
}
// Main N-Queen solver
static List<List<Integer>> nQueen(int n) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> board = new ArrayList<>();
boolean[] visited = new boolean[n +1];
nQueenUtil(1, n, board, result, visited);
return result;
}
// Main method
public static void main(String[] args) {
int n = 4;
List<List<Integer>> result = nQueen(n);
for(List<Integer> res : result) {
System.out.print("[");
for(int i = 0; i < res.size(); i++) {
System.out.print(res.get(i));
if(i != res.size()-1)
System.out.print(", ");
}
System.out.println("]");
}
}
}
# Function to check if placement is safe
def is_safe(board, curr_row, curr_col):
for i in range(len(board)):
placed_row = board[i]
placed_col = i + 1
# Check diagonals
if abs(placed_row - curr_row) == \
abs(placed_col - curr_col):
return False # Not safe
return True # Safe to place
# Recursive utility to solve N-Queens
def nqueen_util(col, n, board, result, visited):
# If all queens placed, add to result
if col > n:
result.append(board.copy())
return
# Try each row in column
for row in range(1, n+1):
# If row not used
if not visited[row]:
# Check safety
if is_safe(board, row, col):
# Mark row
visited[row] = True
# Place queen
board.append(row)
# Recur for next column
nqueen_util(col+1, n, board, result, visited)
# Backtrack
board.pop()
visited[row] = False
# Main N-Queen solver
def nqueen(n):
result = []
board = []
visited = [False] * (n +1)
nqueen_util(1, n, board, result, visited)
return result
# Main function
if __name__ == "__main__":
n = 4
result = nqueen(n)
for res in result:
print("[", end="")
for i in range(len(res)):
print(res[i], end="")
if i != len(res)-1:
print(", ", end="")
print("]")
using System;
using System.Collections.Generic;
class GfG {
// Check if placement is safe
static bool IsSafe(List<int> board, int currRow,
int currCol){
for (int i = 0; i < board.Count; i++) {
int placedRow = board[i];
int placedCol = i + 1;
// Check diagonals
if (Math.Abs(placedRow - currRow)
== Math.Abs(placedCol - currCol)) {
return false; // Not safe
}
}
return true; // Safe to place
}
// Recursive utility to solve
static void NQueenUtil(int col, int n, List<int> board,
List<List<int> > result,
bool[] visited){
// If all queens placed, add to result
if (col > n) {
result.Add(new List<int>(board));
return;
}
// Try each row in column
for (int row = 1; row <= n; row++) {
// If row not used
if (!visited[row]) {
// Check safety
if (IsSafe(board, row, col)) {
// Mark row
visited[row] = true;
// Place queen
board.Add(row);
// Recur for next column
NQueenUtil(col + 1, n, board, result,
visited);
// Backtrack
board.RemoveAt(board.Count - 1);
visited[row] = false;
}
}
}
}
// Main N-Queen solver
static List<List<int> > NQueen(int n){
List<List<int> > result = new List<List<int> >();
List<int> board = new List<int>();
bool[] visited = new bool[n + 1];
NQueenUtil(1, n, board, result, visited);
return result;
}
// Main method
public static void Main(string[] args){
int n = 4;
List<List<int> > result = NQueen(n);
foreach(var res in result)
{
Console.Write("[");
for (int i = 0; i < res.Count; i++) {
Console.Write(res[i]);
if (i != res.Count - 1)
Console.Write(", ");
}
Console.WriteLine("]");
}
}
}
// Function to check if placement is safe
function isSafe(board, currRow, currCol){
for (let i = 0; i < board.length; i++) {
let placedRow = board[i];
let placedCol = i + 1;
// Check diagonals
if (Math.abs(placedRow - currRow)
=== Math.abs(placedCol - currCol)) {
return false; // Not safe
}
}
return true; // Safe to place
}
// Recursive utility to solve N-Queens
function nQueenUtil(col, n, board, result, visited){
// If all queens placed, add to result
if (col > n) {
result.push([...board ]);
return;
}
// Try each row in column
for (let row = 1; row <= n; row++) {
// If row not used
if (!visited[row]) {
// Check safety
if (isSafe(board, row, col)) {
// Mark row
visited[row] = true;
// Place queen
board.push(row);
// Recur for next column
nQueenUtil(col + 1, n, board, result,
visited);
// Backtrack
board.pop();
visited[row] = false;
}
}
}
}
// Main N-Queen solver
function nQueen(n){
let result = [];
let board = [];
let visited = Array(n + 1).fill(false);
nQueenUtil(1, n, board, result, visited);
return result;
}
// Driver code
let n = 4;
let result = nQueen(n);
result.forEach(res => {
let str = "[";
res.forEach((num, idx) => {
str += num;
if (idx != res.length - 1)
str += ", ";
});
str += "]";
console.log(str);
});
Output[2, 4, 1, 3]
[3, 1, 4, 2]
Time Complexity: O(n!×n), n! for generating all permuation and O(n) for checking validation of each permutation.
Auxiliary Space: O(n) for storing each permutation.
Backtracking with Pruning Approach
To optimize the naive 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 is detected then we’ll backtrack immediately, this will result in avoiding unnecessary computations.
This approach significantly reduces the search space and is the standard method for solving the N-Queens problem efficiently.
Step-by-step approach:
- 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++
#include <bits/stdc++.h>
using namespace std;
// Utility function for solving the N-Queens
// problem using backtracking.
void nQueenUtil(int j, int n, vector<int> &board,
vector<vector<int>> &result, vector<bool> &rows,
vector<bool> &diag1, vector<bool> &diag2){
if (j > n){
// A solution is found
result.push_back(board);
return;
}
for (int i = 1; i <= n; ++i){
if (!rows[i] && !diag1[i + j] &&
!diag2[i - j + n]){
// Place queen
rows[i] = diag1[i + j] =
diag2[i - j + n] = true;
board.push_back(i);
// Recurse to the next column
nQueenUtil(j + 1, n, board, result,
rows, diag1, diag2);
// Remove queen (backtrack)
board.pop_back();
rows[i] = diag1[i + j] =
diag2[i - j + n] = false;
}
}
}
// Solves the N-Queens problem and returns
// all valid configurations.
vector<vector<int>> nQueen(int n){
vector<vector<int>> result;
vector<int> board;
// Rows occupied
vector<bool> rows(n + 1, false);
// Major diagonals (row + j)
vector<bool> diag1(2 * n, false);
// Minor diagonals (row - col + n)
vector<bool> diag2(2 * n, false);
// Start solving from the first column
nQueenUtil(1, n, board, result, rows,
diag1, diag2);
return result;
}
int main(){
int n = 4;
vector<vector<int>> result = nQueen(n);
for (auto &res : result){
cout << "[";
for (int i = 0; i < n; ++i){
cout << res[i];
if (i != n - 1)
cout << ", ";
}
cout << "]\n";
}
return 0;
}
import java.util.ArrayList;
import java.util.List;
// Utility class for N-Queens
class GfG {
// Utility function for solving the N-Queens
// problem using backtracking.
static void nQueenUtil(int j, int n,
List<Integer> board,
List<List<Integer> > result,
boolean[] rows, boolean[] diag1,
boolean[] diag2){
if (j > n) {
// A solution is found
result.add(new ArrayList<>(board));
return;
}
for (int i = 1; i <= n; i++) {
if (!rows[i] && !diag1[i + j]
&& !diag2[i - j + n]) {
// Place queen
rows[i] = diag1[i + j] = diag2[i - j + n]
= true;
board.add(i);
// Recurse to next column
nQueenUtil(j + 1, n, board, result, rows,
diag1, diag2);
// Remove queen (backtrack)
board.remove(board.size() - 1);
rows[i] = diag1[i + j] = diag2[i - j + n]
= false;
}
}
}
// Solves the N-Queens problem and returns
// all valid configurations.
static List<List<Integer> > nQueen(int n){
List<List<Integer> > result = new ArrayList<>();
List<Integer> board = new ArrayList<>();
boolean[] rows = new boolean[n + 1];
boolean[] diag1 = new boolean[2 * n + 1];
boolean[] diag2 = new boolean[2 * n + 1];
// Start solving from first column
nQueenUtil(1, n, board, result, rows, diag1, diag2);
return result;
}
public static void main(String[] args){
int n = 4;
List<List<Integer> > result = nQueen(n);
for (List<Integer> res : result) {
System.out.print("[");
for (int i = 0; i < res.size(); i++) {
System.out.print(res.get(i));
if (i != res.size() - 1)
System.out.print(", ");
}
System.out.println("]");
}
}
}
# Utility function for solving the N-Queens
# problem using backtracking.
def nQueenUtil(j, n, board, result,
rows, diag1, diag2):
if j > n:
# A solution is found
result.append(board.copy())
return
for i in range(1, n +1):
if not rows[i] and not diag1[i + j] and \
not diag2[i - j + n]:
# Place queen
rows[i] = diag1[i + j] = \
diag2[i - j + n] = True
board.append(i)
# Recurse to next column
nQueenUtil(j +1, n, board,
result, rows, diag1, diag2)
# Remove queen (backtrack)
board.pop()
rows[i] = diag1[i + j] = \
diag2[i - j + n] = False
# Solves the N-Queens problem and returns
# all valid configurations.
def nQueen(n):
result = []
board = []
rows = [False] * (n +1)
diag1 = [False] * (2 * n +1)
diag2 = [False] * (2 * n +1)
# Start solving from first column
nQueenUtil(1, n, board, result,
rows, diag1, diag2)
return result
if __name__ == "__main__":
n = 4
result = nQueen(n)
for res in result:
print("[", end="")
for i in range(len(res)):
print(res[i], end="")
if i != len(res)-1:
print(", ", end="")
print("]")
using System;
using System.Collections.Generic;
// Utility class for N-Queens
class GfG {
// Utility function for solving the N-Queens
// problem using backtracking.
public static void NQueenUtil(int j, int n,
List<int> board,
List<List<int> > result,
bool[] rows, bool[] diag1,
bool[] diag2){
if (j > n) {
// A solution is found
result.Add(new List<int>(board));
return;
}
for (int i = 1; i <= n; i++) {
if (!rows[i] && !diag1[i + j]
&& !diag2[i - j + n]) {
// Place queen
rows[i] = diag1[i + j] = diag2[i - j + n]
= true;
board.Add(i);
// Recurse to next column
NQueenUtil(j + 1, n, board, result, rows,
diag1, diag2);
// Remove queen (backtrack)
board.RemoveAt(board.Count - 1);
rows[i] = diag1[i + j] = diag2[i - j + n]
= false;
}
}
}
// Solves the N-Queens problem and returns
// all valid configurations.
static List<List<int> > NQueen(int n){
List<List<int> > result = new List<List<int> >();
List<int> board = new List<int>();
bool[] rows = new bool[n + 1];
bool[] diag1 = new bool[2 * n + 1];
bool[] diag2 = new bool[2 * n + 1];
// Start solving from first column
NQueenUtil(1, n, board, result, rows, diag1, diag2);
return result;
}
public static void Main(){
int n = 4;
List<List<int> > result = NQueen(n);
foreach(var res in result)
{
Console.Write("[");
for (int i = 0; i < res.Count; i++) {
Console.Write(res[i]);
if (i != res.Count - 1)
Console.Write(", ");
}
Console.WriteLine("]");
}
}
}
// Utility function for solving the N-Queens
// problem using backtracking.
function nQueenUtil(j, n, board, result,
rows, diag1, diag2){
if (j > n) {
// A solution is found
result.push([...board ]);
return;
}
for (let i = 1; i <= n; i++) {
if (!rows[i] && !diag1[i + j]
&& !diag2[i - j + n]) {
// Place queen
rows[i] = diag1[i + j] =
diag2[i - j + n] = true;
board.push(i);
// Recurse to next column
nQueenUtil(j + 1, n, board, result,
rows, diag1, diag2);
// Remove queen (backtrack)
board.pop();
rows[i] = diag1[i + j] = diag2[i - j + n]
= false;
}
}
}
// Solves the N-Queens problem and returns
// all valid configurations.
function nQueen(n)
{
let result = [];
let board = [];
let rows = Array(n + 1).fill(false);
let diag1 = Array(2 * n + 1).fill(false);
let diag2 = Array(2 * n + 1).fill(false);
// Start solving from first column
nQueenUtil(1, n, board, result, rows, diag1, diag2);
return result;
}
// Driver code
let n = 4;
let result = nQueen(n);
result.forEach(res => {
let str = "[";
res.forEach((num, idx) => {
str += num;
if (idx != res.length - 1)
str += ", ";
});
str += "]";
console.log(str);
});
Output[2, 4, 1, 3]
[3, 1, 4, 2]
Optimized Backtracking Using Bitmasking Approach
To further optimize the backtracking approach, especially for larger values of n, we can use bitmasking to efficiently track occupied rows and diagonals. Bitmasking lets us to use integer to track which rows and diagonals are occupied, making use of fast bitwise operations for quicker calculations.
Similar Reads
N Queen Problem
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. What is N-Queen problem?The N Queen is the problem of placing N chess queens on an N×N chessboard so that n
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 or the same diagonal. We are going to look for the solution for n=4 on a 4 x 4 chessboard in this artic
15 min read
8 queen problem
The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard. There are different solutions for the problem.
8 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, or diagonal. The backtracking Algorithm for N-Queen is already discussed here. In a backtracking solut
15+ min read
N Queen in O(n) space
Given n, of a n x n chessboard, find the proper placement of queens on chessboard.Previous Approach : N Queen Algorithm : Place(k, i) // Returns true if a queen can be placed // in kth row and ith column. Otherwise it // returns false. X[] is a global array // whose first (k-1) values have been set.
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. Each solution is a unique configuration of n queens, represented as a permutation of [1,2,3,....,n]. The number at the
14 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. Examples: Input : N = 8, M = 8Output : 5Layout : Q X X X X X X X X X Q X X X X X X X X X Q X X X X Q
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: Input : N = 8, x = 4, y = 4, K = 0 Output : 27 Input : N = 8, x = 4, y = 4, K = 1, kx1 = 3, ky1
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 0 0 0 0 0 1 1 0 0 0 0 0 1 0 Explanation: The Position of queens are: 1 - {1, 2} 2 - {2, 4} 3 - {3,
15+ min read