Chuyển tới nội dung chính

Quay lui (Backtracking)

Bạn sẽ học được gì

Quay lui (backtracking) là nghệ thuật thử mọi khả năng một cách có tổ chức: đi tới khi còn hứa hẹn, gặp ngõ cụt thì lùi lại (undo) và thử nhánh khác. Nó là chìa khoá cho hoán vị, tổ hợp, xếp hậu (N-Queens), giải Sudoku... Bạn sẽ học khung 3 bước dùng được cho cả họ bài này.

1. Trực quan: đi mê cung có dây Ariadne​

Bạn đi trong mê cung, tay cầm cuộn dây. Tới ngã ba, bạn chọn một lối, thả dây đi tiếp. Gặp tường cụt? Cuốn dây lại (hoàn tác) về ngã ba và thử lối khác. Cứ thế, bạn duyệt mọi đường mà không bao giờ lạc — vì luôn có thể lùi về đúng chỗ vừa rẽ.

        (gốc)
        ╱  │  ╲
      A    B    C        thu A truoc...
     ╱ ╲             ... ngo cut -> LUI lai, thu B
    A1  A2
   (cut)  ✓ loi giai!

"Thả dây" là chọn, "cuốn dây" là hoàn tác. Đó chính là backtracking: một cây các lựa chọn, duyệt theo chiều sâu (gợi nhớ DFS), và luôn dọn sạch dấu vết khi lùi.

2. Khung tổng quát: thử → đệ quy → hoàn tác​

Gần như mọi bài backtracking đều khớp khung này:

def backtrack(trang_thai):
    if la_loi_giai(trang_thai):
        ghi_nhan(trang_thai)
        return
    for lua_chon in cac_lua_chon_hop_le(trang_thai):
        THU:     ap dung lua_chon vao trang_thai   # tien len
        backtrack(trang_thai)                        # de quy sau hon
        HOAN TAC: go lua_chon ra khoi trang_thai     # lui lai

Ba dòng vàng: thử (chọn) → đệ quy → hoàn tác (bỏ chọn). Quên dòng hoàn tác là lỗi kinh điển: trạng thái "rò rỉ" sang nhánh khác và kết quả sai.

3. Bước qua: sinh hoán vị của [1, 2, 3]​

🐞 Hoán vị bằng quay lui (một phần đường đi)Bước 1/7
1def hoan_vi(mang, hien_tai, kq):
2  if len(hien_tai) == len(mang):
3      kq.append(hien_tai[:])      # luu 1 ban sao
4      return
5  for x in mang:
6      if x in hien_tai:
7          continue                 # da dung -> bo qua
8      hien_tai.append(x)           # THU
9      hoan_vi(mang, hien_tai, kq)  # DE QUY
10      hien_tai.pop()               # HOAN TAC
Biến tại bước này
hien_tai[]
x1
👉 Chọn x = 1.

4. Code chạy được: hoán vị, tổ hợp, subsets​

Đang tải trình chạy code…

5. Cắt tỉa (pruning): đừng đi vào nhánh chắc chắn hỏng​

Backtracking trần trụi có thể duyệt cây khổng lồ. Cắt tỉa là: ngay khi biết một nhánh không thể dẫn tới lời giải, bỏ ngay thay vì đi tới cùng. Ví dụ kinh điển là N-Queens (xếp n quân hậu trên bàn n x n sao cho không quân nào ăn nhau).

Đang tải trình chạy code…

Nhờ cắt tỉa, ta không bao giờ đặt hai hậu cùng cột hay cùng đường chéo — cây tìm kiếm co lại rất nhiều so với việc thử mọi cách đặt rồi mới kiểm tra.

6. Phân tích: chậm nhưng đầy đủ​

Khía cạnhBacktracking
Hoán vị n phần tửO(n!) trạng thái — tăng cực nhanh
Tập con (subsets)O(2^n) trạng thái
Bộ nhớO(độ sâu cây) cho ngăn xếp đệ quy
Ưu điểmTìm được mọi lời giải, đảm bảo đầy đủ

Bẫy thường gặp:

  • Quên hoàn tác → trạng thái rò rỉ giữa các nhánh.
  • Lưu tham chiếu thay vì bản sao (kq.append(chon) thay vì chon[:]) → mọi kết quả trỏ chung một list.
  • Không cắt tỉa → cây nổ to, chậm không cần thiết.

7. Mẫu nhận diện: "khi nào nghĩ tới quay lui"​

  • Bài yêu cầu liệt kê tất cả: mọi hoán vị, mọi tổ hợp, mọi cách xếp, mọi lời giải.
  • Có ràng buộc loại bỏ dần các phương án (Sudoku, N-Queens, ghép chữ).
  • Cảm giác "thử một lựa chọn, nếu bí thì lùi lại thử cái khác" → đúng là backtracking.
  • Đệ quy sâu theo cây lựa chọn → bản chất là DFS trên cây trạng thái.

8. 🎮 Trò chơi: Hiểu quay lui​

🎮 Quay lui (backtracking)Câu 1/4· Điểm 0· 🔥 0

Thử - đệ quy - hoàn tác. Quên hoàn tác là sập bẫy kinh điển.

Cắt tỉa (pruning) giúp ích gì?

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Backtracking về bản chất là duyệt cây lựa chọn theo kiểu nào?
2. Lỗi phổ biến nhất khi viết backtracking là?
3. Số hoán vị của n phần tử khác nhau là?

10. Hoàn thành​

…

☑️ Tiếp theo: 3.5.3 — Chia để trị sâu hơn — chia nhỏ bài toán, giải rồi gộp lại.