n皇后问题如何用编程语言解决?
时间: 2024-10-07 11:01:10 浏览: 13
n皇后问题通常使用回溯法(Backtracking)来在编程中解决。以下是一个基本的Python代码示例:
```python
def solve_n_queens(n):
def is_valid(board, row, col):
# 检查行冲突、列冲突以及左上到右下的对角线冲突
for i in range(col):
if board[row][i] == 1 or \
board[i][col] == 1 or \
abs(row-i) == abs(col-board[col]):
return False
return True
def place_queen(board, row):
if row >= n:
solutions.append(list(board))
else:
for col in range(n):
if is_valid(board, row, col):
board[row][col] = 1
place_queen(board, row + 1)
board[row][col] = 0 # 回溯
solutions = []
board = [0] * n
place_queen(board, 0)
return solutions
# 调用函数并打印结果
n = 4 # 或者你想找的任意大小的棋盘
solutions = solve_n_queens(n)
for solution in solutions:
print(solution)
```
这段代码首先定义了一个内部函数`is_valid`用于验证位置是否合法,然后在`place_queen`函数中通过递归尝试将皇后放入每个空位,并在完成后回溯。最后,返回所有的解集。