Backtracking
El backtracking explora sistemáticamente todas las soluciones candidatas, deshaciendo elecciones (retrocediendo) cuando una rama se vuelve inviable; se usa para problemas de satisfacción de restricciones.
Propósito
Resolver problemas de búsqueda combinatoria y satisfacción de restricciones como las N reinas o el Sudoku.
Mecanismo
Realiza una búsqueda en profundidad del árbol del espacio de soluciones, extendiendo un candidato en cada paso y retrocediendo cuando se viola una restricción. La poda (propagación de restricciones, acotación) reduce el espacio de búsqueda. Clásicos: N reinas, coloración de grafos, suma de subconjuntos.
Casos de uso
- Satisfacción de restricciones
- Búsqueda combinatoria
- Resolución de puzles