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: tại 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 là mũ — O(n!) cho permutations, O(2ⁿ) cho subsets — nhưng pruning (cắt tỉa sớm các nhánh không thể cho nghiệm hợp lệ) giảm mạnh thời gian thực tế. N-Queens với n=20 có khoảng 10²⁶ node lý thuyết nhưng pruning giúp tìm tất cả nghiệm trong vài phút.

Năm 2016, AlphaGo đánh bại Lee Sedol 4-1. Một trong những kỹ thuật cốt lõi mà AlphaGo thay thế là brute-force tree search của cờ vây — không gian trạng thái cờ vây là 10¹⁷⁰, không thể enumerate hết. Alpha-beta pruning (phiên bản backtracking nâng cao) cho phép AI cắt bỏ phần lớn cây tìm kiếm mà không cần xét. Trước khi đến AlphaGo, hãy hiểu nguyên lý backtracking cơ bản — bắt đầu từ permutations và N-Queens.

1. Analogy — Mê cung và dây len

Hãy tưởng tượng bạn đi trong mê cung tối với một cuộn dây len. Tại mỗi ngã rẽ, bạn thả một đầu dây và đi theo một hướng. Nếu gặp tường cụt, bạn kéo dây về, quay lại ngã rẽ, thử hướng khác. Khi tìm thấy lối ra, bạn thành công. Khi đã thử hết mọi hướng mà không tìm được — mê cung vô nghiệm.

Backtracking là chính xác thuật toán đó:

• Dây len = call stack đệ quy — biết cách quay về đúng trạng thái trước
• Ngã rẽ = điểm quyết định — chọn phần tử nào tiếp theo
• Tường cụt = constraint violation — trạng thái này không thể cho nghiệm hợp lệ
• Pruning = nhận ra tường cụt sớm — không đi sâu vào ngõ cụt, quay lại ngay

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(depth của cây × overhead mỗi node)

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

• choose: thực hiện lựa chọn, 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, khôi phục trạng thái như trước choose

Bước unchoose là điểm phân biệt backtracking với DFS đơn giản — nó cho phép tái sử dụng cùng trạng thái qua các nhánh khác nhau mà không cần copy.

3. Permutations — tất cả hoán vị của mảng

Bài toán: cho mảng n phần tử phân biệt, liệt kê tất cả n! hoán vị.

Permutations(A[], current_perm, used[]):
    if current_perm.length = A.length:
        output current_perm    -- hoán vị hoàn chỉnh
        return

    for i <- 0 đến A.length - 1:
        if not used[i]:
            used[i] <- true           -- choose: đánh dấu A[i] đã dùng
            current_perm.push(A[i])
            Permutations(A, current_perm, used)
            current_perm.pop()        -- unchoose: bỏ A[i] khỏi perm
            used[i] <- false          -- unchoose: trả A[i] về "chưa dùng"

Time: O(n × n!)  Space: O(n)

Trace với A = [1, 2, 3]:

graph TD
    ROOT["[ ]"] --> P1["[1]"]
    ROOT --> P2["[2]"]
    ROOT --> P3["[3]"]

    P1 --> P12["[1,2]"]
    P1 --> P13["[1,3]"]
    P2 --> P21["[2,1]"]
    P2 --> P23["[2,3]"]
    P3 --> P31["[3,1]"]
    P3 --> P32["[3,2]"]

    P12 --> P123["[1,2,3] ✓"]
    P13 --> P132["[1,3,2] ✓"]
    P21 --> P213["[2,1,3] ✓"]
    P23 --> P231["[2,3,1] ✓"]
    P31 --> P312["[3,1,2] ✓"]
    P32 --> P321["[3,2,1] ✓"]

6 hoán vị = 3! = 6. Mỗi node là một lựa chọn, mỗi leaf là một permutation hoàn chỉnh.

4. Subsets — tất cả tập con

Bài toán: cho mảng n phần tử phân biệt, liệt kê tất cả 2ⁿ tập con.

Subsets(A[], index, current_subset):
    output current_subset    -- mọi trạng thái đều là một tập con hợp lệ

    for i <- index đến A.length - 1:
        current_subset.push(A[i])    -- choose: thêm A[i]
        Subsets(A, i + 1, current_subset)
        current_subset.pop()         -- unchoose: bỏ A[i]
        -- không thêm A[i], tiếp tục với i+1 (implicit trong vòng for)

Time: O(n × 2^n)  Space: O(n)

Với A = [1, 2, 3]: 8 tập con = 2³. Tại mỗi bước, ta có hai lựa chọn ẩn: lấy hoặc không lấy phần tử hiện tại — cây nhị phân có 2ⁿ lá.

