Retour sur trace
La recherche en profondeur d'abord, prise au sérieux. L'ordre dans lequel un solveur visite les cases est son unique choix libre et fait varier la taille de l'arbre de plusieurs ordres de grandeur ; les redémarrages transforment un temps d'exécution à queue lourde en portefeuille. C'est la famille qui se cache derrière chaque backtracker record.
L'ordre dans lequel un algorithme de retour arrière visite les 256 cases est son unique liberté : il ne coûte rien à l'exécution et fait varier la taille de l'arbre de recherche de plusieurs ordres de grandeur. Vingt ans de science communautaire, des guerres fixe-contre-dynamique aux courses de stratégies, jusqu'au carré magique 10×16 et à la recherche en peigne de Verhaard, répondent tous à la même question : quel chemin à travers le plateau est le moins coûteux ?
Lancez deux fois le même backtracker sur le même casse-tête et les temps d'exécution diffèrent d'un facteur dix, cent, mille. La communauté l'a mesuré en 2007 ; la littérature CSP l'avait déjà nommé. Le remède (couper, rebattre, redémarrer) explique pourquoi chaque solveur record depuis est un portefeuille de redémarrages.