Search...
Sign In
Interview Questions Quizzes Must Do Advanced DSA System Design Aptitude Puzzles Interview Corner
N Queen Problem
Last Updated : 27 Sep, 2025
Given an integer n, place n queens on an n × n chessboard such that no two
queens attack each other. A queen can attack another queen if they are
placed in the same row, the same column, or on the same diagonal.
Find all possible distinct arrangements of the queens on the board that
satisfy these conditions.
The output should be an array of solutions, where each solution is
represented as an array of integers of size n, and the i-th integer denotes the
column position of the queen in the i-th row. If no solution exists, return an
empty array.
Examples:
Input: n = 4
Output: [[2, 4, 1, 3], [3, 1, 4, 2]]
Explanation: Below is Solution for 4 queen problem
Input: n = 3
Output: []
Explanation: There are no possible solutions for n = 3
Table of Content
[Naive Approach] - Using Backtracking - O(n!) Time and O(n^2) Space
[Optimized Approach] Using Column and Diagonal Hashing
[Naive Approach] - Using Backtracking
The idea is to use backtracking to place queens on an n × n chessboard.
We can proceed either row by row or column by column. For each row
(or column), try placing a queen in every column (or row) and check if it
is safe (i.e., no other queen in the same column, row, or diagonals). If
safe, place the queen and move to the next row/column. If no valid
position exists, backtrack to the previous step and try a different
position. Continue until all queens are placed or all possibilities are
explored.
Below is a sample part of the recursive tree for the above approach (shown
using column-by-column placement of queens).
C++ Java Python C# JavaScript
def isSafe(mat, row, col):
n = len(mat)
# Check this col on upper side
for i in range(row):
if mat[i][col]:
return 0
# Check upper diagonal on left side
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if mat[i][j]:
return 0
i -= 1
j -= 1
# Check upper diagonal on right side
i, j = row - 1, col + 1
while i >= 0 and j < n:
if mat[i][j]:
return 0
i -= 1
j += 1
return 1
# Recursive function to place queens
def placeQueens(row, mat, result):
n = len(mat)
# base case: If all queens are placed
if row == n:
# store current solution
ans = []
for i in range(n):
for j in range(n):
if mat[i][j]:
[Link](j + 1)
[Link](ans)
return
# Consider the row and try placing
# queen in all columns one by one
for i in range(n):
# Check if the queen can be placed
if isSafe(mat, row, i):
mat[row][i] = 1
placeQueens(row + 1, mat, result)
# backtrack
mat[row][i] = 0
# Function to find all solutions
def nQueen(n):
# Initialize the board
mat = [[0] * n for _ in range(n)]
result = []
# Place queens
placeQueens(0, mat, result)
return result
if __name__ == "__main__":
n = 4
result = nQueen(n)
for ans in result:
print(" ".join(map(str, ans)))
Output
2 4 1 3
3 1 4 2
Time Complexity: O(n!)
For the first queen, we have n columns to choose from. Each subsequent
queen has fewer valid positions because previous queens block their columns
and diagonals, roughly reducing choices to n−2, n−4, and so on, giving an
approximate O(n!) time.
Auxiliary Space: O(n2), We use an n × n board to track queen placements,
which requires O(n²) space, plus O(n) space for the recursion stack during
backtracking.
[Optimized Approach] Using Column and Diagonal Hashing
Instead of checking every row and diagonal, use three arrays to track
occupied columns and diagonals. A queen can be placed at a cell only if
its column and both diagonals are free. This reduces the safe-check
from O(n) to O(1).
We use three arrays to efficiently check if a queen can be placed at (i, j)
without conflicts:
cols[] – Tracks if a queen is already placed in a column.
cols[j] = 1 means column j is occupied.
rightDiagonal[] – Tracks diagonals where i + j is constant.
On a chessboard, all cells on the same top-left to bottom-right diagonal
have the same sum of row and column indices (i + j).
So we use rightDiagonal[i + j] to quickly check if that diagonal is occupied.
leftDiagonal[] – Tracks diagonals where i - j is constant.
All cells on the same top-right to bottom-left diagonal have the same
difference (i - j).
To avoid negative indices, we shift by n - 1: leftDiagonal[i - j + n - 1].
This lets us represent all diagonals with non-negative indices in the array.