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 '.' both indicate a queen and an empty space, respectively.
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 as shown above.
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
1 <= n <= 9
Approach:
- Use
backtrackingrow by row to try placing queens. - Keep three sets to track conflicts:
colSet→ columns with a queen.digSet→ diagonals with slope \(row - col).antiDigSet→ diagonals with slope /(row + col).
- At each row:
- Try every
column. - If column or
diagonalsare already attacked,skip. - Otherwise, place a queen, mark sets, and recurse for the next row.
- Try every
- If all
rows are filled, convert board into string form and add to results. - After recursion,
remove the queen(backtrack) andunmark sets.
Time Complexity:
Time Complexity = O(n!)
Space Complexity:
Space Complexity = O(n2)
Dry Run
Input:
n = 4
State Transitions:
Initialize:
result = []
board = [
[".",".",".","."],
[".",".",".","."],
[".",".",".","."],
[".",".",".","."]
]
Call backtrack(board, row=0, colSet={}, digSet={}, antiDigSet={})
Level 0: row = 0
col=0 → safe → place Q
board[0][0] = "Q"
colSet = {0}, digSet = {0}, antiDigSet = {0}
→ recurse row=1
Level 1: row = 1
col=0 → colSet has 0 → skip
col=1 → digSet has (1-1=0) → skip
col=2 → safe → place Q
board[1][2] = "Q"
colSet = {0,2}, digSet = {0,-1}, antiDigSet = {0,3}
→ recurse row=2
Level 2: row = 2
col=0 → colSet has 0 → skip
col=1 → safe → place Q
board[2][1] = "Q"
colSet = {0,1,2}, digSet = {0,-1,1}, antiDigSet = {0,3,3}
→ recurse row=3
Level 3: row = 3
col=0 → colSet has 0 → skip
col=1 → colSet has 1 → skip
col=2 → colSet has 2 → skip
col=3 → digSet has (3-3=0) → skip
→ no placement possible → backtrack
Remove Q at (2,1)
Backtracking row = 2
col=2 → colSet has 2 → skip
col=3 → safe → place Q
board[2][3] = "Q"
colSet = {0,2,3}, digSet = {0,-1,-1}, antiDigSet = {0,3,5}
→ recurse row=3
Level 3: row = 3
col=0 → safe → place Q
board[3][0] = "Q"
colSet = {0,2,3}, digSet = {0,-1,-1,3}, antiDigSet = {0,3,5,3}
row == n → solution found!
Transform(board):
[".Q..", "...Q", "Q...", "..Q."]
→ push to result
Backtracking continues to find 2nd solution…
Eventually result =
[
[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]
]
Final Output:
[ [".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."] ]
Explanation:
The algorithm uses backtracking with sets to track:
colSet: columns already occupieddigSet: diagonals (row - col)antiDigSet: anti-diagonals (row + col)
- Start from row 0 and try placing queens in safe positions.
- If a placement is valid, recurse to the next row.
- If no valid placement, backtrack by removing the last queen.
- When row == n, transform the board into string format and store in result.
- Finally, all valid 4-Queens solutions are collected.
var solveNQueens = function(n) {
let result = [];
let board = Array.from({ length: n}, () => Array(n).fill("."));
let backtrack = (board, row, colSet, digSet, antiDigSet) => {
if(row == n){
result.push(transform(board));
}
for (let col = 0; col < n; col++) {
if (colSet.has(col) ||
digSet.has(row - col) ||
antiDigSet.has(row + col)) {
continue;
}
board [row][col] = "Q";
colSet.add(col);
digSet.add(row - col);
antiDigSet.add(row + col);
backtrack(board, row + 1, colSet, digSet, antiDigSet);
board[row][col] = ".";
colSet.delete(col);
digSet.delete(row - col);
antiDigSet.delete(row + col);
}
};
backtrack(board, 0, new Set(), new Set(), new Set());
return result;
};
let transform = (board) => {
let newBoard = [];
for(let i=0; i < board.length; i++){
newBoard.push(board[i].join(""));
}
return newBoard;
}
def solveNQueens(n):
result = []
board = [["."] * n for _ in range(n)]
def backtrack(row, colSet, digSet, antiDigSet):
if row == n:
result.append(["".join(r) for r in board])
return
for col in range(n):
if col in colSet or (row - col) in digSet or (row + col) in antiDigSet:
continue
board[row][col] = "Q"
colSet.add(col)
digSet.add(row - col)
antiDigSet.add(row + col)
backtrack(row + 1, colSet, digSet, antiDigSet)
board[row][col] = "."
colSet.remove(col)
digSet.remove(row - col)
antiDigSet.remove(row + col)
backtrack(0, set(), set(), set())
return result
import java.util.*;
class Solution {
public List> solveNQueens(int n) {
List> result = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board)
Arrays.fill(row, '.');
backtrack(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), board, result);
return result;
}
private void backtrack(int row, Set cols, Set diag1, Set diag2, char[][] board, List> result) {
int n = board.length;
if (row == n) {
List newBoard = new ArrayList<>();
for (char[] r : board) newBoard.add(new String(r));
result.add(newBoard);
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue;
board[row][col] = 'Q';
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
backtrack(row + 1, cols, diag1, diag2, board, result);
board[row][col] = '.';
cols.remove(col);
diag1.remove(row - col);
diag2.remove(row + col);
}
}
}
class Solution {
public:
vector> solveNQueens(int n) {
vector> result;
vector board(n, string(n, '.'));
unordered_set cols, diag1, diag2;
function backtrack = [&](int row) {
if (row == n) {
result.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col)) continue;
board[row][col] = 'Q';
cols.insert(col);
diag1.insert(row - col);
diag2.insert(row + col);
backtrack(row + 1);
board[row][col] = '.';
cols.erase(col);
diag1.erase(row - col);
diag2.erase(row + col);
}
};
backtrack(0);
return result;
}
};
int resultCount = 0;
void printBoard(int n, char board[MAXN][MAXN]) {
printf("Solution %d:\n", ++resultCount);
for (int i = 0; i < n; i++) {
printf("%s\n", board[i]);
}
printf("\n");
}
void backtrack(int n, int row, int cols[], int diag1[], int diag2[], char board[MAXN][MAXN]) {
if (row == n) {
printBoard(n, board);
return;
}
for (int col = 0; col < n; col++) {
if (cols[col] || diag1[row - col + n - 1] || diag2[row + col]) continue;
board[row][col] = 'Q';
cols[col] = diag1[row - col + n - 1] = diag2[row + col] = 1;
backtrack(n, row + 1, cols, diag1, diag2, board);
board[row][col] = '.';
cols[col] = diag1[row - col + n - 1] = diag2[row + col] = 0;
}
}
void solveNQueens(int n) {
char board[MAXN][MAXN];
int cols[MAXN] = {0}, diag1[2*MAXN] = {0}, diag2[2*MAXN] = {0};
for (int i = 0; i < n; i++)
memset(board[i], '.', n), board[i][n] = '\0';
backtrack(n, 0, cols, diag1, diag2, board);
}
int main() {
int n = 4;
solveNQueens(n);
return 0;
}
using System;
using System.Collections.Generic;
public class Solution {
public IList> SolveNQueens(int n) {
var result = new List>();
var board = new char[n][];
for (int i = 0; i < n; i++)
board[i] = new string('.', n).ToCharArray();
Backtrack(0, new HashSet(), new HashSet(), new HashSet(), board, result);
return result;
}
private void Backtrack(int row, HashSet cols, HashSet diag1, HashSet diag2, char[][] board, IList> result) {
int n = board.Length;
if (row == n) {
var newBoard = new List();
foreach (var r in board)
newBoard.Add(new string(r));
result.Add(newBoard);
return;
}
for (int col = 0; col < n; col++) {
if (cols.Contains(col) || diag1.Contains(row - col) || diag2.Contains(row + col)) continue;
board[row][col] = 'Q';
cols.Add(col);
diag1.Add(row - col);
diag2.Add(row + col);
Backtrack(row + 1, cols, diag1, diag2, board, result);
board[row][col] = '.';
cols.Remove(col);
diag1.Remove(row - col);
diag2.Remove(row + col);
}
}
}
