1. Problem Statement (Simple Explanation):
Same puzzle as N-Queens (problem 51):
Place n queens on an n x n chessboard so that no two queens attack each other:
Not in the same row
Not in the same column
Not on the same diagonal
But now:
Instead of returning all boards, you must return the number of distinct solutions.
2. Examples:
Example 1:
Input:
n = 4
There are exactly 2 valid configurations (same as problem 51’s example).
Output: 2
Example 2:
Input:
n = 1
Only one way to place a queen on 1x1 board.
Output: 1
3. Approach – Backtracking with Column & Diagonal Constraints:
This is almost identical to N-Queens (51), but we:
Don’t need to build the actual board strings.
Only need a counter of valid placements.
We still:
Place queens row by row.
Use three boolean arrays to track attacked lines:
colUsed[c] – column c is under attack.
diag1Used[row - col + n - 1] – main diagonal (top-left to bottom-right).
diag2Used[row + col] – anti-diagonal (top-right to bottom-left).
Whenever we reach row == n, we found one valid configuration → increment count.
Diagonal Indexing Recap:
For n x n board:
Main diagonal index: d1 = row - col + (n - 1) → range [0..2n-2].
Anti-diagonal index: d2 = row + col → range [0..2n-2].
So diag1Used and diag2Used are size 2n - 1.
Algorithm (Step-by-Step):
Initialize:
count = 0
colUsed[n], diag1Used[2n-1], diag2Used[2n-1] → all false.
Backtrack function dfs(row):
If row == n:
count++
return.
For each column c in 0..n-1:
d1 = row - c + n - 1
d2 = row + c
If any of colUsed[c], diag1Used[d1], diag2Used[d2] is true → skip.
Otherwise:
Set them to true (place queen).
Recurse dfs(row + 1).
Set them back to false (backtrack).
Call dfs(0) and return count.
Pseudo-code:
Same backtracking nature as N-Queens:
Time: Exponential in n, but n <= 9 is small enough.
Space: O(n) for recursion depth + constant-sized arrays (O(n) each).
4. Java code:
7. JavaScript code:
8. C (outline) code:
In C you would:
Define bool colUsed[9], bool diag1Used[17], bool diag2Used[17], int count.
Implement dfs(row, n) similarly, updating and restoring booleans.
Return count.
Given n <= 9, fixed-size arrays are easy to use.
For brevity, full C code is omitted, but logic is identical to C++ with manual management of global or struct state.
Comments
Post a Comment