Cette page répond à une question qui ressurgit sans cesse sur les Stack Exchange
de mathématiques et d'informatique, et qui domine la liste des différends sur la
page de discussion Wikipédia du puzzle : l'appariement de bords est NP-complet en
général, alors cela nous apprend-il quelque chose sur ce plateau 16×16 fixé, et
concrètement, comment confierait-on Eternity II à un solveur ? Les réponses
brèves sont : non, pas directement, voici trois encodages, et une mesure en fin
de page montre à quel point le choix entre eux peut compter.
La NP-complétude est une propriété d'un problème, ce qui, en théorie de la
complexité, désigne une famille infinie d'instances indexée par un paramètre de
taille n. Les « puzzles d'appariement de bords » forment une telle famille :
étant donné n, un ensemble de tuiles carrées et un alphabet de couleurs,
décider si les tuiles pavent un cadre n×n avec tous les bords adjacents
qui concordent. Ce problème de décision est NP-complet
(Demaine & Demaine 2007), ce qui
signifie à la fois qu'une solution proposée est vérifiable en temps polynomial et
que tout problème de NP s'y réduit.
Un plateau fixé unique n'est pas une famille. L'instance Eternity II a une
réponse bien définie, « oui, elle est résoluble » (les concepteurs l'ont
construite à partir d'une solution) ou, dans la forme de compétition à 5 indices,
« oui, avec exactement cet agencement ». Cette réponse tient en un seul bit. Un
seul bit est une constante, et « cette constante est-elle NP-complète ? » n'est
pas une question bien formée : il existe un algorithme en temps constant qui
affiche la réponse (return true), la réponse y est simplement inscrite en dur.
Demander si une instance isolée est NP-complète relève de la même erreur de
catégorie que demander si le nombre 17 est de temps polynomial.
La famille est donc dure et l'instance est une constante. Qu'y a-t-il, alors, de
réellement vrai et utile à dire sur la difficulté du plateau posé sur votre
bureau ?
Deux énoncés distincts, tenus séparés :
- Dureté au pire cas de la famille. Parce que le problème général est
NP-complet, on ne connaît aucun algorithme qui batte le temps exponentiel dans
le pire cas lorsque n croît, et en trouver un prouverait
P=NP. Cela borne ce que tout solveur d'appariement de bords
générique peut promettre. Cela ne dit rien de la manière dont se comporte une
entrée spécifique.
- Dureté empirique de cette instance. Une dureté que l'on peut mesurer. Le
plateau 16×16 compte de l'ordre de 1,115×10557 agencements distincts
de pièces et de rotations, et le puzzle semble n'admettre que très peu de
solutions (la forme à 5 indices est conçue pour n'en avoir essentiellement
qu'une ; voir la théorie de la complexité pour
l'estimation du nombre attendu). Une recherche par retour sur trace faufile
donc un espace astronomiquement vaste vers un ensemble de solutions quasi vide,
et passe ainsi presque tout son temps à explorer des impasses. Voilà pourquoi
le puzzle est dur en pratique, et c'est une affirmation sur ce plateau, non
sur la famille.
Le théorème du pire cas et la difficulté empirique pointent ici dans la même
direction, mais ce sont des énoncés de nature différente et un seul des deux est
un théorème. Une famille peut être NP-complète alors qu'une instance donnée est
triviale (beaucoup le sont), et une instance peut être brutalement difficile à
résoudre en pratique même au sein d'une famille polynomiale. Ansótegui et al. ont
plaidé exactement ce cas empirique pour Eternity II, en en tirant des jeux de
tests pour solveurs et en mesurant la difficulté directement plutôt qu'en
invoquant le théorème général
(CCIA 2008).
La version en une ligne
« Eternity II est-il NP-complet ? » Non : une instance n'a pas de classe de
complexité. « Le problème d'appariement de bords est-il NP-complet ? » Oui.
« Cette instance est-elle difficile à résoudre ? » Empiriquement oui, parce que
l'espace de recherche est large de ~10557 et que l'ensemble des solutions
est quasi vide, si bien que la recherche se noie dans les impasses.
Le reste est pratique : comment écrire le plateau pour qu'un solveur puisse le
mâcher ? Les trois encodages ci-dessous partagent le même squelette. Numérotons
les cases c=1…256, les pièces p=1…256, et les rotations
r∈{0,1,2,3}. Un placement est un triplet (c,p,r) : la pièce p
déposée dans la case c tournée de r quarts de tour. Chaque encodage doit
exprimer trois choses :
- chaque case reçoit exactement un placement,
- chaque pièce est utilisée exactement une fois,
- partout où deux cases se touchent, les couleurs du bord partagé concordent.
Les encodages ne diffèrent que par la façon dont ils expriment la contrainte 3,
l'appariement des couleurs, et cette différence est toute l'affaire. Les croquis
ci-dessous utilisent un plateau 2×2 ou 3×3 pour que l'on puisse voir toutes les
clauses ; le 16×16 a la même forme à plus grande échelle.
Introduisons une variable booléenne xc,p,r, vraie lorsque la pièce p se
trouve à la case c dans la rotation r. Sur le plateau complet, cela fait
256×256×4≈262,000 variables avant la moindre
contrainte. Ensuite :
- Exactement un placement par case. Pour chaque case c, une clause « au
moins un » sur tous ses placements, ⋁p,rxc,p,r, plus des clauses
« au plus un » interdisant toute paire, ¬xc,p,r∨¬xc,p′,r′
pour des placements distincts.
- Exactement une case par pièce. L'image miroir : pour chaque pièce p, une
clause « au moins un » sur les cases qu'elle pourrait occuper, plus des clauses
« au plus un » pour qu'elle ne soit placée qu'une fois.
- Appariement de bords. Pour chaque adjacence intérieure et chaque placement
dont le bord exposé montre la couleur k, interdire tout placement de la case
voisine dont le bord en vis-à-vis n'est pas k : une clause binaire
¬xc,p,r∨¬xc′,p′,r′ pour chaque paire en conflit.
Un croquis 2×2 rend la troisième famille concrète. Les cases A (en haut à
gauche) et B (en haut à droite) partagent un bord vertical ; le bord est de A
doit être égal au bord ouest de B. Pour chaque placement (A,p,r) montrant la
couleur est k, et chaque placement (B,p′,r′) dont la couleur ouest n'est pas
k, ajouter ¬xA,p,r∨¬xB,p′,r′. Faire de même pour A/C
verticalement et pour les deux autres adjacences intérieures. Voilà tout ce
qu'est la contrainte 3 : un grand tas de clauses binaires « ces deux placements
ne peuvent pas être vrais tous les deux ».
Le hic, c'est que le tas est énorme. Les clauses de conflit dominent, les
encodages « au plus un » ajoutent leur propre explosion (l'approche naïve par
paires est quadratique ; les encodages en échelle ou par commandant l'échangent
contre des variables auxiliaires), et le résultat est une formule à des millions
de clauses dont la structure ne donne presque rien à apprendre à la recherche
guidée par les conflits. Cela a été tenté dès 2008 et les solveurs SAT complets
s'enlisent sur le plateau complet ; Blackwood, parmi d'autres, a rapporté que SAT
n'aidait pas. L'encodage est propre, le solveur n'est pas le goulot
d'étranglement, c'est l'instance qui l'est. Voir
Encodages SAT et CSP pour l'historique
des jeux de tests et les cas où les verdicts SAT gagnent encore leur place comme
preuves d'impossibilité sur de petites régions.
La vue par couverture exacte est plus soignée, et elle cache un piège qui fait
trébucher presque tous ceux qui se tournent vers les liens dansants de Knuth.
Posons 512 items : un par case (« la case c est remplie ») et un par pièce
(« la pièce p est utilisée »). Chaque option est un placement (c,p,r), et
elle couvre exactement deux items : la case c et la pièce p. Un ensemble
d'options couvrant chaque item exactement une fois est un plateau où chaque case
est remplie et chaque pièce utilisée une fois. C'est une instance de couverture
exacte propre, et l'Algorithme X de Knuth avec liens dansants résout la
couverture exacte à merveille.
Voici le piège. Les contraintes 1 et 2 sont des conditions de couverture unique,
ce qui est exactement ce qu'exprime la couverture exacte. Mais la contrainte 3,
l'appariement des couleurs, n'est pas du tout une condition de couverture unique :
un bord partagé n'est pas « utilisé une fois », il se voit « attribuer une
couleur sur laquelle les deux voisins s'accordent ». L'Algorithme X ordinaire n'a
aucun moyen de dire cela. On l'encode, on le lance, et on obtient des plateaux
aux bords discordants, ou bien l'on tente de greffer des items supplémentaires et
la sémantique de couverture unique nous résiste. Cette confusion précise a sa
propre question sur le CS Stack Exchange.
La solution est l'extension de Knuth lui-même, l'Algorithme C, pour XCC, la
couverture exacte avec couleurs (TAOCP Volume 4B). À côté des items primaires
(couverts exactement une fois), on ajoute des items secondaires qui peuvent
être couverts un nombre quelconque de fois, pourvu que toutes les options
couvrant un item secondaire donné lui attribuent la même couleur. On donne à
chaque bord intérieur de la grille un item secondaire. Un placement qui expose la
couleur k sur un bord partagé attribue la couleur k à l'item secondaire de ce
bord. Deux placements ne peuvent alors coexister de part et d'autre du bord que
s'ils le colorent de façon identique, ce qui est précisément la contrainte
d'appariement de bords, désormais exprimée nativement.
Un croquis 3×3 : 9 items de case et 9 items de pièce (primaires), plus 12 items
de bord intérieur (secondaires, un par jonction horizontale ou verticale). Les
placements de la case centrale touchent chacun quatre items de bord secondaires
et doivent s'accorder en couleur avec les quatre voisins ; les placements d'une
case de coin en touchent deux. L'Algorithme C faufile tout cela sans jamais
produire de plateau discordant. Le point que les étudiants manquent :
la couverture exacte par DLX pour Eternity II requiert l'Algorithme C, pas
l'Algorithme X. La page
couverture exacte et liens dansants
déroule la construction XCC complète et montre où le DLX brille véritablement
(petits plateaux, dénombrement exhaustif des solutions) par opposition aux cas où
il s'enlise sur le 16×16.
Deux cadrages de plus, utiles surtout comme aiguillages :
- Programmation linéaire en nombres entiers. Réutiliser les variables SAT
comme entiers 0/1 xc,p,r. Les contraintes 1 et 2 deviennent des égalités
∑p,rxc,p,r=1 par case et ∑c,rxc,p,r=1 par pièce.
L'appariement de bords devient, pour chaque bord intérieur et chaque couleur
k, une condition de liaison reliant les placements de couleur k des deux
voisins (une forme propre : une nouvelle variable binaire de couleur de bord
ye,k avec ∑kye,k=1, les placements de chaque côté impliquant le
y correspondant). C'est une PLNE de faisabilité, sans objectif, et la
relaxation linéaire est faible, si bien que la séparation-évaluation se comporte
à peu près comme la recherche SAT. Voir
Relaxations linéaires.
- Clique maximale. Construire un graphe dont les sommets sont les placements
légaux et dont les arêtes joignent deux placements mutuellement compatibles
(cases différentes, pièces différentes, et accord sur tout bord partagé). Un
plateau complet est une clique de taille 256. C'est élégant sur le papier, mais
le graphe est immense et les solveurs de clique ne s'en sortent pas mieux ; cela
vaut d'être connu comme réduction, non comme attaque pratique.
Les sections précédentes se terminent sur une note décourageante : l'encodage
est propre, l'instance est le mur. Cette affirmation méritait un chiffre, et le
chiffrer l'a affinée dans une direction inattendue. Le banc d'essai est une
famille de plateaux plantés : des instances cadrées, aux couleurs
équilibrées, construites à partir d'une solution connue, avec cinq cases de la
solution épinglées comme indices, notées selon la convention des bords appariés
hors pourtour (une résolution complète à la taille N vaut exactement
2N(N−1) bords appariés : 264 en 12×12, 480 en 16×16). Les plateaux plantés ne
sont pas l'Eternity II canonique ; ils admettent vraisemblablement de très
nombreuses solutions là où le vrai puzzle est conçu pour n'en avoir
essentiellement qu'une. Ce qu'ils offrent, c'est une échelle d'instances
résolubles par construction que deux paradigmes de recherche différents peuvent
attaquer côte à côte.
Sur ce banc, à 22 couleurs, une recherche en profondeur à redémarrages qui ne
place que des correspondances exactes résout entièrement quatre graines 10×10
sur cinq (la plus rapide en 4 ms) et deux graines 11×11 sur cinq, puis zéro sur
cinq en 12×12 et zéro à toutes les tailles au-dessus. L'échec n'est pas une
affaire de budget. L'instance 12×12 de graine 1 marque 127 sur 264 après
20 secondes, après 45 secondes et après 120 secondes, tandis que le nombre de
nœuds visités passe de 22 millions à 132 millions ; une instance 14×14 rampe de
236 à 240 sur 364 sur la même extension sextuple du budget. La recherche ne
converge pas lentement ; elle est clouée.
Confiez les instances identiques à CP-SAT avec un modèle structuré (une
variable entière par case parcourant les identifiants de pièces sous une
contrainte AllDifferent, des indices pièce-et-rotation canalisés par des tables
Element vers des variables de couleur par côté, le tout posé en question de
décision) et le mur se déplace. Quatre des cinq instances 12×12 tombent en 31,7
à 88,1 secondes (la cinquième dépasse le délai de 300 secondes), et l'une des
deux instances 13×13 essayées tombe en 74 secondes, chaque plateau retourné
étant revérifié indépendamment : distinction des pièces, conformité aux
indices, décompte des bords recalculé. Ce sont des résolutions complètes
vérifiées de plateaux qu'aucune graine de la DFS ne touche, quel que soit le
budget. La falaise appartient au paradigme de recherche, pas aux plateaux.
Le tour original de cette mesure tournait sur un générateur autorisant 26
couleurs intérieures, un réglage que le banc empaqueté ne peut pas produire
(son générateur plafonne les couleurs intérieures à 22, le compte du vrai
puzzle). À 26 couleurs, le contraste était plus net encore : CP-SAT a résolu
entièrement 25 instances sur 25 aux tailles 10 à 14 avec des temps médians de
0,10 à 0,84 seconde, une demi-seconde en 13×13, et a terminé un 16×16 planté en
15 secondes environ, pendant que la falaise de la DFS se tenait un barreau plus
haut, en 13×13. Ce même tour a aussi mesuré l'écart de formulation en
isolation : sur une instance 12×12, un MIP générique sur binaires de placement
avec lignes de somme à un, passé par la séparation-évaluation de HiGHS, a rendu
11 bords appariés sur 264 après 300 secondes ; CP-SAT a rendu les 264 sur la
même instance en 0,42 seconde. Même problème, même machine, environ trois
ordres de grandeur, et toute la différence tient à la façon d'écrire les
contraintes.
Mettre les deux réglages côte à côte fait apparaître un second résultat : la
falaise bouge avec le nombre de couleurs, pour les deux paradigmes à la fois. À
26 couleurs, la DFS meurt en 13×13 et CP-SAT traverse un 16×16 planté en
quelques secondes. À 22 couleurs, la DFS meurt un barreau plus tôt, en 12×12,
et CP-SAT lui-même ralentit d'environ vingt fois à la médiane entre 11×11 et
12×12 puis commence à dépasser ses délais à partir de 12×12 : les sondes 14×14
et 16×16 butent toutes deux sur un plafond de 120 secondes. (Les grands
barreaux étaient des sondes à graine unique, et les temps CP-SAT à 22 couleurs
portent une part d'inflation due à un volet DFS partageant la machine, qui
n'explique en rien l'écart avec les médianes sous la seconde à 26 couleurs.)
Plus de couleurs, c'est un plateau plus contraint et une recherche plus facile
pour tout le monde ; moins de couleurs tire les deux paradigmes vers le bas
ensemble, si bien que des mesures prises à 26 couleurs avantagent tous les
solveurs de la course. Le 16×16 planté sur lequel la sonde a échoué mérite
d'être vu, montré ici comme sa solution construite :
16×16 planté, 480/480.
Un témoin, compté dix fois
Le tour à 26 couleurs a aussi essayé dix familles heuristiques sur la
falaise, d'un remplisseur naïf ligne par ligne à la propagation AC-3 et à
l'élagage par déficit de Hall : six ont résolu entièrement le 12×12 et
aucune n'a résolu le 13×13. Dix solveurs d'accord ressemblaient à dix
preuves que les instances étaient le mur. C'en était une seule. Les dix
s'engagent chronologiquement et gloutonnement sur une information locale,
donc ils échouent ensemble pour la raison partagée, et le premier solveur
d'un paradigme réellement différent a renversé la conclusion en une
demi-seconde. L'accord de N solveurs de la même famille est un témoin à N
voix.
Si vous êtes venu demander si la théorie de la NP-complétude rend cette instance
prouvablement difficile, la réponse est qu'elle ne le fait pas, et ne le peut
pas : les classes de complexité décrivent des familles, et ce plateau est une
entrée fixée avec une réponse fixée. Le problème général d'appariement de bords
est NP-complet, ce qui plafonne ce que tout solveur peut promettre lorsque n
croît, mais la difficulté que vous ressentez réellement est empirique : un espace
large de 10557 au-dessus d'un ensemble de solutions quasi vide. Chaque
encodage ci-dessus capture fidèlement le puzzle, et sur le 16×16 complet aucun
ne le rend facile ; mais la falaise des plateaux plantés montre que le choix du
formalisme n'a rien de neutre en deçà de cette échelle, où le même plateau peut
être hors d'atteinte pour un paradigme et une résolution d'une minute pour un
autre. Une fois le
plateau encodé, le levier qui subsiste est la
cohérence d'arc et un ordre de recherche
avisé, ce dont s'empare la suite de cette section.