Python程序:检查是否能在N皇后问题中获得解决方案
假设我们有一个二进制矩阵,其中0表示空单元格,1表示该单元格上有国际象棋皇后。我们需要检查是否可以填充此棋盘并获得有效的N皇后问题解决方案。正如我们所知,N皇后难题要求在一个N×N的棋盘上放置N个皇后,以使得任何两个皇后之间都不会相互攻击。
因此,如果输入如下所示:
1 | 0 | 0 | 0 | 0 |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 | 0 |
那么输出将为True,因为一个解决方案是 −
1 | 0 | 0 | 0 | 0 |
---|---|---|---|---|
0 | 0 | 1 | 0 | 0 |
0 | 0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 0 |
0 | 0 | 0 | 1 | 0 |
要解决此问题,我们将遵循以下步骤-
- 定义isSafe()函数。这将接收board、i、j。
-
对于r在范围0到board的大小,执行以下操作
- 如果r不同于i并且board[r,j]与1相同,则
- 返回False
- 如果r不同于i并且board[r,j]与1相同,则
- r := i + 1, c := j + 1
-
当r<board的行大小且c<board的列大小时,执行以下操作
- 如果board[r,c]与1相同,则
- 返回False
- r := r + 1, c := c + 1
- 如果board[r,c]与1相同,则
-
r:= i + 1, c := j – 1
-
当r<board的行大小且c>=0时,执行以下操作
- 如果board[r,c]与1相同,则
- 返回False
- r := r + 1, c := c – 1
- 如果board[r,c]与1相同,则
-
r := i – 1, c := j + 1
-
当r>=0且c<board的列大小时,执行以下操作
- 如果board[r,c]与1相同,则
- 返回False
- r := r – 1, c := c + 1
- 如果board[r,c]与1相同,则
-
r := i – 1, c := j – 1
-
当r>=0且c>=0时,执行以下操作
- 如果board[r,c]与1相同,则
- 返回False
- r := r – 1, c := c – 1
- 如果board[r,c]与1相同,则
-
返回True
-
从主方法执行以下操作−
-
r := 0, c := 0
-
stack :=一个新堆栈
-
当r<board的行大小时,执行以下操作
- 如果1在board[r]中,则
- r := r + 1
-
继续下一次迭代
-
否则,
- found := False
-
当c<board的列大小时,执行以下操作
-
如果isSafe(board,r,c)为true,则
- board[r,c] := 1
-
将[r,c]插入栈中
-
found := True
-
退出循环
-
c :=c + 1
-
如果found为true,则
-
c := 0,r := r + 1
-
否则,
-
如果堆栈为空,则
- 返回False
- m:=从堆栈中删除顶部元素
-
r := m [0],c:= m [1] + 1
-
board [r,c-1]:= 0
- 如果1在board[r]中,则
-
返回True
更多Python相关文章,请阅读:Python 教程
示例
让我们看下面的实现以更好地理解−
class Solution:
def solve(self, board):
def isSafe(board, i, j):
for r in range(len(board)):
if r != i and board[r][j] == 1:
return False
r, c = i + 1, j + 1
while r < len(board) and c < len(board[0]):
if board[r][c] == 1:
return False
r += 1
c += 1
r, c = i + 1, j - 1
while r < len(board) and c >= 0:
if board[r][c] == 1:
return False
r += 1
c -= 1
r, c = i - 1, j + 1
while r >= 0 and c < len(board[0]):
if board[r][c] == 1:
return False
r -= 1
c += 1
r, c = i - 1, j - 1
while r >= 0 and c >= 0:
if board[r][c] == 1:
return False
r -= 1
c -= 1
return True
r = c = 0
stack = []
while r < len(board):
if 1 in board[r]:
r += 1
continue
else:
found = False
while c < len(board[0]):
if isSafe(board, r, c):
board[r][c] = 1
stack.append([r, c])
found = True
break
c += 1
if found:
c = 0
r += 1
else:
if not stack:
return False
m = stack.pop()
r, c = m[0], m[1] + 1
board[r][c - 1] = 0
return True
ob = Solution()
matrix = [
[1, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0]
]
print(ob.solve(matrix))
输入
[ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1],
[0, 0, 0, 0, 0], [0, 0, 0, 1, 0] ]
输出
True