Language Selection
Choose your preferred programming language
Showing: Python
N-Queens
Problem Statement
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' indicate a queen and an empty space, respectively.
Constraints:
1 <= n <= 9
Examples:
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle:
Solution 1: Solution 2:
. Q . . . . Q .
. . . Q Q . . .
Q . . . . . . Q
. . Q . . Q . .
Example 2:
Input: n = 1
Output: [["Q"]]
Example 3:
Input: n = 2
Output: []
Explanation: There is no way to place 2 queens on a 2x2 board without them attacking each other.
Approach 1: Backtracking with Set-Based Constraint Tracking
Algorithm:
- Place queens row by row (one queen per row is guaranteed since n queens on n rows)
- For each row, try placing a queen in each column
- Maintain three sets to track attacked positions:
cols: columns that already have a queenposDiag: positive diagonals (row + col is constant along each)negDiag: negative diagonals (row - col is constant along each)
- If a column and both diagonals are free, place the queen and recurse to the next row
- When all n rows are filled, record the board configuration
Time Complexity: O(n!) – at row 0 we have n choices, at row 1 at most n-1, and so on Space Complexity: O(n^2) for storing the board configurations
Python:
def solveNQueens(n):
"""
Solve N-Queens using backtracking with set-based constraint tracking
Time: O(n!)
Space: O(n^2) for board storage
"""
result = []
cols = set()
pos_diag = set() # row + col
neg_diag = set() # row - col
board = [['.' ] * n for _ in range(n)]
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
continue
# Place the queen
board[row][col] = 'Q'
cols.add(col)
pos_diag.add(row + col)
neg_diag.add(row - col)
backtrack(row + 1)
# Remove the queen (backtrack)
board[row][col] = '.'
cols.remove(col)
pos_diag.remove(row + col)
neg_diag.remove(row - col)
backtrack(0)
return result
Java:
class Solution {
/**
* Solve N-Queens using backtracking with set-based constraint tracking
* Time: O(n!)
* Space: O(n^2) for board storage
*/
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
Set<Integer> cols = new HashSet<>();
Set<Integer> posDiag = new HashSet<>(); // row + col
Set<Integer> negDiag = new HashSet<>(); // row - col
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0, n, board, cols, posDiag, negDiag, result);
return result;
}
private void backtrack(int row, int n, char[][] board,
Set<Integer> cols, Set<Integer> posDiag,
Set<Integer> negDiag, List<List<String>> result) {
if (row == n) {
List<String> solution = new ArrayList<>();
for (char[] r : board) {
solution.add(new String(r));
}
result.add(solution);
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || posDiag.contains(row + col) ||
negDiag.contains(row - col)) {
continue;
}
// Place the queen
board[row][col] = 'Q';
cols.add(col);
posDiag.add(row + col);
negDiag.add(row - col);
backtrack(row + 1, n, board, cols, posDiag, negDiag, result);
// Remove the queen (backtrack)
board[row][col] = '.';
cols.remove(col);
posDiag.remove(row + col);
negDiag.remove(row - col);
}
}
}
Go:
// solveNQueens - Solve N-Queens using backtracking with set-based constraint tracking
// Time: O(n!)
// Space: O(n^2) for board storage
func solveNQueens(n int) [][]string {
var result [][]string
cols := make(map[int]bool)
posDiag := make(map[int]bool) // row + col
negDiag := make(map[int]bool) // row - col
board := make([][]byte, n)
for i := range board {
board[i] = make([]byte, n)
for j := range board[i] {
board[i][j] = '.'
}
}
var backtrack func(row int)
backtrack = func(row int) {
if row == n {
solution := make([]string, n)
for i, r := range board {
solution[i] = string(r)
}
result = append(result, solution)
return
}
for col := 0; col < n; col++ {
if cols[col] || posDiag[row+col] || negDiag[row-col] {
continue
}
// Place the queen
board[row][col] = 'Q'
cols[col] = true
posDiag[row+col] = true
negDiag[row-col] = true
backtrack(row + 1)
// Remove the queen (backtrack)
board[row][col] = '.'
delete(cols, col)
delete(posDiag, row+col)
delete(negDiag, row-col)
}
}
backtrack(0)
return result
}
JavaScript:
/**
* Solve N-Queens using backtracking with set-based constraint tracking
* Time: O(n!)
* Space: O(n^2) for board storage
*/
function solveNQueens(n) {
const result = [];
const cols = new Set();
const posDiag = new Set(); // row + col
const negDiag = new Set(); // row - col
const board = Array.from({ length: n }, () => Array(n).fill('.'));
function backtrack(row) {
if (row === n) {
result.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
continue;
}
// Place the queen
board[row][col] = 'Q';
cols.add(col);
posDiag.add(row + col);
negDiag.add(row - col);
backtrack(row + 1);
// Remove the queen (backtrack)
board[row][col] = '.';
cols.delete(col);
posDiag.delete(row + col);
negDiag.delete(row - col);
}
}
backtrack(0);
return result;
}
C#:
public class Solution {
/// <summary>
/// Solve N-Queens using backtracking with set-based constraint tracking
/// Time: O(n!)
/// Space: O(n^2) for board storage
/// </summary>
public IList<IList<string>> SolveNQueens(int n) {
IList<IList<string>> result = new List<IList<string>>();
HashSet<int> cols = new HashSet<int>();
HashSet<int> posDiag = new HashSet<int>(); // row + col
HashSet<int> negDiag = new HashSet<int>(); // row - col
char[][] board = new char[n][];
for (int i = 0; i < n; i++) {
board[i] = new char[n];
Array.Fill(board[i], '.');
}
Backtrack(0, n, board, cols, posDiag, negDiag, result);
return result;
}
private void Backtrack(int row, int n, char[][] board,
HashSet<int> cols, HashSet<int> posDiag,
HashSet<int> negDiag, IList<IList<string>> result) {
if (row == n) {
List<string> solution = new List<string>();
foreach (char[] r in board) {
solution.Add(new string(r));
}
result.Add(solution);
return;
}
for (int col = 0; col < n; col++) {
if (cols.Contains(col) || posDiag.Contains(row + col) ||
negDiag.Contains(row - col)) {
continue;
}
// Place the queen
board[row][col] = 'Q';
cols.Add(col);
posDiag.Add(row + col);
negDiag.Add(row - col);
Backtrack(row + 1, n, board, cols, posDiag, negDiag, result);
// Remove the queen (backtrack)
board[row][col] = '.';
cols.Remove(col);
posDiag.Remove(row + col);
negDiag.Remove(row - col);
}
}
}
Approach 2: Backtracking with Array-Based Constraint Tracking
Algorithm:
- Instead of hash sets, use boolean arrays for O(1) lookup with lower constant overhead
colUsed[col]tracks whether columncolhas a queenposDiagUsed[row + col]tracks positive diagonals (indices range from 0 to 2n-2)negDiagUsed[row - col + n - 1]tracks negative diagonals (shift by n-1 to avoid negative indices)- Same row-by-row backtracking logic as Approach 1
Time Complexity: O(n!) Space Complexity: O(n^2) for storing the board configurations
Python:
def solveNQueens(n):
"""
Solve N-Queens using backtracking with array-based constraint tracking
Time: O(n!)
Space: O(n^2) for board storage
"""
result = []
col_used = [False] * n
pos_diag_used = [False] * (2 * n - 1) # row + col ranges from 0 to 2n-2
neg_diag_used = [False] * (2 * n - 1) # row - col + n - 1 ranges from 0 to 2n-2
board = [['.' ] * n for _ in range(n)]
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
pd = row + col
nd = row - col + n - 1
if col_used[col] or pos_diag_used[pd] or neg_diag_used[nd]:
continue
# Place the queen
board[row][col] = 'Q'
col_used[col] = True
pos_diag_used[pd] = True
neg_diag_used[nd] = True
backtrack(row + 1)
# Remove the queen (backtrack)
board[row][col] = '.'
col_used[col] = False
pos_diag_used[pd] = False
neg_diag_used[nd] = False
backtrack(0)
return result
Java:
class Solution {
/**
* Solve N-Queens using backtracking with array-based constraint tracking
* Time: O(n!)
* Space: O(n^2) for board storage
*/
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
boolean[] colUsed = new boolean[n];
boolean[] posDiagUsed = new boolean[2 * n - 1]; // row + col
boolean[] negDiagUsed = new boolean[2 * n - 1]; // row - col + n - 1
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0, n, board, colUsed, posDiagUsed, negDiagUsed, result);
return result;
}
private void backtrack(int row, int n, char[][] board,
boolean[] colUsed, boolean[] posDiagUsed,
boolean[] negDiagUsed, List<List<String>> result) {
if (row == n) {
List<String> solution = new ArrayList<>();
for (char[] r : board) {
solution.add(new String(r));
}
result.add(solution);
return;
}
for (int col = 0; col < n; col++) {
int pd = row + col;
int nd = row - col + n - 1;
if (colUsed[col] || posDiagUsed[pd] || negDiagUsed[nd]) {
continue;
}
// Place the queen
board[row][col] = 'Q';
colUsed[col] = true;
posDiagUsed[pd] = true;
negDiagUsed[nd] = true;
backtrack(row + 1, n, board, colUsed, posDiagUsed, negDiagUsed, result);
// Remove the queen (backtrack)
board[row][col] = '.';
colUsed[col] = false;
posDiagUsed[pd] = false;
negDiagUsed[nd] = false;
}
}
}
Go:
// solveNQueens - Solve N-Queens using backtracking with array-based constraint tracking
// Time: O(n!)
// Space: O(n^2) for board storage
func solveNQueens(n int) [][]string {
var result [][]string
colUsed := make([]bool, n)
posDiagUsed := make([]bool, 2*n-1) // row + col
negDiagUsed := make([]bool, 2*n-1) // row - col + n - 1
board := make([][]byte, n)
for i := range board {
board[i] = make([]byte, n)
for j := range board[i] {
board[i][j] = '.'
}
}
var backtrack func(row int)
backtrack = func(row int) {
if row == n {
solution := make([]string, n)
for i, r := range board {
solution[i] = string(r)
}
result = append(result, solution)
return
}
for col := 0; col < n; col++ {
pd := row + col
nd := row - col + n - 1
if colUsed[col] || posDiagUsed[pd] || negDiagUsed[nd] {
continue
}
// Place the queen
board[row][col] = 'Q'
colUsed[col] = true
posDiagUsed[pd] = true
negDiagUsed[nd] = true
backtrack(row + 1)
// Remove the queen (backtrack)
board[row][col] = '.'
colUsed[col] = false
posDiagUsed[pd] = false
negDiagUsed[nd] = false
}
}
backtrack(0)
return result
}
JavaScript:
/**
* Solve N-Queens using backtracking with array-based constraint tracking
* Time: O(n!)
* Space: O(n^2) for board storage
*/
function solveNQueens(n) {
const result = [];
const colUsed = new Array(n).fill(false);
const posDiagUsed = new Array(2 * n - 1).fill(false); // row + col
const negDiagUsed = new Array(2 * n - 1).fill(false); // row - col + n - 1
const board = Array.from({ length: n }, () => Array(n).fill('.'));
function backtrack(row) {
if (row === n) {
result.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
const pd = row + col;
const nd = row - col + n - 1;
if (colUsed[col] || posDiagUsed[pd] || negDiagUsed[nd]) {
continue;
}
// Place the queen
board[row][col] = 'Q';
colUsed[col] = true;
posDiagUsed[pd] = true;
negDiagUsed[nd] = true;
backtrack(row + 1);
// Remove the queen (backtrack)
board[row][col] = '.';
colUsed[col] = false;
posDiagUsed[pd] = false;
negDiagUsed[nd] = false;
}
}
backtrack(0);
return result;
}
C#:
public class Solution {
/// <summary>
/// Solve N-Queens using backtracking with array-based constraint tracking
/// Time: O(n!)
/// Space: O(n^2) for board storage
/// </summary>
public IList<IList<string>> SolveNQueens(int n) {
IList<IList<string>> result = new List<IList<string>>();
bool[] colUsed = new bool[n];
bool[] posDiagUsed = new bool[2 * n - 1]; // row + col
bool[] negDiagUsed = new bool[2 * n - 1]; // row - col + n - 1
char[][] board = new char[n][];
for (int i = 0; i < n; i++) {
board[i] = new char[n];
Array.Fill(board[i], '.');
}
Backtrack(0, n, board, colUsed, posDiagUsed, negDiagUsed, result);
return result;
}
private void Backtrack(int row, int n, char[][] board,
bool[] colUsed, bool[] posDiagUsed,
bool[] negDiagUsed, IList<IList<string>> result) {
if (row == n) {
List<string> solution = new List<string>();
foreach (char[] r in board) {
solution.Add(new string(r));
}
result.Add(solution);
return;
}
for (int col = 0; col < n; col++) {
int pd = row + col;
int nd = row - col + n - 1;
if (colUsed[col] || posDiagUsed[pd] || negDiagUsed[nd]) {
continue;
}
// Place the queen
board[row][col] = 'Q';
colUsed[col] = true;
posDiagUsed[pd] = true;
negDiagUsed[nd] = true;
Backtrack(row + 1, n, board, colUsed, posDiagUsed, negDiagUsed, result);
// Remove the queen (backtrack)
board[row][col] = '.';
colUsed[col] = false;
posDiagUsed[pd] = false;
negDiagUsed[nd] = false;
}
}
}
Key Insights
Row-by-Row Placement: Since each row must contain exactly one queen, we place one queen per row. This reduces the problem from O(n^2) positions to O(n) choices per level.
Diagonal Identification: On an n x n board, cells on the same positive diagonal share the same
row + colvalue, and cells on the same negative diagonal share the samerow - colvalue. This allows O(1) conflict detection.O(n!) Time Bound: At row 0 there are at most n valid columns. At row 1 there are at most n-1 (one column is taken), and so on. The total work is bounded by n * (n-1) * (n-2) * … * 1 = n!.
Sets vs Arrays: Hash sets provide O(1) average-case lookup but have higher constant overhead. Boolean arrays provide O(1) guaranteed lookup with lower overhead, making them faster in practice for small n.
No Row Tracking Needed: Since we place exactly one queen per row and advance the row counter, we never need to check for row conflicts.
Edge Cases
n = 1: single solution[["Q"]]n = 2: no solution, returns[]n = 3: no solution, returns[]n = 4: two solutionsn = 8: 92 solutions (the classic 8-queens problem)n = 9: 352 solutions
Test Cases
# Test case 1: n = 1
assert solveNQueens(1) == [["Q"]]
# Test case 2: n = 2 (no solution)
assert solveNQueens(2) == []
# Test case 3: n = 3 (no solution)
assert solveNQueens(3) == []
# Test case 4: n = 4 (two solutions)
result = solveNQueens(4)
assert len(result) == 2
assert [".Q..","...Q","Q...","..Q."] in result
assert ["..Q.","Q...","...Q",".Q.."] in result
# Test case 5: n = 8 (classic problem)
result = solveNQueens(8)
assert len(result) == 92
Common Mistakes
- Forgetting diagonal checks: Only checking columns leads to queens attacking each other diagonally. Both positive and negative diagonals must be tracked.
- Wrong diagonal formula: Using
row + colfor both diagonals or confusing the signs. Positive diagonals userow + col; negative diagonals userow - col. - Negative index in arrays: When using arrays instead of sets for negative diagonals,
row - colcan be negative. Shift byn - 1to ensure non-negative indices. - Not restoring state on backtrack: Forgetting to unmark the column and diagonals after removing a queen causes valid placements to be incorrectly skipped.
- Storing references to the board: Appending the board object directly instead of creating a snapshot means all solutions end up as the final (empty) board state.