Comment résoudre Eternity II avec un ordinateur ?

2 · Le mur exponentiel

Ce « tout », au juste, c'est grand comment ? Pour un puzzle n×n, on compte à peu près n²! manières de ranger les pièces, multipliées par leurs 4 rotations. Le graphique ci-dessous indique le nombre de chiffres de ce total. Remarquez la ligne, presque droite : à chaque cran de taille, le travail est multiplié par un facteur astronomique. La boîte 16×16 posée sur votre étagère, elle, plafonne aux alentours de 560 chiffres.

La ligne bleue résume la toute première leçon de conception d'algorithmes : une déduction, c'est un monde qui rétrécit. Rien que de remarquer que les pièces de coin finissent dans les coins et les pièces de bord sur le pourtour, on raye déjà environ 100 chiffres. Les vrais solveurs enchaînent quantité de déductions du même genre. Et pourtant, on reste très loin du compte.

Le mot « chiffres » reste abstrait ; alors rendons la chose concrète :

3 · La difficulté, mesurée : taille et couleurs

Nous avons généré des centaines de mini-puzzles et confié chacun au moteur, en comptant les nœuds (les placements de pièce mis à l'essai) jusqu'à la première solution (médiane sur 10 puzzles tirés au hasard pour chaque point ; échelle logarithmique !). Trois choses sautent aux yeux. D'abord, chaque rangée de plateau en plus multiplie le travail : les courbes sont espacées de plusieurs ordres de grandeur. Ensuite, ajouter des couleurs rend souvent le puzzle plus facile, parce qu'un mauvais placement se fait recaler plus vite au lieu d'attirer la recherche au fond d'une impasse. Enfin, chaque courbe trahit un phénomène bien connu : un pic de difficulté. Très peu de couleurs → des solutions à la pelle, faciles à dégoter par hasard. Beaucoup de couleurs → un puzzle si contraint que la recherche ne se ramifie presque plus. Le pic se loge entre les deux — et surtout, il glisse vers la droite à mesure que le plateau s'agrandit : la courbe 6×6 culmine à 4 couleurs, la courbe 8×8 à 6 couleurs, soit grosso modo une couleur de plus par rangée ajoutée. À son sommet, le puzzle 8×8 médian réclame plus de 2 milliards de placements de pièces, et la plupart des graines ont tourné si longtemps qu'on a dû renoncer à les mesurer (les plateaux des courbes, ce sont ces points censurés). Une couleur de plus ou de moins, et tout s'effondre d'un facteur cent. Prolongez cette progression d'une couleur par rangée jusqu'au plateau 16×16 et le pic retombe pile sur les 22 couleurs — exactement le réglage choisi pour Eternity II. Rien d'accidentel à ce qu'il se tienne au-delà du pic : il est calibré pour tomber dessus.

4 · L'ordre dans lequel on cherche compte. Et même énormément.

Mêmes puzzles, même solveur. La seule chose qui change, c'est le parcours, l'ordre dans lequel les cases se remplissent. Les parcours qui collent chaque nouveau placement à des voisins déjà posés (snake, spiral) verrouillent chaque étape et élaguent tôt. Ceux qui dispersent les placements (random) laissent les pièces libres de toute contrainte… et le paient cher plus loin. C'est un véritable sujet de recherche, et vous pouvez d'ailleurs concevoir votre propre parcours pour le lancer dans la course. Voici l'allure réelle des parcours classiques ; suivez les flèches (rouge = première case, vert = dernière) :

Une subtilité à nommer (merci à Dan Karlsson) : « rangées » et « colonnes » sont le même ordre à une symétrie diagonale près du plateau, donc sur de nombreux puzzles ils devraient coûter pareil — tout écart ici est du bruit d'échantillonnage, pas une vraie différence. Les ordres qui diffèrent vraiment sont ceux de forme différente : une spirale, une diagonale, le cadre d'abord. Une réserve : la barre de l'ordre aléatoire est une borne inférieure, pas une médiane mesurée — chaque exécution échantillonnée a atteint le plafond de recherche sans finir, donc son coût réel est plus élevé que ce qui est montré.

La même question, poussée jusqu'au bout sur le vrai plateau 16×16, c'est l'étude DFS : elle mesure ce qu'apportent chaque ordre de remplissage, chaque heuristique et chaque règle de cassure, et montre que le mauvais ordre peut coûter plus de 300 points de score.

5 · Pourquoi, ici, les ordinateurs raisonnent en binaire

Une pièce, ce n'est rien d'autre que quatre petits nombres (les motifs du haut, de droite, du bas et de gauche). Ni image, ni géométrie. Les quatre démos ci-dessous tournent en direct ; accordez quelques secondes à chacune :

Une fois codé sous forme de nombres, le jeu officiel au complet tient dans environ 1 Ko. Les solveurs sérieux poussent l'astuce plus loin avec les bitsets : un seul nombre de 64 bits transporte une réponse oui/non sur 64 pièces à la fois, si bien qu'une unique instruction du processeur filtre 64 candidates d'un seul coup. C'est ce qui permet aux moteurs les plus rapides d'abattre des centaines de millions de nœuds par seconde. La façon de représenter les données — pas seulement l'algorithme — fait partie du métier.