Thuật toán quay lui (Backtracking): khuôn mẫu 3 bước, code C++ và Python

Hình dung thuật toán quay lui qua việc đi tìm lối ra trong mê cung

Hãy tưởng tượng bạn đang đi trong một mê cung có nhiều ngã rẽ:

• Tại ngã rẽ thứ nhất, bạn đánh dấu phấn xuống đất rồi rẽ trái.
• Đi thêm một đoạn lại gặp ngã rẽ thứ hai, bạn tiếp tục rẽ trái nhưng đụng phải ngõ cụt.
• Bạn không cần phải quay về tận cổng xuất phát! Bạn chỉ cần lùi lại đúng ngã rẽ thứ hai vừa rồi, xóa vết phấn rẽ trái và thử sang lối rẽ phải.
• Nếu cả hai lối ở ngã rẽ thứ hai đều cụt, bạn mới lùi tiếp về ngã rẽ thứ nhất.

Đó chính là quay lui (backtracking) được cài đặt bằng đệ quy: mỗi tầng đệ quy phụ trách quyết định tại một ngã rẽ; khi lời gọi đệ quy kết thúc và trả quyền điều khiển về tầng trước, ta khôi phục trạng thái cũ để thử phương án tiếp theo trong vòng lặp.

Khuôn mẫu 3 bước dùng chung cho mọi bài quay lui

Gần như 100% các bài toán liệt kê cấu hình (sinh dãy nhị phân, sinh tập con, sinh tổ hợp, sinh hoán vị, giải Sudoku, N quân hậu) đều có chung bộ khung sau:

1. Kiểm tra điều kiện hoàn thành: Nếu cấu hình hiện tại cur đã đủ độ dài n, ta ghi nhận hoặc in ra nghiệm rồi return.
2. Duyệt qua các ứng viên có thể chọn cho bước hiện tại: Với mỗi ứng viên v chưa bị cấm (thỏa điều kiện cắt nhánh):
   • Bước 1 (Chọn): Thêm v vào cấu hình cur và bật mảng đánh dấu daDung[v] = true.
   • Bước 2 (Đi tiếp): Gọi đệ quy để điền vị trí tiếp theo.
   • Bước 3 (Hoàn tác — Backtrack): Ngay sau dòng gọi đệ quy, rút v ra khỏi cur (cur.pop_back()) và trả lại daDung[v] = false để trạng thái sạch như cũ cho lần lặp kế tiếp.

Ví dụ 1: Liệt kê mọi hoán vị của {1, 2, ..., n}

Cần xếp n = 3 số {1, 2, 3} vào 3 vị trí sao cho mỗi số xuất hiện đúng 1 lần. Hãy nhìn nhánh đầu tiên của cây quyết định khi vị trí đầu chọn số 1:

• Ở gốc [], chọn 1 → đánh dấu daDung[1] = true, cấu hình thành [1].
• Tại [1], số 1 đã dùng nên vòng lặp chọn tiếp 2 → cấu hình thành [1, 2].
• Tại [1, 2], chỉ còn 3 chưa dùng → cấu hình thành [1, 2, 3] (đủ 3 số, in ra 123).
• Quay lui: rút 3 ra, rồi rút 2 ra (daDung[2] = false), cấu hình quay về [1]. Bây giờ vòng lặp tại [1] thử sang ứng viên tiếp theo là 3 → đi tới [1, 3] rồi [1, 3, 2] (in ra 132).

#include <iostream>
#include <vector>
using namespace std;

void quayLuiHoanVi(int n, vector<int>& cur, vector<bool>& daDung) {
    if ((int)cur.size() == n) {  // đã xếp đủ n vị trí -> in cấu hình
        for (int x : cur) cout << x;
        cout << " ";
        return;
    }
    for (int v = 1; v <= n; ++v) {
        if (daDung[v]) continue;
        // 1. Ghi nhận lựa chọn
        daDung[v] = true;
        cur.push_back(v);

        // 2. Đi tiếp sang vị trí kế tiếp
        quayLuiHoanVi(n, cur, daDung);

        // 3. Hoàn tác lựa chọn (quay lui) để thử giá trị v khác
        cur.pop_back();
        daDung[v] = false;
    }
}

int main() {
    int n = 3;
    vector<int> cur;
    vector<bool> daDung(n + 1, false);
    quayLuiHoanVi(n, cur, daDung);
    cout << "\n";  // 123 132 213 231 312 321
    return 0;
}

