Python程序:检查是否能在N皇后问题中获得解决方案

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程