Python程序：检查是否可以填充方阵，使得每行每列都包含不同的元素

假设我们有一个n × n矩阵，包含从0到n的值。其中0代表未填充的方格，我们需要检查是否可以填充空方格，使得每行和每列中每个数字从1到n都恰好出现一次。

例如，如果输入如下：

002
201
123

那么输出将是True，因为我们可以将矩阵设置为：

312
231
123

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

  • 定义一个函数`find_empty_cell()`。它将接收矩阵和n。

  • 对于i从0到n：

    • 对于j从0到n：

      • 如果`matrix[i, j]`等于0，则：

        • 返回(i, j)

  • 返回(-1, -1)

  • 定义一个函数`is_feasible()`。它将接收矩阵、i、j和x。

  • 如果x在矩阵的第i行中，则：

    • 返回False

  • 如果x在矩阵的第j列的任何一行中，则：

    • 返回False


  • 返回True

  • 定义一个函数`is_complete()`。它将接收矩阵和n。

  • 对于矩阵中的每一行：

    • 如果该行包含重复元素，则：

      • 返回False

    • 对于j从0到n：

      • 如果该列包含重复元素，则：

        • 返回False

    • 返回True

    • 在主方法中执行以下操作：

    • n := 矩阵的行数

    • (i, j) = `find_empty_cell(matrix, n)`

    • 如果(i, j)等于(-1, -1)，则：

      • 如果`is_complete(matrix, n)`为真，则：

        • 返回True

      • 否则：

        • 返回False

    • 对于x从1到n + 1：

      • 如果`is_feasible(matrix, i, j, x)`为真，则：

        • `matrix[i, j] := x`

        • 如果`solve(matrix)`为真，则：

          • 返回True

        • `matrix[i, j] := 0`

    • 返回False


让我们来看下面的实现来更好地理解：

示例

在线演示

class Solution:
   def solve(self, matrix):
      n = len(matrix)
      def find_empty_cell(matrix, n):
         for i in range(n):
            for j in range(n):
               if matrix[i][j] == 0:
                  return (i, j)
         return (-1, -1)
      def is_feasible(matrix, i, j, x):
         if x in matrix[i]:
            return False
         if x in [row[j] for row in matrix]:
            return False
         return True
      def is_complete(matrix, n):
         for row in matrix:
            if set(row) != set(range(1, n + 1)):
               return False
         for col in range(n):
            if set(row[col] for row in matrix) != set(range(1, n + 1)):
               return False
         return True
      (i, j) = find_empty_cell(matrix, n)

      if (i, j) == (-1, -1):
         if is_complete(matrix, n):
            return True
         else:
            return False
      for x in range(1, n + 1):
         if is_feasible(matrix, i, j, x):
            matrix[i][j] = x
            if self.solve(matrix):
               return True
            matrix[i][j] = 0
      return False
ob = Solution()
matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3]
]
print(ob.solve(matrix))

输入

matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3] ]

输出

True

更新于：2020年10月9日

42次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告