def sinh_hoan_vi(n):
    cur = []
    da_dung = [False] * (n + 1)
    ket_qua = []

    def quay_lui():
        if len(cur) == n:
            ket_qua.append("".join(str(x) for x in cur))
            return
        for v in range(1, n + 1):
            if da_dung[v]:
                continue
            # 1. Ghi nhận lựa chọn
            da_dung[v] = True
            cur.append(v)

            # 2. Gọi đệ quy sang bước kế
            quay_lui()

            # 3. Hoàn tác lựa chọn (quay lui)
            cur.pop()
            da_dung[v] = False

    quay_lui()
    return ket_qua


print(*sinh_hoan_vi(3))  # 123 132 213 231 312 321

Ví dụ 2: Bài toán N quân hậu (N-Queens) và kỹ thuật Cắt nhánh

Đề bài: Đặt N quân hậu lên bàn cờ vua kích thước N × N sao cho không có hai quân hậu nào ăn nhau (tức không có hai quân hậu nào nằm cùng hàng, cùng cột, hoặc cùng đường chéo). Đếm số cách đặt hợp lệ.

• Nếu vét cạn đặt thử mọi cách trên bàn cờ 8 × 8 rồi cuối cùng mới kiểm tra, số cách chọn 8 ô trong 64 ô là hơn 4,4 tỷ cách.
• Nếu nhận xét mỗi hàng bắt buộc phải có đúng 1 quân hậu và đặt lần lượt từ hàng 0 đến hàng N - 1, ngay khi định đặt quân hậu ở ô (r, c) mà thấy cột c hoặc hai đường chéo đi qua (r, c) đã có hậu ở các hàng trên, ta cắt bỏ ngay nhánh đó không xét các hàng dưới nữa!

Mẹo đánh dấu đường chéo trong O(1) cực kỳ gọn:

• Mọi ô (r, c) nằm trên cùng một đường chéo chính (hướng \ ) đều có hiệu r - c bằng nhau (cộng thêm n thành r - c + n để chỉ số không bị âm).
• Mọi ô (r, c) nằm trên cùng một đường chéo phụ (hướng / ) đều có tổng r + c bằng nhau.

#include <iostream>
#include <vector>
using namespace std;

int demNQuanHau(int n) {
    vector<bool> cot(n, false), cheoChinh(2 * n, false), cheoPhu(2 * n, false);
    int soCach = 0;

    auto datHau = [&](auto& self, int r) -> void {
        if (r == n) {  // đã đặt xong cả n hàng từ 0 đến n - 1
            soCach++;
            return;
        }
        for (int c = 0; c < n; ++c) {
            if (cot[c] || cheoChinh[r - c + n] || cheoPhu[r + c]) continue;  // cắt nhánh bị ăn
            cot[c] = cheoChinh[r - c + n] = cheoPhu[r + c] = true;
            self(self, r + 1);
            cot[c] = cheoChinh[r - c + n] = cheoPhu[r + c] = false;         // hoàn tác
        }
    };

    datHau(datHau, 0);
    return soCach;
}

int main() {
    cout << demNQuanHau(4) << " " << demNQuanHau(8) << "\n";  // 2 92
    return 0;
}

def dem_n_quan_hau(n):
    cot = [False] * n
    cheo_chinh = [False] * (2 * n)
    cheo_phu = [False] * (2 * n)
    so_cach = 0

    def dat_hau(r):
        nonlocal so_cach
        if r == n:
            so_cach += 1
            return
        for c in range(n):
            if cot[c] or cheo_chinh[r - c + n] or cheo_phu[r + c]:
                continue  # cắt nhánh sớm
            cot[c] = cheo_chinh[r - c + n] = cheo_phu[r + c] = True
            dat_hau(r + 1)
            cot[c] = cheo_chinh[r - c + n] = cheo_phu[r + c] = False

    dat_hau(0)
    return so_cach


print(dem_n_quan_hau(4), dem_n_quan_hau(8))  # 2 92

Nhờ cắt nhánh sớm ngay từ hàng đầu, với N = 8, trong số 8⁸ = 16.777.216 cấu hình đặt 8 hàng, hàm quay lui chỉ phải ghé thăm đúng 2.057 nút để tìm ra đầy đủ 92 nghiệm!

Độ phức tạp của thuật toán quay lui

Độ phức tạp thời gian của quay lui phụ thuộc vào số nút trên cây quyết định không bị cắt bỏ:

Độ phức tạp bộ nhớ phụ của các bài trên chỉ là O(n) (chiều cao của cây đệ quy và vài mảng đánh dấu độ dài n).

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thực hành ngay tư duy quay lui và duyệt cấu hình qua các bài tập dưới đây trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• CSES Competitive Programmer's Handbook — Chapter 5: Complete Search
• USACO Guide: Complete Search with Recursion
• cp-algorithms: Backtracking & Brute Force