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 the number of distinct solutions to the n-queens puzzle.
Examples:
Example 1:
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1
Output: 1Solution in Python:
To solve the problem of finding the number of distinct solutions to the n-queens puzzle, we can use a backtracking approach.
Python
class Solution:
def totalNQueens(self, n: int) -> int:
# Function to check if placing a queen at board[row][col] is valid
def is_valid(row, col, cols, diagonals, anti_diagonals):
if cols[col] or diagonals[row - col] or anti_diagonals[row + col]:
return False
return True
# Backtracking function to place queens
def backtrack(row, cols, diagonals, anti_diagonals):
if row == n: # If all queens are placed successfully
return 1
count = 0
for col in range(n):
if is_valid(row, col, cols, diagonals, anti_diagonals):
# Place the queen
cols[col] = True
diagonals[row - col] = True
anti_diagonals[row + col] = True
# Move to the next row
count += backtrack(row + 1, cols, diagonals, anti_diagonals)
# Remove the queen (backtrack)
cols[col] = False
diagonals[row - col] = False
anti_diagonals[row + col] = False
return count
# Initialize arrays to track columns and diagonals
cols = [False] * n
diagonals = [False] * (2 * n - 1)
anti_diagonals = [False] * (2 * n - 1)
# Start backtracking from the first row
return backtrack(0, cols, diagonals, anti_diagonals)Explanation:
- Initialization:
cols: A list to track if a column is occupied by a queen.diagonals: A list to track if a main diagonal is under attack by a queen. The index is calculated asrow - col + n - 1.anti_diagonals: A list to track if an anti-diagonal is under attack by a queen. The index is calculated asrow + col.
- Validation Function:
is_valid(row, col, cols, diagonals, anti_diagonals): This function checks if placing a queen atboard[row][col]is valid by ensuring that the column, main diagonal, and anti-diagonal are not already under attack.
- Backtracking Function:
backtrack(row, cols, diagonals, anti_diagonals): This function tries to place a queen in each column of the current row and recursively attempts to place queens in subsequent rows.- Base Case: If
rowequalsn, it means all queens are placed successfully, so we return1. - Recursive Case: Iterate through each column in the current row and check if placing a queen is valid. If valid, update the tracking lists and call
backtrackfor the next row. After the recursive call, backtrack by resetting the tracking lists.
- Start Backtracking:
- Call
backtrackstarting from the first row (row = 0).
- Call
This solution efficiently counts all distinct solutions to the n-queens problem using backtracking and ensures that each placement is valid by checking column, diagonal, and anti-diagonal constraints.
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @return {number}
*/
var totalNQueens = function(n) {
// Helper function to check if placing a queen at (row, col) is valid
const isValid = (row, col, cols, diagonals, antiDiagonals) => {
return !cols[col] && !diagonals[row - col + n - 1] && !antiDiagonals[row + col];
};
// Backtracking function to place queens
const backtrack = (row, cols, diagonals, antiDiagonals) => {
// If all queens are placed successfully
if (row === n) {
return 1;
}
let count = 0;
for (let col = 0; col < n; col++) {
if (isValid(row, col, cols, diagonals, antiDiagonals)) {
// Place the queen
cols[col] = true;
diagonals[row - col + n - 1] = true;
antiDiagonals[row + col] = true;
// Move to the next row
count += backtrack(row + 1, cols, diagonals, antiDiagonals);
// Remove the queen (backtrack)
cols[col] = false;
diagonals[row - col + n - 1] = false;
antiDiagonals[row + col] = false;
}
}
return count;
};
// Initialize arrays to track columns and diagonals
const cols = new Array(n).fill(false);
const diagonals = new Array(2 * n - 1).fill(false);
const antiDiagonals = new Array(2 * n - 1).fill(false);
// Start backtracking from the first row
return backtrack(0, cols, diagonals, antiDiagonals);
};Solution in Java:
Java
class Solution {
public int totalNQueens(int n) {
// Arrays to indicate whether a column, main diagonal or anti-diagonal is occupied
boolean[] cols = new boolean[n];
boolean[] diagonals = new boolean[2 * n - 1];
boolean[] antiDiagonals = new boolean[2 * n - 1];
return backtrack(0, cols, diagonals, antiDiagonals, n);
}
// Helper function to perform backtracking
private int backtrack(int row, boolean[] cols, boolean[] diagonals, boolean[] antiDiagonals, int n) {
// If all queens are placed successfully, return 1 as a valid solution
if (row == n) {
return 1;
}
int count = 0;
for (int col = 0; col < n; col++) {
if (isValid(row, col, cols, diagonals, antiDiagonals, n)) {
// Place the queen
cols[col] = true;
diagonals[row - col + n - 1] = true;
antiDiagonals[row + col] = true;
// Move to the next row
count += backtrack(row + 1, cols, diagonals, antiDiagonals, n);
// Remove the queen (backtrack)
cols[col] = false;
diagonals[row - col + n - 1] = false;
antiDiagonals[row + col] = false;
}
}
return count;
}
// Helper function to check if placing a queen at (row, col) is valid
private boolean isValid(int row, int col, boolean[] cols, boolean[] diagonals, boolean[] antiDiagonals, int n) {
return !cols[col] && !diagonals[row - col + n - 1] && !antiDiagonals[row + col];
}
}Solution in C#:
C#
public class Solution {
public int TotalNQueens(int n) {
// Arrays to indicate whether a column, main diagonal, or anti-diagonal is occupied
bool[] cols = new bool[n];
bool[] diagonals = new bool[2 * n - 1];
bool[] antiDiagonals = new bool[2 * n - 1];
return Backtrack(0, cols, diagonals, antiDiagonals, n);
}
// Helper function to perform backtracking
private int Backtrack(int row, bool[] cols, bool[] diagonals, bool[] antiDiagonals, int n) {
// If all queens are placed successfully, return 1 as a valid solution
if (row == n) {
return 1;
}
int count = 0;
for (int col = 0; col < n; col++) {
if (IsValid(row, col, cols, diagonals, antiDiagonals, n)) {
// Place the queen
cols[col] = true;
diagonals[row - col + n - 1] = true;
antiDiagonals[row + col] = true;
// Move to the next row
count += Backtrack(row + 1, cols, diagonals, antiDiagonals, n);
// Remove the queen (backtrack)
cols[col] = false;
diagonals[row - col + n - 1] = false;
antiDiagonals[row + col] = false;
}
}
return count;
}
// Helper function to check if placing a queen at (row, col) is valid
private bool IsValid(int row, int col, bool[] cols, bool[] diagonals, bool[] antiDiagonals, int n) {
return !cols[col] && !diagonals[row - col + n - 1] && !antiDiagonals[row + col];
}
}