程序检查我们是否可以在Python中获得N个皇后解决方案

假设我们有一个二进制矩阵，其中0表示空单元格，而1表示该单元格的国际象棋皇后。我们必须检查是否可以填充此板并获得有效的nqueen解决方案。众所周知，n个皇后难题要求将n个皇后放置在n×n棋盘上，以便没有两个国际象棋皇后可以互相攻击。

所以，如果输入像

那么输出将为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