程序检查是否可以在每个行和列将容纳Python中不同元素的正方形上填充

假设我们有一个n×n矩阵，包含从0到n的值。这里0代表一个未填充的正方形，我们必须检查是否可以填充空的正方形，以便在每一行和每一列中，从1到n的每个数字都恰好出现一次。

所以，如果输入像

然后输出将为True，因为我们可以将矩阵设置为

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

• 定义一个函数find_empty_cell()。这将采用矩阵n

• 对于0到n范围内的i，执行

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

• 返回(i,j)

• 对于0到n范围内的j，执行

• return(-1,-1)

• 定义一个函数is_feasible()。这将采用矩阵i，j，x

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

• 返回False

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

• 返回False

  
  

• 返回True

• 定义一个函数is_complete()。这将采用矩阵n

• 对于矩阵中的每一行，执行

• 如果is_feasible(matrix,i,j,x)为true，则

• 返回True

• 矩阵[i，j]：= x

• 如果solve（矩阵）为真，则

• 矩阵[i，j]：= 0

• 如果is_complete(matrix,n)为true，则

• 除此以外，

• 返回True

• 返回False

• 如果col有一些重复的元素，则

• 返回False

• 返回False

• 如果行中有一些重复的元素，则

• 对于0到n范围内的col，请执行

• 返回True

• 从主要方法中执行以下操作-

• n：=矩阵的行数

• (i,j)= find_empty_cell（矩阵，n）

• 如果(i,j)与(-1,-1)相同，则

• 对于x范围从1到n + 1，

• 返回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