Vuelta atrás (Backtracking) es una estrategia para encontrar soluciones a problemas que satisfacen restricciones.Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una búsqueda en profundidad.Normalmente, se suele implementar este tipo de algoritmos como un procedimiento recursivo.Además, se comprueba si la solución parcial que falla puede incrementar significativamente la eficiencia del algoritmo.Cabe destacar, que las cotas eficaces se crean de forma parecida a las funciones heurísticas, esto es, relajando las restricciones para conseguir mayor eficiencia.De esta forma, devolverá siempre la mejor solución que haya encontrado.
Ejemplo de árbol de búsqueda. Nótese que el árbol no tiene por qué ser binario.