5. N-Queens — backtracking có pruning

5.1 Bài toán

Đặt N quân hậu trên bàn cờ N×N sao cho không quân nào tấn công quân khác (không cùng hàng, cột, đường chéo).

5.2 Thuật toán có pruning

NQueens(n, row, col_used[], diag1_used[], diag2_used[], board[]):
    -- col_used[c]: cột c đã có quân hậu chưa
    -- diag1_used[r-c+n]: đường chéo chính đã có chưa (r-c hằng số)
    -- diag2_used[r+c]: đường chéo phụ đã có chưa (r+c hằng số)

    if row = n:
        output board    -- đặt xong N hàng, tìm được nghiệm
        return

    for col <- 0 đến n-1:
        if not col_used[col]
           and not diag1_used[row - col + n]
           and not diag2_used[row + col]:
            -- PRUNING: skip nếu conflict, không đệ quy vào

            board[row] <- col
            col_used[col] <- true
            diag1_used[row - col + n] <- true
            diag2_used[row + col] <- true
            -- choose: đặt quân hậu ở (row, col)

            NQueens(n, row + 1, col_used, diag1_used, diag2_used, board)
            -- explore: xét hàng tiếp theo

            board[row] <- -1
            col_used[col] <- false
            diag1_used[row - col + n] <- false
            diag2_used[row + col] <- false
            -- unchoose: rút quân hậu khỏi (row, col)

Time: O(n!) worst case, thực tế tốt hơn nhiều nhờ pruning
Space: O(n)

5.3 Cây quyết định với nhánh bị cắt (N = 4)

graph TD
    ROOT["Hàng 0"]

    ROOT --> C0["Cột 0"]
    ROOT --> C1["Cột 1"]
    ROOT --> C2["Cột 2"]
    ROOT --> C3["Cột 3"]

    C0 --> C0_R1_0["Cột 0 ✗ (conflict)"]
    C0 --> C0_R1_1["Cột 1 ✗ (diag)"]
    C0 --> C0_R1_2["Cột 2"]
    C0 --> C0_R1_3["Cột 3"]

    C0_R1_2 --> C0_R2_0["Cột 0 ✗"]
    C0_R1_2 --> C0_R2_1["Cột 1 ✗"]
    C0_R1_2 --> C0_R2_2["Cột 2 ✗"]
    C0_R1_2 --> C0_R2_3["Cột 3 ✗"]

    C0_R1_3 --> C0R1_3a["Cột 0 ✗"]
    C0_R1_3 --> C0R1_3b["Cột 1 ✓ nghiệm!"]
    C0R1_3b --> SOL1["[1,3,0,2] ✓"]

    C1 --> C1_skip["..."]
    C2 --> C2_sol["... → [2,0,3,1] ✓"]
    C3 --> C3_skip["... tất cả bị cắt"]

    style C0_R1_0 fill:#ff9999
    style C0_R1_1 fill:#ff9999
    style C0_R2_0 fill:#ff9999
    style C0_R2_1 fill:#ff9999
    style C0_R2_2 fill:#ff9999
    style C0_R2_3 fill:#ff9999
    style C0R1_3a fill:#ff9999
    style C3_skip fill:#ff9999
    style SOL1 fill:#99ff99
    style C2_sol fill:#99ff99

Node đỏ là nhánh bị cắt (pruning), node xanh là nghiệm. N=4 có 2 nghiệm: [1,3,0,2] và [2,0,3,1].

5.4 Tại sao pruning hiệu quả với N-Queens

Không có pruning: cây có N^N = 4^4 = 256 node. Với pruning: thực tế chỉ xét khoảng 8-12 node. Hiệu quả tăng theo cấp số nhân khi N lớn.

Với N=8: 8^8 = 16,7 triệu nodes lý thuyết, nhưng chỉ 92 nghiệm và thuật toán chỉ xét vài nghìn nodes nhờ pruning cột + chéo. Với N=20: lý thuyết khoảng 10²⁶ nodes (20^20), thực tế tìm được 39,029,188,884 nghiệm trong vài phút.

6. Phân tích độ phức tạp

6.1 Worst case lý thuyết

6.2 Pruning — hiệu quả thực tế

Pruning không thay đổi worst-case complexity nhưng cắt đáng kể constant factor và average case.

Forward checking (N-Queens variant): không chỉ check conflict tại node hiện tại, mà track trước: "nếu đặt quân hậu ở đây, có bao nhiêu ô còn hợp lệ ở hàng tiếp theo?" Nếu có hàng nào không còn ô hợp lệ → cắt ngay, không cần đệ quy.

