Chương trình kiểm tra có thể điền ma phương Latin hay không trong Python

Cho ma trận n x n chứa giá trị 0 đến n (0 = ô trống). Kiểm tra có thể điền các ô trống sao cho mỗi hàng và mỗi cột chứa đúng một lần các số 1..n hay không (Latin Square).

Ví dụ: ma trận 3x3 với một số ô 0 → có thể điền thành Latin Square → True.

Giải thuật (Backtracking)

1. Hàm find_empty_cell: tìm ô giá trị 0, trả về hoặc .
2. Hàm : kiểm tra chưa có trong hàng và cột .
3. Hàm : kiểm tra ma trận đã đầy và mỗi hàng/cột là hoán vị của 1..n.
4. Hàm chính :
   • Tìm ô trống. Nếu không có: kiểm tra is_complete.
   • Thử điền vào ô trống nếu .
   • Đệ quy . Nếu thành công → .
   • Backtrack: đặt lại ô = 0.
   • Nếu hết số không thành công → .

Ví dụ minh họa

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))  # Output: True

Đầu vào

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

Đầu ra

True