N-Queen II Problem
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:
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle:
[
[“.Q..”,
“…Q”,
“Q…”,
“..Q.”],
[“..Q.”,
“Q…”,
“…Q”,
“.Q..”]
]Input: n = 1
Output: 1
Explanation:
There is only one solution to the 1-queen puzzle:
[
[“Q”]
]
Approach: To solve the problem, follow the below idea:
To solve the problem, we can use backtracking. The idea is to place a queen in each row and recursively check if this placement is valid. If it is, we move to the next row and continue placing queens until all queens are placed on the board. If a conflict is found, we backtrack by removing the queen and trying the next possible position.
Step-by-step Algorithm:
- Create arrays to track columns and diagonals that are under attack.
- Recursive Backtracking Function:
- If all rows are processed, increment the solution count.
- For each column in the current row, check if placing a queen is valid.
- If valid, place the queen and mark the column and diagonals as attacked.
- Recur to place a queen in the next row.
- Backtrack by removing the queen and unmarking the attacked columns and diagonals.
- Validation:
- A position is valid if the column and both diagonals are not under attack.
Below is the implementation of the above algorithm:
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
// Arrays to mark the unsafe column, primary diagonal
// and secondary diagonal on the board
bool isCol[10], isPrimary[20], isSecondary[20];
int solve(int rowNo, int n)
{
// If we have reached the end of board, then we have
// placed n queens correctly
if (rowNo == n) {
return 1;
}
int ans = 0;
// Iterate over all the columns of row = currRow
for (int colNo = 0; colNo < n; colNo++) {
// Check if it safe to place the queen in this
// column
if (!isCol[colNo] && !isPrimary[rowNo + colNo]
&& !isSecondary[rowNo - colNo + 10]) {
// Mark the column, primary and secondary
// diagonal as unsafe
isCol[colNo] = isPrimary[rowNo + colNo]
= isSecondary[rowNo - colNo + 10]
= true;
// Add all the possible solutions to ans
ans += solve(rowNo + 1, n);
// Mark the column, primary and secondary
// diagonal as safe
isCol[colNo] = isPrimary[rowNo + colNo]
= isSecondary[rowNo - colNo + 10]
= false;
}
}
return ans;
return ans;
}
// Function to count the number of ways to place n
// queens on nxn board
int totalNQueens(int n)
{
// base cases
if (n == 1)
return 1;
if (n <= 3)
return 0;
return solve(0, n);
}
};
// Example usage
int main()
{
Solution solution;
cout << solution.totalNQueens(4) << endl;
return 0;
}
import java.util.HashSet;
import java.util.Set;
public class Solution {
public int totalNQueens(int n)
{
return solve(0, n, new HashSet<>(), new HashSet<>(),
new HashSet<>());
}
private int solve(int row, int n, Set<Integer> cols,
Set<Integer> diags1,
Set<Integer> diags2)
{
if (row == n)
return 1;
int count = 0;
for (int col = 0; col < n; ++col) {
int diag1 = row - col;
int diag2 = row + col;
if (!cols.contains(col)
&& !diags1.contains(diag1)
&& !diags2.contains(diag2)) {
cols.add(col);
diags1.add(diag1);
diags2.add(diag2);
count += solve(row + 1, n, cols, diags1,
diags2);
cols.remove(col);
diags1.remove(diag1);
diags2.remove(diag2);
}
}
return count;
}
public static void main(String[] args)
{
Solution solution = new Solution();
System.out.println(
solution.totalNQueens(4)); // Output: 2
}
}
def totalNQueens(n):
def solve(row, cols, diags1, diags2):
if row == n:
return 1
count = 0
for col in range(n):
diag1 = row - col
diag2 = row + col
if col not in cols and diag1 not in diags1 and diag2 not in diags2:
count += solve(row + 1, cols | {col}, diags1 | {diag1}, diags2 | {diag2})
return count
return solve(0, set(), set(), set())
# Example usage
print(totalNQueens(4))
// Function to calculate the total number of solutions for the N-Queens problem
function totalNQueens(n) {
// Recursive function to solve the N-Queens problem
function solve(row, cols, diags1, diags2) {
// Base case: All queens are placed
if (row === n) {
return 1;
}
let count = 0;
// Iterate over each column in the current row
for (let col = 0; col < n; col++) {
// Calculate the diagonal positions
const diag1 = row - col;
const diag2 = row + col;
// Check if placing a queen at the current position is valid
if (!cols.has(col) && !diags1.has(diag1) && !diags2.has(diag2)) {
// Recursively call solve for the next row with updated sets of columns
// and diagonals
count += solve(row + 1, new Set(cols).add(col), new Set(diags1).add(diag1), new Set(diags2).add(diag2));
}
}
return count;
}
// Start the recursive backtracking process from the first row
return solve(0, new Set(), new Set(), new Set());
}
// Example usage
console.log(totalNQueens(4)); // Output the total number of solutions for N=4
// This code is contributed by Shivam Gupta
Output
2
Time Complexity: O(N!), where N is the number of queens (or the size of the board). This is because in the worst case, the algorithm tries all permutations of queen placements.
Auxiliary Space: O(N), due to the recursive call stack and the space required to store the columns and diagonals information.