Backtracking và cắt tỉa — Permutations, N-Queens, pruning

TL;DR: Backtracking là kỹ thuật tìm kiếm có hệ thống trên cây quyết định: ở mỗi bước chọn một lựa chọn (choose), đệ quy xuống sâu hơn (explore), rồi hoàn tác lựa chọn đó để thử lựa chọn khác (unchoose). Độ phức tạp lý thuyết tăng theo hàm mũ: O(n!) cho permutations, O(2ⁿ) cho subsets. Nhưng pruning (cắt tỉa sớm các nhánh chắc chắn không ra nghiệm hợp lệ) giảm mạnh thời gian chạy thực tế. N-Queens với n=8: cây vét cạn có ≈ 19 triệu node (8^8 ≈ 16,7 triệu cách đặt đủ 8 quân), nhưng nhờ pruning chỉ cần xét 2.057 node để tìm ra cả 92 nghiệm.

Đặt 8 quân hậu lên bàn cờ 8×8 sao cho không quân nào ăn nhau: duyệt vét cạn phải đi qua ≈ 19 triệu node, còn backtracking có cắt tỉa chỉ xét 2.057 node để tìm đủ cả 92 nghiệm. Cùng khung đó sinh mọi tổ hợp cấu hình để test, giải Sudoku hay chạy constraint solver. Bài này đi từ permutations và subsets tới N-Queens.

1. Hình dung: mê cung và dây len

Cứ hình dung bạn đi trong mê cung tối với một cuộn dây len. Ở mỗi ngã rẽ, bạn thả dây ra và đi theo một hướng. Gặp tường cụt thì kéo dây về, quay lại ngã rẽ và thử hướng khác. Tìm thấy lối ra là xong. Thử hết mọi hướng mà không thấy lối ra thì mê cung vô nghiệm.

Backtracking làm đúng như vậy.

2. Khung tổng quát: Choose → Explore → Unchoose

Backtrack(current_state, choices_remaining):
    if is_solution(current_state):
        record(current_state)    -- ghi nhận nghiệm
        return

    for each choice c trong choices_remaining:
        if is_valid(current_state, c):    -- constraint check (pruning)
            choose(current_state, c)      -- thêm c vào trạng thái hiện tại
            Backtrack(new_state, remaining_after_c)
            unchoose(current_state, c)    -- hoàn tác, thử lựa chọn tiếp theo

Time: O(mũ) worst case  Space: O(độ sâu của cây × chi phí mỗi node)

Ba bước cốt lõi:

• choose: đưa ra lựa chọn và cập nhật trạng thái
• explore: đệ quy xuống sâu hơn với trạng thái mới
• unchoose: hoàn tác lựa chọn, đưa trạng thái về như trước khi choose

Bước unchoose là điểm khác nhau giữa backtracking và DFS thông thường: nhờ nó, các nhánh khác nhau dùng lại được cùng một trạng thái mà không cần copy. Cơ chế "nhớ đường quay về" là hàm gọi hàm: mỗi lời gọi có biến riêng.