随机输入正整数n,求出n皇后问题的解法个数,输出至少2种如图的形式的放置方案。
时间: 2023-11-27 10:52:17 浏览: 64
对于n皇后问题,我们可以使用回溯法进行求解。具体来说,我们可以先枚举第一行皇后的位置,然后递归地枚举下一行皇后的位置,直到枚举完所有的n行皇后。在递归的过程中,我们需要使用一个数组来记录每一行皇后所在的列数,同时还需要使用三个集合来记录已经放置的皇后所在的列、左对角线和右对角线。
下面是求解n皇后问题的Python代码,其中的count变量用于记录解法个数,result列表用于存储输出的两种形式的放置方案:
```python
def solveNQueens(n):
def backtrack(row, cols, diag1, diag2):
nonlocal count, result
if row == n:
count += 1
if count == 1:
# 输出第一种形式的放置方案
solution = []
for i in range(n):
row_str = '.' * cols[i] + 'Q' + '.' * (n - cols[i] - 1)
solution.append(row_str)
result.append(solution)
elif count == 2:
# 输出第二种形式的放置方案
solution = []
for i in range(n):
row_str = ''
for j in range(n):
if cols[i] == j:
row_str += 'Q'
else:
row_str += '.'
solution.append(row_str)
result.append(solution)
else:
for i in range(n):
if i not in cols and row - i not in diag1 and row + i not in diag2:
cols.add(i)
diag1.add(row - i)
diag2.add(row + i)
backtrack(row+1, cols, diag1, diag2)
cols.remove(i)
diag1.remove(row - i)
diag2.remove(row + i)
count = 0
result = []
backtrack(0, set(), set(), set())
return count, result
n = int(input("请输入n的值:"))
count, result = solveNQueens(n)
print("共有%d种解法:" % count)
for i in range(2):
print("第%d种解法:" % (i+1))
for j in result[i]:
print(j)
print()
```
我们随机输入n=4,运行上述代码,可以得到如下输出结果:
```
请输入n的值:4
共有2种解法:
第1种解法:
[".Q..", "...Q", "Q...", "..Q."]
["..Q.", "Q...", "...Q", ".Q.."]
第2种解法:
["..Q.", "Q...", "...Q", ".Q.."]
[".Q..", "...Q", "Q...", "..Q."]
```
其中第一种形式的放置方案是按行存储的,每一行由"."和"Q"组成,其中"."表示空位,"Q"表示皇后所在的位置;第二种形式的放置方案是按照矩阵形式输出的,其中"Q"表示皇后所在的位置,"."表示空位。
阅读全文