Si l'on ne peut pas améliorer une excellente grille en la peaufinant, peut-être peut-on sauter vers une autre excellente grille. Sur chaque paire de records testée, c'est impossible, et la raison structurelle mérite qu'on la voie.
Reproduire ce résultat: calcul lourd — script et résultats sont dans le dépôt
Deux grilles de haut niveau paraissent totalement différentes, et pourtant elles sont liées : on peut transformer l'une en l'autre en prélevant un ensemble de pièces et en déplaçant chacune vers l'emplacement qu'occupait la suivante, tout le long d'une boucle. Les mathématiciens appellent cette boucle un cycle. Parcourez la boucle entière et vous arrivez à l'autre grille.
Voici le hic. Entre les meilleures grilles, cette boucle est énorme et il n'en existe qu'une seule. Passer d'une grille à 459 à celle à 469 de McGavin, c'est un unique cycle imbriqué de 154 cellules, couvrant l'intégralité de l'intérieur de la grille.
Ce n'est pas un schéma : le moteur en direct trouve deux solutions réelles, calcule les cycles effectifs entre elles, et note chaque étape que vous franchissez.
Nous avons calculé les cycles exacts entre trois grilles-records différentes, puis essayé chaque mouvement partiel : n'appliquer qu'une portion de la boucle et observer ce que devient le score. Le résultat est sans appel. Toute application partielle dégrade le score, avec des chutes allant de quelques points à plus d'une centaine. Il n'existe aucun sous-ensemble de la boucle qui aide, pas un seul.
C'est ce qui en fait un mur. Pour passer d'une bonne grille vers une meilleure, il faudrait s'engager à déplacer jusqu'à 154 cellules d'un coup, sans aucune étape améliorante en chemin pour vous y guider. Toute recherche qui procède par étapes est aveugle à un mouvement de ce genre.
Conjuguée avec le mur de rigidité, cette observation ferme d'un coup les deux voies de sortie évidentes. On ne peut pas s'extraire localement d'une bonne grille, et (sur chaque paire de records mesurée ici) on ne peut pas non plus sauter vers une voisine, car la meilleure grille la plus proche se trouve à un unique mouvement indivisible de 80 à 154 cellules. C'est une explication plausible de la raison pour laquelle le record de 470 tient depuis 2021 : les mouvements qui le battraient semblent trop vastes pour qu'une recherche pas à pas puisse les trouver.
Les cycles sont calculés exactement à partir de paires de grilles-records en composant leurs permutations de pièces ; les tests de sous-ensembles énumèrent les sous-cycles et les re-notent. L'animation ci-dessus est une schématisation du mécanisme, non le cycle de 154 cellules lui-même.