Il y a quelques années, j’ai mis en ligne Les 16 immeubles : une grille 4×4 à remplir avec des immeubles de 1 à 4 étages, où des observateurs postés autour annoncent combien d’immeubles ils aperçoivent — un immeuble plus haut cache ceux qui sont derrière. La page propose 372 grilles, et le petit script Python qui les a fabriquées tourne en quelques secondes. Je n’y avais plus touché.
Passer en 5×5 me semblait une formalité : le même programme, une constante à changer. J’ai essayé plusieurs fois, au fil des mois. Mes versions de test n’ont jamais terminé. Le plus long était la vérification de l’unicité des solutions — je lançais, j’attendais, j’abandonnais.
La page existe désormais : Les 25 immeubles, 400 grilles. La chaîne complète se calcule en 28 secondes. Voici ce qui coinçait, parce que je crois que le cas est instructif bien au-delà de ce petit casse-tête.
Une case de plus, et tout change d’échelle
Une grille valide, c’est un carré latin : chaque hauteur une fois par ligne et une fois par colonne. Il y en a 576 en 4×4, et 161 280 en 5×5. Un facteur 280 : rien d’effrayant.
Sauf que mon programme ne construisait pas 280 fois plus de choses. Il en construisait 90 000 fois plus. Parce qu’il faisait ceci :
# toutes les grilles imaginables, puis on jette celles qui ne vont pas
a = list(itertools.permutations(resultat, cote))
bonnes = [x for x in a if accept_list(x)]
Engendrer tout, puis filtrer. C’est la façon la plus naturelle d’écrire ce genre de chose, et elle est parfaitement raisonnable… tant que le tas de départ reste petit.
| grilles à construire | grilles valides | déchet | |
|---|---|---|---|
| 4×4 | 255 024 | 576 | 443 : 1 |
| 5×5 | 22 869 362 880 | 161 280 | 141 800 : 1 |
Vingt-deux milliards. Et ce n’est même pas une question de patience : ce list(...) demande à Python de tenir les vingt-deux milliards de grilles en mémoire d’un seul coup. Le programme ne ramait pas, il ne pouvait pas démarrer.
Voilà le vrai piège, et il n’a rien d’évident : mon code de 2023 n’était pas mauvais. En 4×4 il gaspille déjà 443 grilles sur 444, et personne ne s’en aperçoit. Le gaspillage ne devient visible qu’en changeant d’échelle.
Premier levier : ne pas construire ce qu’on va jeter
Plutôt que d’empiler cinq lignes au hasard pour vérifier ensuite si l’empilement tient, on pose les lignes une par une, et on vérifie la compatibilité dès qu’une ligne est posée. Une deuxième ligne qui heurte la première est abandonnée sur-le-champ — et avec elle, d’un seul geste, le million et demi de grilles qui commençaient ainsi.
def poser(lignes):
if len(lignes) == n:
grilles.append(tuple(lignes))
return
for p in perms:
# le test a lieu AVANT de descendre, pas apres
if all(all(a != b for a, b in zip(l, p)) for l in lignes):
lignes.append(p)
poser(lignes)
lignes.pop()
Neuf lignes. Le résultat est le même — exactement les mêmes 161 280 grilles — mais le chemin pour y arriver n’a plus rien à voir :
| approche directe | en élaguant | rapport | |
|---|---|---|---|
| 4×4 | 255 024 | 19 608 | 13 × |
| 5×5 | 22 869 362 880 | 27 950 520 | 818 × |
Treize fois en 4×4 : indolore, invisible. Huit cent dix-huit fois en 5×5 : c’est toute la différence entre un programme qui finit et un programme qui ne finit pas.
Deuxième levier : ne pas chercher ce qu’on peut ranger
Mon autre goulot, celui que j’avais identifié — la vérification de l’unicité. Une grille n’est publiable que si ses indices ne désignent qu’elle : deux grilles différentes portant les mêmes nombres autour donneraient un énoncé sans réponse unique. Je testais cela ainsi :
for i in dico:
if list(dico.values()).count(dico[i]) == 1:
dico2[i] = dico[i]
Pour chaque grille, je reconstruis la liste de toutes les valeurs, et je la parcours entièrement pour compter. Sur 576 grilles, c’est instantané. Sur 161 280, chaque tour de boucle repasse sur les 161 280 autres — et il y a 161 280 tours.
La bonne façon tient en deux lignes : on range chaque empreinte dans un casier, une seule fois, puis on relit les casiers qui n’en contiennent qu’un.
combien = Counter(empreintes)
uniques = [g for g, e in zip(grilles, empreintes) if combien[e] == 1]
| grilles | en balayant | en rangeant |
|---|---|---|
| 8 000 | 1,06 s | 0,0016 s |
| 161 280 | ≈ 430 s (7 minutes) | 0,045 s |
Et le point qui m’a le plus frappé, une fois dit : on ne résout jamais aucune grille pour vérifier l’unicité. On calcule l’empreinte de chacune — ses vingt indices — et on cherche les empreintes en double. C’est exactement ce que fait un index de base de données, et je cherchais à la main ce qu’il suffisait de ranger.
Le vrai problème n’était pas la vitesse
C’est ici que l’histoire devient intéressante, parce qu’elle cesse de parler d’informatique.
Une fois le calcul en place, j’avais 68 368 grilles 5×5 à solution unique. De quoi publier. Sauf que « solution unique » et « on peut la résoudre » ne veulent pas dire la même chose.
En 4×4, les deux se confondent : les 372 grilles de la page se résolvent toutes par déduction pure. On peut publier les yeux fermés. En 5×5, c’est faux. Près de la moitié des grilles à solution unique n’admettent aucun chemin de déduction : pour les finir, il faut poser une hauteur au hasard, dérouler les conséquences, et revenir en arrière si l’on se contredit. Elles sont mathématiquement irréprochables et humainement injouables — et rien, dans l’énoncé, ne les distingue des autres.
J’ai eu la démonstration en direct. On m’avait préparé un échantillon gradué, et j’ai attaqué celle qui était classée la plus facile. Je n’ai réussi à placer que trois 5. Puis plus rien. Vérification faite après coup : les règles de déduction usuelles donnent sur cette grille exactement trois cases, et ce sont précisément ces trois-là. Je n’avais pas calé — j’avais atteint le fond de ce que la grille pouvait donner. La suite demandait d’énumérer les 120 dispositions possibles d’une ligne. À la main, non.
Le critère a donc changé. Une grille n’est plus retenue parce qu’elle a une solution unique, mais parce qu’elle se résout avec les règles qu’un joueur applique de tête : l’indice 1 impose le plus haut immeuble au bord, l’indice 5 impose la file croissante, un indice c plafonne les premières cases, on élimine ce qui est déjà posé sur la ligne et la colonne, et une hauteur qui n’a plus qu’une case possible y va.
Ce répertoire est volontairement pauvre : ni énumération, ni hypothèse, ni retour en arrière. Il ne retient que 1 448 grilles sur 161 280 — mais celles-là se terminent sans jamais tâtonner.
Dernier tri : une grille et ses sept images par rotation et symétrie posent le même problème. Qui vient d’en résoudre une refera la suivante sans y penser. En groupant, les 1 448 grilles se ramènent à 188 réellement distinctes, dans lesquelles les 400 fiches sont puisées à tour de rôle. Au passage, cela m’a appris quelque chose sur ma vieille page : ses 372 grilles 4×4 ne sont, elles, que 55 grilles distinctes. Chacune revient en moyenne près de sept fois, tournée d’un quart de tour. Personne ne s’en est jamais plaint, mais c’est bon à savoir.
Le compte final
énumération des 161 280 grilles 14,2 s
calcul des indices 0,9 s
repérage des empreintes uniques 0,03 s → 68 368
résolubles sans tâtonner 13,0 s → 1 448 (188 classes)
───────
total 28,1 s
Vingt-huit secondes, dont zéro virgule zéro trois pour l’étape qui me bloquait depuis des mois.
Le code est en libre accès
J’ai sorti le cœur du générateur dans un dépôt autonome, sans rien qui dépende de mon site, sous licence AGPL-3.0 et sans aucune dépendance hors bibliothèque standard. Il vit sur deux dépôts miroirs : la Forge des communs numériques éducatifs et GitHub, et il est archivé et citable : DOI 10.5281/zenodo.22065758.
Il contient la bibliothèque, un utilitaire en ligne de commande qui sort des grilles en texte ou en HTML, une série de contrôles — dont la vérification du solveur par force brute — et surtout bench.py, qui reproduit tous les chiffres de cet article sur votre machine. Le code est générique : il marche en 4×4 comme en 5×5. Au-delà, l’énumération exhaustive n’a plus de sens et il faudrait échantillonner.
Pour un usage en classe, une seule commande suffit : python3 generate.py -c 20 -o html sort une feuille prête à photocopier, grilles puis solutions. En 4×4 c’est jouable dès le cycle 3, en 5×5 plutôt au cycle 4.
Un mot sur la méthode
J’ai mené ce travail avec Claude (l’assistant d’Anthropic, en version ligne de commande). Ce qui m’a le plus servi n’est pas la production de code — les neuf lignes de l’élagage, je les aurais écrites. C’est d’abord d’avoir mesuré : sans les chiffres du tableau, j’aurais continué à croire que mon goulot était l’unicité, alors que le vrai mur était l’énumération.
Et c’est surtout d’avoir vu que mon critère de 2023 ne voulait plus dire la même chose en 5×5. Sans cela, j’aurais publié 400 grilles dont la moitié auraient été infaisables, et je n’aurais compris pourquoi qu’en lisant les courriels de lecteurs bloqués. C’est le genre de piège qu’on ne repère pas en relisant son code : il faut le chercher.
Une dernière remarque, honnête : la première graduation de difficulté qu’on m’a proposée était fausse, et c’est mon essai raté — les fameux trois 5 — qui l’a révélé. La machine mesurait la puissance de son propre solveur, pas la difficulté pour un humain. Il a fallu changer d’unité de mesure : non plus « en combien d’étapes la machine finit », mais « combien de cases un joueur peut-il poser d’entrée ». Ce recalibrage-là, aucune mesure automatique ne l’aurait déclenché. Il fallait quelqu’un pour s’asseoir devant la grille avec un crayon et constater que ça ne passait pas.
- Les 25 immeubles — 400 grilles 5×5, une nouvelle chaque jour
- Les 16 immeubles — l’aînée, 372 grilles 4×4
- Le générateur, AGPL-3.0 — sur la Forge des communs numériques éducatifs ou sur GitHub, archivé sous DOI 10.5281/zenodo.22065758