資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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。
對於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次瀏覽
廣告