Backtracking
La búsqueda en profundidad tomada en serio. El orden en que un solucionador visita las celdas es su única elección libre y hace variar el tamaño del árbol en órdenes de magnitud; los reinicios convierten un tiempo de ejecución de cola pesada en un portafolio. Esta es la familia detrás de cada backtracker récord.
El orden en que un algoritmo de backtracking visita las 256 celdas es su única libertad: no cuesta nada en tiempo de ejecución y mueve el tamaño del árbol de búsqueda en varios órdenes de magnitud. Veinte años de ciencia comunitaria, desde las guerras entre fijo y dinámico y las carreras de estrategias hasta el cuadrado mágico 10×16 y la búsqueda en peine de Verhaard, responden todos a la misma pregunta: ¿qué camino a través del tablero es el más barato?
Ejecute el mismo backtracker sobre el mismo puzzle dos veces y los tiempos de ejecución diferirán por potencias de diez. La comunidad lo midió en 2007; la literatura CSP ya lo había bautizado. La cura (cortar, rebarajar, reiniciar) es la razón por la que todo solucionador récord desde entonces es un portafolio de reinicios.