Une relaxation semi-définie du problème de placement, ou sa forme de rang faible, moins chère, ouvre-t-elle un chemin vers une solution complète que la recherche n'offre pas ? Sur des plateaux jouets générés de 4x4 à 6x6 (7x7 pour un seul témoin de recuit) : non. Tous les plateaux sortent du générateur du projet (5x5 : couleurs de cadre 3, couleurs intérieures 4 ; 6x6 : cadre 4, intérieur 5 ; graines 0 à 4). Les prix fixes du vrai puzzle sont sur le hub de la série et ne sont pas redémontrés ici. Cette page ne chiffre rien en bits face à eux : la forme convexe ne tourne pas à taille réelle, et la forme bon marché n'a été mesurée que sur deux tailles.
Une variable par placement (une tuile, une rotation, une case) : 478 placements en 5x5, 1 290 en 6x6, 156 816 en 16x16. Le relèvement de degré 2 est une matrice indexée par les placements, avec des zéros sur les paires en conflit (même case, même tuile, ou désaccord de couleur entre voisines), la positivité terme à terme, et les sommes par case et par tuile. La question : les seuls points permis sont-ils les vraies solutions et leurs moyennes ?
Prenez deux solutions complètes d'un plateau jouet et donnez à chacune la moitié du poids. Le résultat met un poids de 0,5 sur chaque placement de l'une ou l'autre, et vérifie toutes les contraintes ci-dessus : les sommes par case et par tuile tombent juste, et aucune paire en conflit n'est utilisée. Toute moyenne de vraies solutions est donc, gratuitement, un point admissible de la relaxation. On dit la relaxation exacte sur un plateau quand elle n'admet rien d'autre : tout point admissible est alors un mélange de vraies solutions. Sur un tel plateau, une seule résolution indique quels placements appartiennent à une solution : sur deux plateaux convergés, 93 des 418 placements que garde la cohérence d'arcs, et 106 sur 373 (une résolution par plateau, non contre-vérifié).
Un poids hors solutions est l'échec de cette propriété : du poids sur un placement qu'aucune solution n'utilise. Un point admissible qui en porte n'est pas un mélange de solutions, donc la relaxation a accepté ce que le puzzle refuse. Deux conséquences. Un mélange n'est pas un plateau : le lire case par case prend des pièces de solutions différentes et laisse des désaccords (13 sur un cas de test), si bien que même une relaxation exacte demande une étape de décodage. Et sans poids hors solutions le point renseigne ; avec lui, la relaxation prouve moins que ce que le plateau permet.
| Résultat | Statut |
|---|
| Relèvement convexe en 5x5 : propre (aucun poids hors solutions) sur les graines 1, 2 et 4 (2 à 8 solutions) | contre-vérifié indépendamment |
| Graine 0 (36 solutions) | indécidé : des points propres existent, la résolution à fuite maximale n'a pas convergé |
| Graine 3 (403 solutions) | inexact : environ 0,042 par case sur dix placements qu'aucune solution n'utilise, à violation 1,5e-9 ; une seule famille de solveurs |
| Mémoire en 16x16 : une copie dense 183 GiB ; facteur plus multiplicateurs de positivité environ 119 GiB ; scission convexe 916 GiB | contre-vérifié indépendamment |
| Essais convexes 6x6 (trois plateaux) | non convergés (poids hors solutions 0,73 à 0,87 par case, stable) : il n'existe aucune lecture 6x6 |
| Forme de rang faible, 5x5 : 200 essais sur 200 résolus sur 15 plateaux, environ 5 200 évaluations par solution | contre-vérifié indépendamment ; recherche aléatoire à test d'acceptation exact, pas un solveur de la relaxation |
| Même forme sans positivité : 46 essais sur 50 résolus | son succès en 5x5 ne dit donc rien du relèvement |
| Facteur positif : 0 départ sur 50 en 5x5 dans chacune de quatre variantes (recuit : 26 sur 50) | non contre-vérifié (dérivation recontrôlée) |
| Six des huit relèvements plus petits fuient ou sont vides en 5x5 | non contre-vérifié |
| Un balayage structuré exact demande encore environ 4,8e12 flops et 100 GB par balayage en 16x16 | non contre-vérifié (arithmétique de coût recontrôlée) |
Le coût par plateau est l'autre moitié. Une résolution convexe 5x5 a pris 400 à 1 100 s sur des plateaux qu'une recherche en profondeur vide en 0,1 s au plus ; en 6x6, la recherche prend 0,3 à 0,6 s.
La forme de rang faible se comporte comme une recherche aléatoire guidée par une pénalité. Les essais qui convergent vers un point admissible sont des mélanges que l'arrondi ne sait pas lire ; ceux qui réussissent sont arrêtés par le test exact pendant que la dynamique de pénalité bouge encore.
Recuit avec redémarrages aléatoires, sur les mêmes plateaux :
| Taille | Recuit par solution face à la forme de rang faible | Statut |
|---|
| 5x5 | 8 à 35 fois moins cher | contre-vérifié indépendamment |
| 6x6 | 3,6 à 63 fois moins cher | une seule passe, intervalles qui se chevauchent sur trois plateaux |
| 7x7 | rien trouvé en 210 essais (taux inférieur à 26 pour cent par essai, non démontré nul) | une seule passe |
Croissance du coût de la forme de rang faible avec le nombre de placements P, sur deux tailles :
| Mesure | 5x5 vers 6x6 | Statut |
|---|
| Évaluations par solution, premier lot | 62 fois (30 à 155) ; exposant 4,2 en P (3,4 à 5,1) | contre-vérifié indépendamment |
| Lot 6x6 complet : 22 départs sur 50 résolus | 460 416 évaluations par solution contre 5 083 ; exposant 4,54 (bootstrap 3,97 à 5,31) | non contre-vérifié |
Deux tailles ne séparent pas une puissance de P d'une exponentielle. Extrapolé naïvement en 16x16, le lot complet donne environ 1,3e15 évaluations par solution : c'est une extrapolation à partir de deux points, pas une mesure.
Les corrections font partie du résultat.
- « Le relèvement est exact en 5x5 » et « premier certificat d'exactitude » : inexact sur la graine 3, et le certificat ne couvre qu'un plateau.
- Probabilités de 60, 20 et 2 pour cent que le relèvement soit exact en 6x6, 8x8 et 16x16 : une estimation jamais dérivée, formulée avant qu'un plateau se révèle inexact.
- « 30 GiB au rang garanti », « 9,3 GB, tient en mémoire en 16x16 » et « 10 heures par départ » : retirés. Tel qu'il est codé, le programme de rang faible demande 910 GB en 16x16 ; la garantie de rang ne vaut que pour la forme sans positivité.
- « Le recuit ne trouve rien en 6x6 » (0 sur 1 000) : un artefact de budget. À 200 millions de pas, le recuit a résolu 20 essais sur 100 sur cinq plateaux 6x6.
- « Recuit 58 pour cent, rang faible 100 pour cent » : les efforts étaient inégaux.
- « Environ 145 fois plus rapide » qu'une version NumPy : non démontré. Le gain ultérieur tient surtout à la charge de la machine (1,3 fois par évaluation). « 50 sur 50 » est 49 sur 50.
- « 70 à 190 s par départ » en 6x6 et « exposant 2,5 au moins » : trop bas d'un facteur 15 à 40 ; 2,5 est un plancher.
- Croissance des itérations « entre P^1,6 et P^3,1 » et « réduction faciale nécessaire » : non démontrées ou contredites.
- Un intervalle de redémarrage plus court en 6x6 : retiré, car la solution médiane tombe au pas 605 sur 1 000.
Rien de positif. La forme convexe est la seule qui ait un certificat, et elle est exacte sur certains petits plateaux, fuit sur au moins un, n'a jamais été lue en 6x6 et demande 119 GiB ou plus en 16x16. La forme bon marché fonctionne comme une recherche aléatoire et perd face au recuit, qui n'a lui-même rien trouvé en 7x7 dans les essais faits. Rien de tout cela n'est un progrès sur Eternity II, et rien ne déplace l'écart du hub. Les records actuels sont sur /research/records et la frontière sur /research/open-problems.
Les essais convexes 6x6 jusqu'à convergence ; une seconde famille de solveurs sur la graine 3 ; toute taille au-delà de 7x7 ; la relaxation en 16x16 ; une décomposition en relèvements locaux, seule voie qui pourrait rendre la forme convexe abordable.
just experiments relaxation-small-boards lance trois essais de fumée (voir la ligne de portée plus haut). Les tableaux viennent des notes et résultats versionnés dans le dossier de l'expérience, dont le README indique d'où vient chaque nombre.