Xanh: Đang tìm kiếm
Đỏ: Backtracking (Quay lui)
Khi đi vào ngõ cụt, thuật toán buộc phải "tua ngược" về ngã rẽ gần nhất.
Backtracking (Quay lui) giống như việc đi vào một mê cung mà không có bản đồ. Bạn chọn một hướng và đi tiếp cho đến khi:
Khi gặp ngõ cụt, bạn không bỏ cuộc. Bạn quay ngược lại (backtrack) ngã rẽ gần nhất và thử một hướng khác.
// Mã giả thuật toán
function TryPath(pos) {
if (FoundExit) return true;
if (DeadEnd) return false;
// Thử các hướng: Phải, Xuống, Trái, Lên
for (dir in directions) {
Move(dir);
if (TryPath(newPos)) return true;
Backtrack(); // Quay lại nếu thất bại
}
}