Cerca exhaustiva · 6.1
Backtracking
Construir la solució pas a pas i desfer quan un camí no porta enlloc. L'esquema serveix per a permutacions, subconjunts i molts trencaclosques.
Conceptes clau
- Arbre d'exploració
- Esquema de backtracking
- Generació de permutacions i subconjunts
- Poda
0posicions provades
0tornades enrere
0solucions trobades
sense poda (força bruta)
void reines(int fila) {
if (fila == n) { solucio(); return; }
for (int col = 0; col < n; col++) {
if (pot_anar(fila, col)) { // poda: no l'ataca cap reina
posa(fila, col);
reines(fila + 1);
treu(fila, col); // tornada enrere
}
}
}