Backtracking (N-Queens)

Phương pháp này duyệt tìm kiếm mọi hướng đi khả thi. Nhưng nó thông minh hơn Vet cạn (Brute Force) ở chỗ: Chỉ cần thấy đường đi hiện tại có dấu hiệu "vô nghiệm", thuật toán sẽ Cắt tỉa (Pruning) nhánh đó và lập tức "Quay lui".

Yêu cầu: Đặt N quân Hậu lên bàn cờ NxN sao cho không con nào có thể ăn con nào (Không nằm cùng hàng dọc, ngang, hoặc chéo).

Cách giải: Đặt con 1, xong đặt con 2. Nếu con 2 bị chiếu, di chuyển con 2 sang ô bên cạnh. Cứ thế đi tiếp hoặc lùi về sau.