To solve this problem, we need to determine the number of ways to place n queens on an n×n chessboard such that no two queens attack each other. This is a classic backtracking problem where we explore all possible placements of queens while ensuring they do not conflict.
Approach
The key insight here is to use backtracking to explore valid queen placements row by row. For each row, we check if placing a queen in a specific column is safe. A queen is safe if:
- No other queen is in the same column.
- No other queen is on the same diagonal (both top-left to bottom-right and top-right to bottom-left).
We use three sets to track:
used_cols: Columns that already have a queen.used_diag1: Diagonals of the formrow - column(top-left to bottom-right).used_diag2: Diagonals of the formrow + column(top-right to bottom-left).
The backtracking function recursively places queens row by row. When we reach the n-th row (all queens are placed), we increment the count of valid configurations.
Solution Code
n = int(input())
def count_n_queens(n):
count = 0
used_cols = set()
used_diag1 = set() # Tracks row - column
used_diag2 = set() # Tracks row + column
def backtrack(row):
nonlocal count
if row == n:
count += 1
return
for col in range(n):
d1 = row - col
d2 = row + col
if col not in used_cols and d1 not in used_diag1 and d2 not in used_diag2:
# Place the queen
used_cols.add(col)
used_diag1.add(d1)
used_diag2.add(d2)
# Move to the next row
backtrack(row + 1)
# Backtrack: remove the queen
used_cols.remove(col)
used_diag1.remove(d1)
used_diag2.remove(d2)
backtrack(0)
return count
print(count_n_queens(n))
Explanation
- Initialization: We start with empty sets to track used columns and diagonals, and a count of valid configurations set to 0.
- Backtracking Function: For each row, we try placing a queen in each column. If the column and both diagonals are unused, we place the queen and move to the next row.
- Base Case: When we reach the
n-th row (all queens are placed), we increment the count of valid configurations. - Backtrack: After exploring all possibilities for a given placement, we remove the queen from the current column and diagonals to try other placements.
This approach efficiently explores all valid configurations using backtracking, ensuring we only consider safe placements. The time complexity is O(n!) in the worst case, but the use of sets for tracking conflicts makes the solution efficient enough for small values of n (up to 12, which has 14200 valid configurations).
Example Output:
- For
n=4, the output is2. - For
n=5, the output is10. - For
n=8, the output is92.
This solution correctly computes the number of valid non-attacking queen placements for any positive integer n.


作者声明:本文包含人工智能生成内容。