0에서 n까지의 값을 포함하는 하나의 n × 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에 대해 수행
-
행렬[i, j]가 0과 같으면
-
리턴(i,j)
-
-
-
-
리턴(-1, -1)
-
is_feasible() 함수를 정의합니다. 이것은 행렬 i, j, x
를 취합니다. -
행렬의 i번째 행에 x이면
-
거짓을 반환
-
-
행렬의 임의의 행에서 j번째 열의 x이면
-
거짓을 반환
-
-
참을 반환
-
is_complete() 함수를 정의합니다. 행렬이 필요합니다. n
-
행렬의 각 행에 대해 수행
-
행에 중복 요소가 있는 경우
-
거짓을 반환
-
-
범위 0에서 n까지의 col에 대해 수행
-
col에 중복 요소가 있으면
-
거짓을 반환
-
-
-
참을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
n :=행렬의 행 수
-
(i, j) =find_empty_cell(행렬, n)
-
(i, j)가 (-1, -1)과 같으면
-
is_complete(matrix, n)이 참이면
-
참을 반환
-
-
그렇지 않으면
-
거짓을 반환
-
-
-
범위 1에서 n + 1까지의 x에 대해 수행
-
is_feasible(matrix, i, j, x)이 참이면
-
행렬[i, j] :=x
-
solve(matrix)가 참이면
-
참을 반환
-
-
행렬[i, j] :=0
-
-
-
거짓을 반환
-
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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