N Queens 🧠
LeetCode Link: N Queens
Difficulty: Hard
Problem Explanation 📝
Problem: LeetCode 51 - N-Queens
Description: 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. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Intuition: The N-Queens problem can be solved using backtracking. The idea is to place queens on the board row by row, ensuring that no two queens attack each other. We can use a recursive approach to explore all possible placements and backtrack when conflicts arise.
Approach:
- Define a vector of vectors
board
to represent the chessboard. - Define a vector
queens
to store the column index of the queens placed in each row. - Define a helper function
backtrack
:
- If the current row is equal to
n
, it means all queens have been placed successfully. Add the currentboard
configuration to theresult
vector. - Otherwise:
- Iterate through the columns from 0 to
n
: - Check if placing a queen at the current position (row, col) is valid (i.e., no conflicts with previously placed queens).
- If it is valid, mark the current position on the
board
as a queen ('Q') and add the current column toqueens
. - Recursively call
backtrack
for the next row. - Remove the queen from the
board
and backtrack by removing the last queen fromqueens
.
- Call the
backtrack
function with the initial row 0. - Return the
result
vector containing all distinct board configurations.
⌛ Time Complexity: The time complexity is O(N!), where N is the size of the chessboard (n x n). This is because there are N! possible placements for the queens.
💾 Space Complexity:
The space complexity is O(N), where N is the size of the chessboard (n x n). This is because we store the board
, queens
, and the result
vector.
Solutions 💡
Cpp 💻
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<string> board(n, string(n, '.')); // Initialize the board with empty spaces
vector<int> queens; // Column indices of the queens in each row
backtrack(n, 0, board, queens, result); // Call the backtrack function to generate all valid solutions
return result;
}
private:
// Backtracking function to generate all valid solutions
void backtrack(int n, int row, vector<string> &board, vector<int> &queens, vector<vector<string>> &result) {
if (row == n) {
result.push_back(board); // Add the current valid solution to the result
return;
}
for (int col = 0; col < n; ++col) {
if (isValidPlacement(row, col, queens)) {
board[row][col] = 'Q'; // Place the queen at the current position
queens.push_back(col); // Store the column index of the queen in the current row
// Recursively call for the next row
backtrack(n, row + 1, board, queens, result);
queens.pop_back(); // Remove the last queen from the current row
board[row][col] = '.'; // Restore the empty space
}
}
}
// Function to check if placing a queen at the current position is valid
bool isValidPlacement(int row, int col, const vector<int> &queens) {
for (int i = 0; i < queens.size(); ++i) {
int rowDiff = abs(row - i);
int colDiff = abs(col - queens[i]);
if (rowDiff == 0 || colDiff == 0 || rowDiff == colDiff) {
return false; // Found a queen in the same row, same column, or diagonal
}
}
return true; // No conflicting queens found, placement is valid
}
};
Python 🐍
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def is_safe(row, col):
# Check for conflicts with previous rows
for prev_row in range(row):
if board[prev_row][col] == "Q":
return False
if (
col - (row - prev_row) >= 0
and board[prev_row][col - (row - prev_row)] == "Q"
):
return False
if (
col + (row - prev_row) < n
and board[prev_row][col + (row - prev_row)] == "Q"
):
return False
return True
def place_queen(row):
if row == n:
result.append(["".join(row) for row in board])
return
for col in range(n):
if is_safe(row, col):
board[row][col] = "Q"
place_queen(row + 1)
board[row][col] = "."
board = [["." for _ in range(n)] for _ in range(n)]
result = []
place_queen(0)
return result
# class Solution:
# def solveNQueens(self, n: int) -> List[List[str]]:
# result = [] # List to store solutions
# board = [['.'] * n for _ in range(n)] # Chessboard representation
# left_diagonal = [False] * (2 * n - 1) # Left diagonals availability
# right_diagonal = [False] * (2 * n - 1) # Right diagonals availability
# column = [False] * n # Columns availability
# def backtrack(row):
# if row == n:
# solution = ["".join(row) for row in board] # Convert the board to a solution format
# result.append(solution)
# return
# for col in range(n):
# # Check if placing a queen in the current position is valid
# if column[col] or left_diagonal[row - col] or right_diagonal[row + col]:
# continue
# # Place a queen and mark unavailable positions
# board[row][col] = 'Q'
# column[col] = left_diagonal[row - col] = right_diagonal[row + col] = True
# # Move to the next row
# backtrack(row + 1)
# # Backtrack: Reset the board and availability
# board[row][col] = '.'
# column[col] = left_diagonal[row - col] = right_diagonal[row + col] = False
# backtrack(0) # Start the backtracking process from the first row
# return result