Réduire la recherche
Tout ce qui élimine les états sans espoir avant que la recherche n'y perde du temps : propagation jusqu'au point fixe, filtre d'appariement all-different, no-goods appris et invariant de glissement des bords.
Le forward checking regarde un coup à l'avance ; la cohérence d'arc oblige la liste de candidats de chaque case à se défendre contre celle de chaque voisine, jusqu'à un point fixe. AC-3 de Mackworth, les raffinements optimaux qui ont suivi, ce que toute cette famille a réellement mesuré sur ce casse-tête, et où elle devient incorrecte.
Aucune pièce ne peut servir deux fois : une seule contrainte all-different globale sur 256 cases. Jean-Charles Régin a montré en 1994 comment un matching biparti la filtre complètement en temps polynomial ; sa variante par couleur est le propagateur le plus puissant jamais mesuré sur l'edge matching, avec une réserve nette sur les recherches tolérantes aux erreurs.
Le coup primé de Louis Verhaard : laisser le backtracker poser une pièce non concordante, mais seulement à des profondeurs choisies près du bas du plateau. Chaque glissement autorisé coûte un point de score et multiplie de façon astronomique le nombre de plateaux cibles. Voilà pourquoi son 467 a été trouvé plus de cinquante fois, et l'ancêtre direct des ruptures de Blackwood.
Un sous-arbre voué à l'échec est un théorème : cet état partiel ne pourra jamais s'étendre. Mémorisez-le et n'y revenez plus jamais. La communauté a essayé les deux variantes : tables de transposition à la manière des échecs sur la frontière de recherche, et contraintes extraites du puzzle lui-même. Le bilan complet de ce que la mémoire achète à l'échelle d'E2, et les petits plateaux où elle paie vraiment.