Lesson 18 — Backtracking (Quay lui)

Thử từng lựa chọn → đi sâu (DFS) → gặp ngõ cụt thì quay lui (undo) thử lựa chọn khác. Ba module dưới đây cho bạn "nhìn thấy" cây trạng thái được duyệt, bàn N-Queens được lấp dần và sức mạnh của pruning.

1. Decision Tree Explorer

Duyệt cây trạng thái cho [1,2,3]. Xem DFS đi xuống (xanh) và backtrack đi lên; node được ghi nhận lời giải tô vàng.

Bài: Tốc độ

đang thăm ghi lời giải đã xong (quay lui)

Nhấn "Bước" hoặc "Tự chạy".

2. N-Queens Solver

Đặt N hậu theo từng hàng. Ô xanh = đang thử, đỏ = bị tấn công (pruning cắt nhánh), xanh lá = đặt thành công.

N: Tốc độ

Chọn N (4–8) rồi nhấn Giải.

3. Pruning Impact

Đếm số node dfs được duyệt để đếm nghiệm N-Queens, có vs không pruning cột/chéo. Không pruning = thử mọi cách đặt 1 hậu/hàng rồi kiểm tra ở lá (b^d = N^N).

Nhấn "Đo" để so sánh.