N Queen Problem
What is N-Queen Problem?
The n-queens puzzle is about placing n queens on an n x n chessboard so that no two queens can attack each other.
Queens can attack in three ways: horizontally, vertically, and diagonally.
Your task is to find all possible ways to place the queens on the board, ensuring no two queens attack each other.
Each solution will show a unique board arrangement where ‘Q’ represents a queen and ‘.’ represents an empty square. The solutions can be returned in any order.
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
Output: [[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
Explanation: There are two different solutions to the 4-queens puzzle.
Example 2
Input: n = 1
Output: [["Q"]]
Output: [["Q"]]
Constraints:
- 1 <= n <= 8
N Queen Problem Solution
Recommendation for Time and Space Complexity – The solution should aim for O(n!) time and O(n²) space, where n is the size of the chessboard.
Hints for solving problems
Hint 1 :
A queen can attack in 8 directions, but we only need to ensure no two queens are in the same row, column, or diagonals. Place one queen per row and try each column. Use a recursive approach to explore all valid ways to position the queens.
Hint 2 :
Use backtracking to explore the chessboard column by column. Start with an empty board and place a queen in a valid cell. If you successfully place queens in all columns, add the board configuration to the result.
Hint 3 :
Begin with an empty board and check each cell in the current column to see if it’s safe to place a queen. A cell is valid if no queens exist in the same row, left diagonal, or left bottom diagonal. Place the queen, continue the recursive search, and backtrack by removing the queen to explore other options.
There are mainly 4 approach to solve this problem-
- Backtracking Method
- Backtracking(Hash Set) Method
- Backtracking(Visited Array) Method
- Backtracking(Bit Mask) Method
1. Backtracking Method
This method uses recursion to place queens row by row while ensuring no two queens attack each other. At each step, we check the validity of placing a queen by verifying the current row, column, and diagonals. If a valid placement is found, the algorithm continues recursively; otherwise, it backtracks.
- Time complexity: O(n!)
- Space complexity: O(n^2)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> board(n, string(n, '.'));
backtrack(0, board, res);
return res;
}
void backtrack(int r, vector<string>& board, vector<vector<string>>& res) {
if (r == board.size()) {
res.push_back(board);
return;
}
for (int c = 0; c < board.size(); c++) {
if (isSafe(r, c, board)) {
board[r][c] = 'Q';
backtrack(r + 1, board, res);
board[r][c] = '.';
}
}
}
bool isSafe(int r, int c, vector<string>& board) {
for (int i = r - 1; i >= 0; i--) {
if (board[i][c] == 'Q') return false;
}
for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
for (int i = r - 1, j = c + 1; i >= 0 && j < board.size(); i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
};
Java
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
backtrack(0, board, res);
return res;
}
private void backtrack(int r, char[][] board, List<List<String>> res) {
if (r == board.length) {
List copy = new ArrayList<>();
for (char[] row : board) {
copy.add(new String(row));
}
res.add(copy);
return;
}
for (int c = 0; c < board.length; c++) { if (isSafe(r, c, board)) { board[r][c] = 'Q'; backtrack(r + 1, board, res); board[r][c] = '.'; } } } private boolean isSafe(int r, int c, char[][] board) { for (int i = r - 1; i >= 0; i--) {
if (board[i][c] == 'Q') return false;
}
for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
for (int i = r - 1, j = c + 1; i >= 0 && j < board.length; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
}
Python
class Solution:
def solveNQueens(self, n: int):
res = []
board = [["."] * n for i in range(n)]
def backtrack(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if self.isSafe(r, c, board):
board[r][c] = "Q"
backtrack(r + 1)
board[r][c] = "."
backtrack(0)
return res
def isSafe(self, r: int, c: int, board):
row = r - 1
while row >= 0:
if board[row][c] == "Q":
return False
row -= 1
row, col = r - 1, c - 1
while row >= 0 and col >= 0:
if board[row][col] == "Q":
return False
row -= 1
col -= 1
row, col = r - 1, c + 1
while row >= 0 and col < len(board):
if board[row][col] == "Q":
return False
row -= 1
col += 1
return True
JavaScript
class Solution {
/**
* @param {number} n
* @return {string[][]}
*/
solveNQueens(n) {
let res = [];
let board = Array.from({length: n}, () => Array(n).fill('.'));
const backtrack = (r) => {
if (r === n) {
res.push(board.map(row => row.join('')));
return;
}
for (let c = 0; c < n; c++) { if (this.isSafe(r, c, board)) { board[r][c] = 'Q'; backtrack(r + 1); board[r][c] = '.'; } } } backtrack(0); return res; } /** * @param {number} r * @param {number} c * @param {string[][]} board * @return {boolean} */ isSafe(r, c, board) { for (let i = r - 1; i >= 0; i--) {
if (board[i][c] === 'Q') return false;
}
for (let i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === 'Q') return false;
}
for (let i = r - 1, j = c + 1; i >= 0 && j < board.length; i--, j++) {
if (board[i][j] === 'Q') return false;
}
return true;
}
}
2. Backtracking(Hash Set) Method
Here, we use hash sets to track the columns and diagonals already occupied by queens. These sets allow quick lookups to check if a cell is safe for placing a queen. The method reduces redundant checks and improves efficiency.
- Time complexity: O(n!)
- Space complexity: O(n^2)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
unordered_set<int> col;
unordered_set<int> posDiag;
unordered_set<int> negDiag;
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtrack(0, n, board);
return res;
}
private:
void backtrack(int r, int n, vector<string>& board) {
if (r == n) {
res.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
if (col.count(c) || posDiag.count(r + c) ||
negDiag.count(r - c)) {
continue;
}
col.insert(c);
posDiag.insert(r + c);
negDiag.insert(r - c);
board[r][c] = 'Q';
backtrack(r + 1, n, board);
col.erase(c);
posDiag.erase(r + c);
negDiag.erase(r - c);
board[r][c] = '.';
}
}
};
Java
public class Solution {
Set<Integer> col = new HashSet<>();
Set<Integer> posDiag = new HashSet<>();
Set<Integer> negDiag = new HashSet<>();
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0, n, board);
return res;
}
private void backtrack(int r, int n, char[][] board) {
if (r == n) {
List<String> copy = new ArrayList<>();
for (char[] row : board) {
copy.add(new String(row));
}
res.add(copy);
return;
}
for (int c = 0; c < n; c++) {
if (col.contains(c) || posDiag.contains(r + c)
|| negDiag.contains(r - c)) {
continue;
}
col.add(c);
posDiag.add(r + c);
negDiag.add(r - c);
board[r][c] = 'Q';
backtrack(r + 1, n, board);
col.remove(c);
posDiag.remove(r + c);
negDiag.remove(r - c);
board[r][c] = '.';
}
}
}
Python
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
col = set()
posDiag = set()
negDiag = set()
res = []
board = [["."] * n for i in range(n)]
def backtrack(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if c in col or (r + c) in posDiag or (r - c) in negDiag:
continue
col.add(c)
posDiag.add(r + c)
negDiag.add(r - c)
board[r][c] = "Q"
backtrack(r + 1)
col.remove(c)
posDiag.remove(r + c)
negDiag.remove(r - c)
board[r][c] = "."
backtrack(0)
return res
JavaScript
class Solution {
/**
* @param {number} n
* @return {string[][]}
*/
solveNQueens(n) {
const col = new Set();
const posDiag = new Set();
const negDiag = new Set();
const res = [];
const board = Array.from({ length: n },
() => Array(n).fill('.'));
/**
* @param {number} r
* @return {void}
*/
function backtrack(r) {
if (r === n) {
res.push(board.map(row => row.join('')));
return;
}
for (let c = 0; c < n; c++) {
if (col.has(c) || posDiag.has(r + c) ||
negDiag.has(r - c)) {
continue;
}
col.add(c);
posDiag.add(r + c);
negDiag.add(r - c);
board[r][c] = 'Q';
backtrack(r + 1);
col.delete(c);
posDiag.delete(r + c);
negDiag.delete(r - c);
board[r][c] = '.';
}
}
backtrack(0);
return res;
}
}
3. Backtracking(Visited Array) Method
Instead of hash sets, this method uses arrays to mark visited columns and diagonals. One array tracks columns, and two additional arrays track the left and right diagonals. This approach is similar to the hash set method but more space-efficient.
- Time complexity: O(n!)
- Space complexity: O(n^2)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<string> board;
vector<bool> col, posDiag, negDiag;
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
col.resize(n, false);
posDiag.resize(2 * n, false);
negDiag.resize(2 * n, false);
board.resize(n, string(n, '.'));
backtrack(0, n);
return res;
}
void backtrack(int r, int n) {
if (r == n) {
res.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || posDiag[r + c] || negDiag[r - c + n]) {
continue;
}
col[c] = true;
posDiag[r + c] = true;
negDiag[r - c + n] = true;
board[r][c] = 'Q';
backtrack(r + 1, n);
col[c] = false;
posDiag[r + c] = false;
negDiag[r - c + n] = false;
board[r][c] = '.';
}
}
};
Java
public class Solution {
boolean[] col, posDiag, negDiag;
List<List<String>> res;
char[][] board;
public List<List<String>> solveNQueens(int n) {
col = new boolean[n];
posDiag = new boolean[2 * n];
negDiag = new boolean[2 * n];
res = new ArrayList<>();
board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
backtrack(0, n);
return res;
}
private void backtrack(int r, int n) {
if (r == n) {
List<String> copy = new ArrayList<>();
for (char[] row : board) {
copy.add(new String(row));
}
res.add(copy);
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || posDiag[r + c] || negDiag[r - c + n]) {
continue;
}
col[c] = true;
posDiag[r + c] = true;
negDiag[r - c + n] = true;
board[r][c] = 'Q';
backtrack(r + 1, n);
col[c] = false;
posDiag[r + c] = false;
negDiag[r - c + n] = false;
board[r][c] = '.';
}
}
}
Python
class Solution:
def solveNQueens(self, n: int):
col = [False] * n
posDiag = [False] * (n * 2)
negDiag = [False] * (n * 2)
res = []
board = [["."] * n for i in range(n)]
def backtrack(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if col[c] or posDiag[r + c] or negDiag[r - c + n]:
continue
col[c] = True
posDiag[r + c] = True
negDiag[r - c + n] = True
board[r][c] = "Q"
backtrack(r + 1)
col[c] = False
posDiag[r + c] = False
negDiag[r - c + n] = False
board[r][c] = "."
backtrack(0)
return res
JavaScript
class Solution {
/**
* @param {number} n
* @return {string[][]}
*/
solveNQueens(n) {
const col = Array(n).fill(false);
const posDiag = Array(2 * n).fill(false);
const negDiag = Array(2 * n).fill(false);
const res = [];
const board = Array.from({ length: n },
() => Array(n).fill('.'));
/**
* @param {number} r
* @return {void}
*/
function backtrack(r) {
if (r === n) {
res.push(board.map(row => row.join('')));
return;
}
for (let c = 0; c < n; c++) {
if (col[c] || posDiag[r + c] || negDiag[r - c + n]) {
continue;
}
col[c] = true;
posDiag[r + c] = true;
negDiag[r - c + n] = true;
board[r][c] = 'Q';
backtrack(r + 1, n);
col[c] = false;
posDiag[r + c] = false;
negDiag[r - c + n] = false;
board[r][c] = '.';
}
}
backtrack(0);
return res;
}
}
4. Backtracking(Bit Mask) Method
This optimized approach uses bit masking to track columns and diagonals, making it extremely space-efficient. By representing occupied columns and diagonals as bits in integers, we can quickly check and update states during recursion, making it suitable for larger board sizes.
- Time complexity: O(n!)
- Space complexity: O(n^2)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int col = 0, posDiag = 0, negDiag = 0;
vector<string> board;
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
board.resize(n, string(n, '.'));
backtrack(0, n);
return res;
}
void backtrack(int r, int n) {
if (r == n) {
res.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
if ((col & (1 << c)) || (posDiag & (1 << (r + c)))
|| (negDiag & (1 << (r - c + n)))) {
continue;
}
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = 'Q';
backtrack(r + 1, n);
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = '.';
}
}
};
Java
public class Solution {
int col = 0, posDiag = 0, negDiag = 0;
List<List<String>> res;
char[][] board;
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
backtrack(0, n);
return res;
}
private void backtrack(int r, int n) {
if (r == n) {
List<String> copy = new ArrayList<>();
for (char[] row : board) {
copy.add(new String(row));
}
res.add(copy);
return;
}
for (int c = 0; c < n; c++) {
if ((col & (1 << c)) > 0 || (posDiag & (1 << (r + c))) > 0
|| (negDiag & (1 << (r - c + n))) > 0) {
continue;
}
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = 'Q';
backtrack(r + 1, n);
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = '.';
}
}
}
Python
class Solution:
def solveNQueens(self, n: int):
col = 0
posDiag = 0
negDiag = 0
res = []
board = [["."] * n for i in range(n)]
def backtrack(r):
nonlocal col, posDiag, negDiag
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if ((col & (1 << c)) or (posDiag & (1 << (r + c)))
or (negDiag & (1 << (r - c + n)))):
continue
col ^= (1 << c)
posDiag ^= (1 << (r + c))
negDiag ^= (1 << (r - c + n))
board[r][c] = "Q"
backtrack(r + 1)
col ^= (1 << c)
posDiag ^= (1 << (r + c))
negDiag ^= (1 << (r - c + n))
board[r][c] = "."
backtrack(0)
return res
JavaScript
class Solution {
/**
* @param {number} n
* @return {string[][]}
*/
solveNQueens(n) {
let col = 0, posDiag = 0, negDiag = 0;
const res = [];
const board = Array.from({ length: n },
() => Array(n).fill('.'));
/**
* @param {number} r
* @return {void}
*/
function backtrack(r) {
if (r === n) {
res.push(board.map(row => row.join('')));
return;
}
for (let c = 0; c < n; c++) {
if ((col & (1 << c)) > 0 || (posDiag & (1 << (r + c))) > 0
|| (negDiag & (1 << (r - c + n))) > 0) {
continue;
}
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = 'Q';
backtrack(r + 1, n);
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = '.';
}
}
backtrack(0);
return res;
}
}
