Backtracking = "înapoi în caz de eșec". Construiești o soluție pas cu pas; dacă ajungi într-o situație invalidă, te întorci (backtrack) și încerci o altă alegere.
Schema generală:
python.py
def backtrack(solutie_partiala):
if este_completa(solutie_partiala):
proceseaza(solutie_partiala)
return
for optiune in optiuni_posibile():
if este_valida(solutie_partiala + optiune):
backtrack(solutie_partiala + optiune) # continua
Condiții pentru backtracking:
- Poți construi soluția incremental (pas cu pas).
- Poți verifica rapid dacă o alegere e validă.
- Soluția e finită (se termină).
Backtracking explorează un arbore de decizii. La fiecare nivel alegi o ramură; dacă nu duce la nimic, revii și alegi alta.