Journal De 4×4 à 5×5 : quand mon générateur de grilles ne finissait plus

Sommaire

• De 4×4 à 5×5 : quand mon générateur de grilles ne finissait plus
  • Je cherchais la lenteur au mauvais endroit
  • Le programme terminait. Moi, je restais bloqué.
  • Changer la question posée au générateur
  • Le code et les grilles

De 4×4 à 5×5 : quand mon générateur de grilles ne finissait plus

Il y a quelques années, j’ai écrit un programme Python pour fabriquer des grilles de « gratte-ciel ». On doit placer dans chaque ligne et chaque colonne des immeubles de hauteurs différentes. Les nombres inscrits autour de la grille indiquent combien d’immeubles on voit depuis chaque bord : un immeuble plus haut cache ceux qui sont derrière lui.

En 4×4, mon programme tournait en quelques secondes. Il m’avait permis de publier une série de 372 grilles. Passer en 5×5 me paraissait être une évolution naturelle. J’ai changé la taille, lancé le calcul, attendu… puis abandonné. Plusieurs fois.

Cet été, j’ai repris le problème avec Claude, utilisé en ligne de commande. Je savais qu’il faudrait revoir le code, mais je me trompais sur ce qui le bloquait. Et lorsque le générateur a enfin fonctionné, une grille essayée au crayon m’a montré qu’il restait un problème bien plus gênant.

Je cherchais la lenteur au mauvais endroit

Je soupçonnais la vérification de l’unicité. Une grille n’est publiable que si ses indices de bord conduisent à une seule solution. Mon ancien programme calculait ces indices, puis reparcourait toutes les grilles pour repérer les doublons. Avec davantage de grilles, cette opération devenait effectivement coûteuse.

Mais les premières mesures ont révélé un obstacle antérieur. Pour construire ses candidats, le programme assemblait toutes les lignes possibles, mettait le résultat en mémoire, puis rejetait les grilles dont une colonne répétait une hauteur.

	Assemblages envisagés	Grilles valides
4×4	255 024	576
5×5	22 869 362 880	161 280

D’une taille à l’autre, le nombre de grilles valides est multiplié par 280. Le nombre d’assemblages que mon code voulait fabriquer est multiplié par environ 90 000. En 4×4, le gaspillage passait inaperçu. En 5×5, la tentative de placer tous ces assemblages dans une liste rendait le calcul impraticable.

La correction a consisté à poser les lignes une par une. Dès qu’une nouvelle ligne répète une hauteur dans une colonne, on abandonne cette branche. Il n’y a aucune raison de construire toutes les grilles qui commenceraient par cette erreur.

L’unicité avait aussi besoin d’une correction : au lieu de reparcourir la collection pour chaque grille, un Counter compte en un passage combien de fois apparaît chaque série d’indices. On conserve les séries qui n’apparaissent qu’une fois. On n’a pas besoin de résoudre les grilles pour ce contrôle : deux grilles portant les mêmes indices constituent précisément deux solutions possibles du même énoncé.

Je travaillais donc sur un vrai défaut, mais ce n’était pas celui qui empêchait le programme de terminer. Sans les mesures, j’aurais continué à optimiser le mauvais endroit.

Le programme terminait. Moi, je restais bloqué.

Le calcul réparé, j’obtenais 68 368 grilles 5×5 à solution unique. J’avais de quoi choisir.

J'ai préparé un échantillon classé par difficulté. J’ai pris une grille présentée comme facile, avec un crayon. J’ai placé trois immeubles de hauteur 5. Ensuite, plus rien.

J’ai d’abord pensé que je ratais une évidence. Mais les règles de déduction que je voulais mettre à la portée des joueurs ne permettaient effectivement pas d’aller plus loin. Pour terminer cette grille, il fallait envisager des dispositions possibles, faire une hypothèse et, au besoin, revenir en arrière. Elle avait bien une solution unique ; cela ne la rendait pas agréable à résoudre à la main.

La première graduation proposée au cours de mon travail avec Claude mesurait ce que savait faire son solveur. Moi, je voulais savoir ce que pouvait déduire une personne devant la grille. Le code répondait correctement à une question que je n’aurais pas dû lui poser.

On pourra appeler cela du vibe coding : j’ai travaillé avec Claude pour cette version 5×5 et je ne cherche pas à le dissimuler. Mais la difficulté la plus instructive n’était ni une erreur de syntaxe ni un plantage. Le programme fonctionnait, ses résultats semblaient cohérents, et son critère de difficulté était mauvais pour l’usage que j’en avais. Il a fallu essayer de jouer pour le voir.

Changer la question posée au générateur

J’ai alors retenu un critère plus exigeant que l’unicité : une grille doit pouvoir se résoudre entièrement par une suite de déductions simples, sans hypothèse ni retour en arrière.

Le programme utilise pour cela un répertoire volontairement limité de règles. Un indice 1 place le plus haut immeuble au bord ; un indice 5 impose l’ordre croissant de toute une ligne ; les hauteurs déjà placées éliminent des possibilités dans leur ligne et leur colonne. Lorsqu’une hauteur n’a plus qu’une case possible, on la place, puis on recommence.

Ce filtre ne retient que 1 448 grilles parmi les 161 280 grilles valides. Après regroupement des grilles équivalentes par rotation ou symétrie, il reste 188 configurations distinctes. Les 400 fiches publiées puisent dans cet ensemble : certaines configurations reviennent donc sous une autre orientation.

La chaîne complète prend maintenant environ 28 secondes sur ma machine. Ce chiffre me plaît, bien sûr. Mais le changement essentiel est ailleurs : le programme sélectionne désormais des grilles selon ce que je souhaite proposer à quelqu’un qui va réellement les résoudre.

Le code et les grilles

J’ai extrait le générateur de mon site pour le publier séparément sous licence AGPL-3.0. Il n’utilise que la bibliothèque standard de Python 3. Le dépôt contient aussi des contrôles et un bench.py pour reproduire les mesures. On peut produire des grilles en console ou une feuille HTML avec les solutions, prête à imprimer.

Je retiens deux choses de ce travail avec Claude. D’abord, mesurer a démenti mon intuition sur le blocage du programme. Ensuite, obtenir un résultat calculable et vérifiable ne suffisait pas : il fallait encore vérifier que nous avions défini la bonne tâche. Dans mon cas, cette dernière vérification a commencé avec trois 5 posés au crayon et une grille qui refusait d’en dire davantage.

Le générateur et ses instructions sont sur la Forge des communs numériques éducatifs, avec un miroir sur GitHub. Les grilles 5×5 sont jouables en ligne. J’ai raconté les calculs et les choix plus en détail sur mon blog.