用 Python 编写程序检查是否可以填充正方形，其中每行和每列将容纳不同的元素
假设我们有一个 n × n 矩阵，其中包含从 0 到 n 的值。这里 0 表示未填充的正方形，我们必须检查是否可以填充空正方形，使得每行和每列中的每个数字从 1 到 n 都恰好出现一次。
因此，如果输入如下
| 0 | 0 | 2 |
| 2 | 0 | 1 |
| 1 | 2 | 3 |
那么输出将为 True，因为我们可以将矩阵设置为
| 3 | 1 | 2 |
| 2 | 3 | 1 |
| 1 | 2 | 3 |
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 find_empty_cell() 。这将采用矩阵 n
对于范围从 0 到 n 的 i，执行
对于范围从 0 到 n 的 j，执行
如果 matrix[i, j] 与 0 相同，则
return(i, j)
return(-1, -1)
定义一个函数 is_feasible() 。这将采用矩阵 i、j、x
如果 x 在矩阵的第 i 行，则
返回 False
如果 x 在矩阵任意行的第 j 列，则
返回 False
返回 True
定义一个函数 is_complete() 。这将获取矩阵 n
对于矩阵中的每一行，执行
如果行有一些重复元素，则
返回 False
对于范围从 0 到 n 的 col，执行
如果 col 有一些重复元素，则
返回 False
返回 True
从主方法执行以下操作 −
n := 矩阵的行数
(i, j) = find_empty_cell(matrix, n)
如果 (i, j) 与 (-1, -1) 相同，则
如果 is_complete(matrix, n) 为真，则
返回 True
否则，
返回 False
对于 1 到 n + 1 范围内的 x，执行
如果 is_feasible(matrix, i, j, x) 为真，则
matrix[i, j] := x
如果解决(矩阵)为真，则
返回 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
