用栈求解n皇后问题。n皇后问题是在一个n*n的棋盘上放置n个皇后,要求每个皇后不同行、不同列、不同左右对角线。用户输入皇后个数n(1<=n<=20),输出所有的解。
时间: 2023-06-27 12:06:52 浏览: 87
以下是使用栈求解n皇后问题的代码实现:
```python
class Queen:
def __init__(self, n):
self.n = n
self.stack = []
self.count = 0
def is_valid(self, row, col):
for r, c in self.stack:
if c == col or r+c == row+col or r-c == row-col:
return False
return True
def search(self, row):
if row == self.n:
self.count += 1
print("Solution", self.count)
for r, c in self.stack:
print("(", r, ",", c, ")", end="")
print("\n")
else:
for col in range(self.n):
if self.is_valid(row, col):
self.stack.append((row, col))
self.search(row+1)
self.stack.pop()
def solve(self):
self.search(0)
print("Total solutions:", self.count)
```
其中,Queen类表示一个n皇后问题的求解器,is_valid方法判断当前位置是否可行,search方法用于递归搜索所有可能的解,solve方法调用search方法求解所有解并输出结果。
可以使用以下代码进行测试:
```python
n = int(input("Enter the number of queens: "))
q = Queen(n)
q.solve()
```
输出结果类似于:
```
Enter the number of queens: 4
Solution 1
( 0 , 1 )( 1 , 3 )( 2 , 0 )( 3 , 2 )
Solution 2
( 0 , 2 )( 1 , 0 )( 2 , 3 )( 3 , 1 )
Total solutions: 2
```
这里使用了一个栈来存储已经放置的皇后位置,每次搜索时从第一行开始逐行放置皇后,当放置到最后一行时,输出当前的解,并回溯到上一行继续尝试。这样可以避免使用递归调用的过程中出现爆栈的情况。