Constraint propagation: khi đặt một giá trị, lan truyền constraint để loại giá trị không hợp lệ từ các ô khác. Sudoku solver mạnh dùng arc consistency (AC-3) — cắt hàng chục nghìn node cho mỗi giá trị được đặt.

Pruning strategies (từ yếu đến mạnh):

1. Basic validity: check conflict ngay khi chọn
   -- chỉ cắt node vi phạm
   Time: O(1) per node

2. Forward checking: project conflict vào tương lai
   -- cắt sớm hơn
   Time: O(n) per node

3. Constraint propagation (AC-3):
   -- lan truyền xâu chuỗi, cắt rất sớm
   Time: O(n² × d) per propagation, d = domain size

Tradeoff: pruning mạnh hơn → cắt nhiều hơn nhưng overhead per node lớn hơn.

7. Pitfall — Forget unchoose

-- BUG: quên unchoose → trạng thái bị "nhiễm" giữa các nhánh

Permutations_WRONG(A[], current_perm, used[]):
    if current_perm.length = A.length:
        output current_perm
        return

    for i <- 0 đến A.length - 1:
        if not used[i]:
            used[i] <- true
            current_perm.push(A[i])
            Permutations_WRONG(A, current_perm, used)
            -- THIẾU: current_perm.pop() và used[i] <- false
            -- Hậu quả: sau khi explore nhánh [1,2,...],
            -- current_perm vẫn chứa [1,2,...] khi thử nhánh [1,3,...]
            -- → output sai hoàn toàn

Time: O(?)  Space: O(?)  -- output không xác định

-- CORRECT: luôn unchoose sau explore

Permutations(A[], current_perm, used[]):
    if current_perm.length = A.length:
        output current_perm
        return

    for i <- 0 đến A.length - 1:
        if not used[i]:
            used[i] <- true
            current_perm.push(A[i])          -- choose
            Permutations(A, current_perm, used)  -- explore
            current_perm.pop()               -- unchoose ← KHÔNG THIẾU
            used[i] <- false                 -- unchoose ← KHÔNG THIẾU

Time: O(n × n!)  Space: O(n)

Invariant: khi hàm Backtrack return, trạng thái phải giống hệt trước khi gọi hàm. Unchoose đảm bảo invariant này.

8. Liên hệ các bài khác

• Greedy: Khi backtracking quá chậm và greedy không đảm bảo tối ưu, cần lựa chọn có căn cứ. Hiểu cả ba — greedy/DP/backtracking — giúp nhận diện bài toán nào dùng approach nào.
• 0/1 Knapsack: Knapsack dùng DP vì overlapping subproblems cho phép reuse. Nhưng nếu cần liệt kê tất cả tập items đạt value tối ưu (không chỉ một nghiệm), backtracking là phương pháp tự nhiên — DP chỉ cho một nghiệm.
• DFS: Backtracking là DFS trên cây quyết định với khả năng undo. DFS trên graph cũng có thể có backtracking component (visited set đóng vai trò constraint). Hai kỹ thuật có cùng skeleton đệ quy, chỉ khác về cấu trúc dữ liệu và undo.
• Đệ quy và call stack: Backtracking phụ thuộc hoàn toàn vào call stack để "nhớ" trạng thái quay về. Hiểu stack frame và recursion depth giúp tránh stack overflow và ước tính space complexity.

9. Deep Dive

10. Tóm tắt

• Backtracking = DFS + undo: khám phá cây quyết định đệ quy, hoàn tác mỗi lựa chọn sau khi explore để thử lựa chọn khác. Invariant: trạng thái sau return = trạng thái trước call.
• Khung tổng quát: choose → explore → unchoose. Quên unchoose là bug phổ biến nhất — trạng thái bị nhiễm giữa các nhánh.
• Pruning: kiểm tra constraint trước khi đệ quy — cắt nhánh vi phạm ngay lập tức. Forward checking và constraint propagation tăng sức mạnh pruning.
• Permutations O(n × n!): dùng used[] để đánh dấu phần tử đã dùng. Subsets O(n × 2ⁿ): dùng index tăng dần để tránh duplicate.
• N-Queens: pruning cột + đường chéo cắt hầu hết cây — N=20 giải trong vài phút dù lý thuyết là số khổng lồ.
• Complexity: worst case luôn mũ (O(n!), O(2ⁿ)), nhưng pruning cắt mạnh average case. Backtracking phù hợp khi n nhỏ (≤ 20-25), greedy/DP khi n lớn hơn.
• Ứng dụng: constraint satisfaction (Sudoku, crossword), game tree search (chess, Go), tổ hợp (tìm tất cả nghiệm).

11. Tự kiểm tra

Bài tiếp theo: Mini-challenge — Edit Distance