Chương trình kiểm tra bàn cờ N-Queens có hợp lệ không bằng Python

Cho ma trận n×n (1: hậu, 0: trống). Kiểm tra xem có phải lời giải N-Queens hợp lệ (không có 2 hậu tấn công nhau) hay không.

Ví dụ: ma trận 5x5 cho trước → True.

Giải thuật

• Duyệt ma trận, với mỗi ô giá trị 1:
• Thêm hàng vào tập rows, cột vào cols, đường chéo chính i-j vào diags, đường chéo phụ i+j vào rev_diags.
• Hợp lệ khi kích thước 4 tập hợp đều bằng n (mỗi hàng, cột, đường chéo chỉ có 1 hậu).

Ví dụ minh họa

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        rows = set()
        cols = set()
        diags = set()
        rev_diags = set()
        for i in range(n):
            for j in range(n):
                if matrix[i][j]:
                    rows.add(i)
                    cols.add(j)
                    diags.add(i - j)
                    rev_diags.add(i + j)
        return len(rows) == len(cols) == len(diags) == len(rev_diags) == n

ob = Solution()
matrix = [
    [0,0,0,1,0],
    [0,1,0,0,0],
    [0,0,0,0,1],
    [0,0,1,0,0],
    [1,0,0,0,0]
]
print(ob.solve(matrix))

Đầu vào

matrix = [[0,0,0,1,0], [0,1,0,0,0], [0,0,0,0,1], [0,0,1,0,0], [1,0,0,0,0]]

Đầu ra

True