Python程序检查N皇后问题是否有解

假设我们有一个二进制矩阵，其中0表示空单元格，1表示该单元格上的棋子皇后。我们需要检查是否可以填充此棋盘并获得有效的n皇后解。众所周知，n皇后问题要求在n×n棋盘上放置n个皇后，使得任何两个皇后都不能相互攻击。

因此，如果输入类似于

10000
00000
00001
00000
00010

则输出将为True，因为其中一个解类似于-

10000
00100
00001
01000
00010

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个函数isSafe()。它将接收棋盘、i、j作为参数

  • 对于r从0到棋盘大小，执行

    • 如果r不等于i且board[r, j]等于1，则

      • 返回False

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

  • 当r < 棋盘行数且c < 棋盘列数时，执行

    • 如果board[r, c]等于1，则

      • 返回False

    • r := r + 1, c := c + 1

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

  • 当r < 棋盘行数且c >= 0时，执行

    • 如果board[r, c]等于1，则

      • 返回False

    • r := r + 1, c := c - 1

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

  • 当r >= 0且c < 棋盘列数时，执行

    • 如果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[r]中存在1，则

      • r := r + 1

      • 进入下一轮迭代

    • 否则，

      • found := False

      • 当c < 棋盘列数时，执行

        • 如果isSafe(board, r, c)为真，则

          • board[r, c] := 1

          • 将[r, c]插入栈中

          • found := True

          • 退出循环

        • c := c + 1

      • 如果found为真，则

        • c := 0, r := r + 1

      • 否则，

        • 如果栈为空，则

          • 返回False

        • m := 从栈中删除顶部元素

        • r := m[0], c := m[1] + 1

        • board[r, c - 1] := 0

  • 返回True

示例

让我们看看以下实现以更好地理解-

实时演示

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

更新于: 2020年12月22日

181 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习
广告