Python程序：检查棋盘是否为有效的N皇后解

假设我们有一个n x n矩阵代表一个棋盘。其中一些元素为1，一些元素为0，其中1代表皇后，0代表空单元格。我们必须检查该棋盘是否为N皇后问题的有效解。众所周知，如果棋盘上任意两个皇后都不能互相攻击，则该棋盘为有效的N皇后解。

因此，如果输入如下所示：

则输出为True

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

  • n := 矩阵的行数
  • rows := 一个新的集合，cols := 一个新的集合，diags := 一个新的集合，rev_diags := 一个新的集合
  • 对于范围0到n内的i：
    • 对于范围0到n内的j：
      • 如果matrix[i, j]为1，则：
        • 将i插入rows
        • 将j插入cols
        • 将(i - j)插入diags
        • 将(i + j)插入rev_diags
  • 如果rows的大小、cols的大小、diags的大小和rev_diags的大小都等于n，则返回true，否则返回false。

让我们来看下面的实现，以便更好地理解。

示例

在线演示

class Solution:
   def solve(self, matrix):
      n = len(matrix)

      rows = set()
      cols = set()
      diags = set()
      rev_diags = set()

      for i in range(n):
         for j in range(n):
            if matrix[i][j]:
               rows.add(i)
               cols.add(j)
               diags.add(i - j)
               rev_diags.add(i + j)

      return len(rows) == len(cols) == len(diags) == len(rev_diags) == n

ob = Solution()
matrix = [
   [0, 0, 0, 1, 0],
   [0, 1, 0, 0, 0],
   [0, 0, 0, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0]
]
print(ob.solve(matrix))

输入

matrix = [    
   [0, 0, 0, 1, 0],    
   [0, 1, 0, 0, 0],    
   [0, 0, 0, 0, 1],    
   [0, 0, 1, 0, 0],    
   [1, 0, 0, 0, 0]
]

输出

True

更新于：2020年11月26日

749 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告