Chương trình kiểm tra có thể hoàn thành bài toán N-Queens từ bàn cờ cho trước trong Python

Cho ma trận nhị phân: 0 ô trống, 1 quân hậu đã đặt. Kiểm tra có thể đặt thêm hậu để thành lời giải N-Queens hợp lệ (không 2 hậu ăn nhau) hay không.

Ví dụ ma trận 5x5 với 3 hậu đã đặt → True (có thể bổ sung 2 hậu nữa).

Giải thuật (Backtracking lặp với Stack)

1. Hàm isSafe(board, i, j) kiểm tra ô (i,j) an toàn (không cùng hàng, cột, đường chéo với hậu khác).
2. Duyệt hàng r từ 0 đến n-1:
   • Nếu hàng đã có hậu → chuyển hàng sau.
   • Thử đặt hậu ở cột c đầu tiên an toàn. Đẩy (r,c) vào stack, đánh dấu board.
   • Nếu không tìm được cột an toàn: backtrack (pop stack, xóa hậu, thử cột sau).
   • Nếu stack rỗng khi backtrack → thất bại.
3. Nếu duyệt hết tất cả hàng → thành công.

Ví dụ minh họa

class Solution:
    def solve(self, board):
        def isSafe(board, i, j):
            n = len(board)
            # Kiểm tra cột
            for r in range(n):
                if r != i and board[r][j] == 1:
                    return False
            # 4 đường chéo
            for dr, dc in [(1,1), (1,-1), (-1,1), (-1,-1)]:
                r, c = i + dr, j + dc
                while 0 <= r < n and 0 <= c < n:
                    if board[r][c] == 1:
                        return False
                    r += dr; c += dc
            return True
        
        n = len(board)
        r = c = 0
        stack = []
        while r < n:
            if 1 in board[r]:
                r += 1
                continue
            found = False
            while c < n:
                if isSafe(board, r, c):
                    board[r][c] = 1
                    stack.append([r, c])
                    found = True
                    break
                c += 1
            if found:
                c = 0
                r += 1
            else:
                if not stack:
                    return False
                pr, pc = stack.pop()
                r, c = pr, pc + 1
                board[pr][pc] = 0
        return True

ob = Solution()
matrix = [[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,1,0]]
print(ob.solve(matrix))  # Output: True

Đầu vào / Đầu ra

Input: ma trận 5x5 như ví dụ

Output: True