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 + 1, c := j + 1

• 当r<board的行大小且c<board的列大小时，执行以下操作

  • 如果board[r，c]与1相同，则
    • 返回False
  • r := r + 1, c := c + 1

• r:= i + 1, c := j – 1

• 当r<board的行大小且c>=0时，执行以下操作

  • 如果board[r，c]与1相同，则
    • 返回False
  • r := r + 1, c := c – 1

• r := i – 1, c := j + 1

• 当r>=0且c<board的列大小时，执行以下操作

  • 如果board[r，c]与1相同，则
    • 返回False
  • r := r – 1, c := c + 1

• r := i – 1, c := j – 1

• 当r>=0且c>=0时，执行以下操作

  • 如果board[r，c]与1相同，则
    • 返回False
  • r := r – 1, c := 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

• 返回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