Dans les coulisses de ma série Sudoku Géant 16×16 sur Amazon KDP

J’ai commencé à écrire un programme pour générer des Sudoku en 2008. Un vieux projet, presque oublié, que j’ai ressorti cette année pour lancer ma série de livres Sudoku Géant 16×16. Je voulais vous raconter comment il fonctionne, parce que ça me tient à cœur de montrer en quoi il est différent : contrairement à la plupart des générateurs, le mien ne construit pas ses grilles au hasard pour les vérifier après coup. Il simule à chaque étape un vrai raisonnement humain, celui qu’on ferait avec un crayon.

L’idée de départ

La plupart des générateurs travaillent à l’envers : ils créent une grille, la font résoudre par un programme qui teste des hypothèses au hasard (on appelle ça du backtracking), et si l’ordinateur a dû deviner à un moment pour y arriver, tant pis, la grille passe quand même.

Moi j’ai voulu faire différemment, un peu par entêtement. Mon algorithme construit chaque grille en se posant la question qu’un joueur se poserait avec son crayon : est-ce que je peux déduire cette case, oui ou non ? Si à un moment il n’y a plus moyen de déduire quoi que ce soit, la grille est rejetée. Pas de round de rattrapage, pas de « on verra bien si ça passe ».

Ce que ça change pour vous

Concrètement, quand vous ouvrez un de mes livres, chaque case que vous remplirez peut se déduire par un raisonnement logique, sans jamais avoir besoin de tenter un chiffre au hasard en croisant les doigts.

J’ai aussi essayé de rendre les niveaux de difficulté honnêtes. Plutôt que de sortir un chiffre de nulle part selon le nombre de cases vides, je regarde quelles techniques il faut vraiment mobiliser pour venir à bout de la grille :

• Facile

  On s’en sort avec l’essentiel : une case qui n’a plus qu’une seule possibilité, quelques déductions simples sur les lignes, colonnes et blocs.

• Moyen

  Il faut repérer des candidats bloqués et des paires ou triplets de chiffres coincés dans une petite zone, qui permettent d’en éliminer ailleurs.

• Difficile

  La grille exige au moins un X-Wing ou un Skyscraper, ces motifs où un chiffre n’a plus que deux positions possibles sur deux lignes ou colonnes.

• Expert

  Disponible en 9×9 et en 16×16, il faut sortir les techniques réservées à ce niveau : XYZ-Wing, Swordfish, Jellyfish, Unique Rectangle, et quelques autres du même genre.

En coulisses, ce classement ne se limite pas à repérer la technique la plus dure utilisée. Chaque technique a un poids : un solitaire caché vaut peu, une paire nue un peu plus, un Swordfish beaucoup plus, un Unique Rectangle encore plus. L’algorithme additionne ces points au fil de la résolution, et le total doit tomber dans la fourchette propre au niveau visé pour que la grille soit acceptée. Une tentative « Moyen » qui accumulerait trop de points, même sans technique plus dure, est rejetée et le retrait recommence ailleurs. Une tentative « Difficile » qui utiliserait discrètement un Swordfish (réservé à l’Expert) est refusée pour la même raison. Ce filtre automatique fait le plus gros du travail, mais je fais aussi un tri visuel de chaque lot avant publication, pour repérer à l’œil ce que l’algorithme pourrait laisser passer.

Un chiffre illustre bien pourquoi je ne me fie pas au nombre de cases vides : en 16×16, une grille « Expert » vise environ 152 cases vides sur 256, mais une grille « Moyen » en vise 128. Il y a donc des grilles faciles avec plus de trous que des grilles difficiles. Ce nombre n’est qu’un point de départ pour le retrait, pas la mesure de la difficulté. C’est bien la nature des techniques mobilisées qui tranche, pas le compte de cases blanches.

Je ne dis pas que c’est la seule bonne manière de graduer une difficulté. Mais c’est celle qui me paraissait la plus honnête à vous proposer.

Comment ça marche, dans le détail

Pour ceux que ça intéresse vraiment, voici ce qui se passe côté machine quand je génère une grille 16×16.

Tout part d’une grille complète et valide : les 16 lignes, les 16 colonnes, les 16 blocs de 4×4, tout est rempli correctement. Je ne construis pas cette grille case par case en espérant que ça tombe juste. Je mélange des blocs entiers de lignes, de colonnes et l’ordre des 16 symboles, puis je les recombine selon un motif qui garantit une grille valide dès le premier essai. Cette grille de départ devient la solution de référence, celle qui sera imprimée à la fin du livre.

Ensuite je retire des chiffres un par un, mais pas au hasard. Ici je simplifie un peu quand je dis que je relance un solveur complet après chaque retrait : pour une grille de 256 cases, ce serait beaucoup trop lent. En réalité, la plupart des retraits passent par un contrôle rapide et local, je vérifie juste que la case retirée reste déductible par une technique simple (candidat unique ou solitaire caché) à cet instant précis. Le solveur complet, celui qui remonte toute la liste des techniques, n’intervient qu’à des points de contrôle, quand je dois confirmer que la grille entière tient encore le niveau visé. C’est ce mélange de vérifications rapides et de vérifications complètes qui rend la génération praticable en quelques minutes plutôt qu’en quelques heures.

Pour les niveaux les plus élevés en 16×16, je vais même plus loin sur cette phase principale : je refuse les cases qui se retrouveraient récupérables par un simple candidat unique, j’exige au minimum un solitaire caché. Ça force le retrait à durcir la grille plus efficacement. Si je n’arrive pas à atteindre le nombre de cases vides visé avec cette exigence, une passe de repli plus permissive prend le relai pour finir le travail.

C’est pendant ces vérifications complètes que je garde la trace de chaque technique utilisée, case par case. Et pour chaque case, le solveur ne se contente pas de trouver une technique qui fonctionne : il vérifie d’abord qu’aucune technique plus simple ne suffirait. Si une case se déduit par un simple candidat unique, elle n’est pas comptabilisée comme résolue par un X-Wing sous prétexte que le X-Wing marche aussi. C’est ce qui rend le niveau de difficulté fidèle à ce qu’il faut vraiment mobiliser pour finir la grille, plutôt qu’une estimation vague basée sur le nombre de trous.

D’où viennent les indices du livre

Ce même journal de résolution sert à autre chose : c’est lui qui alimente les indices imprimés dans mes livres. Chaque fois que le solveur applique une technique pendant la phase de vérification, il note la méthode utilisée et les coordonnées exactes des cases concernées. Ces notes ne sont pas retravaillées après coup pour l’édition papier, ce sont les mêmes qui sortent directement du solveur. Quand vous lisez « X-Wing » à côté d’une case dans un de mes livres, c’est très concrètement la trace laissée par l’algorithme au moment où il a validé cette grille.

Pour les techniques les plus avancées en 16×16, je vais même un cran plus loin : je distingue la case où la déduction s’applique (celle où un chiffre est éliminé ou posé) des cases qui forment le motif lui-même, les quatre coins d’un X-Wing, le pivot et les deux ailes d’un XY-Wing, les positions d’un triplet ou d’un quadruplet. Ce sont deux informations différentes, enregistrées séparément. C’est ce qui permet, si besoin, de montrer non seulement le résultat de la déduction mais aussi la forme du raisonnement qui y mène, utile pour un indice qui explique vraiment quelque chose plutôt que de juste donner la réponse.

Cette façon de faire a aussi une conséquence utile : une grille qui se résout intégralement par déduction logique, sans jamais avoir besoin de deviner, n’a par construction qu’une seule solution possible. Si plusieurs solutions existaient, le raisonnement logique seul ne suffirait pas à trancher entre elles à un moment donné, et le solveur resterait bloqué. La solution unique n’est donc pas une vérification que j’ajoute à part : elle découle directement du principe de base.

Pourquoi je m’embête avec tout ça

Sur un écran, un solveur peut deviner et revenir en arrière sans que personne ne le voie. Sur papier, c’est une autre histoire : si une grille imprimée demande de tâtonner à un moment, le lecteur se retrouve coincé, ou pire, il avance plusieurs cases sur une fausse piste avant de s’en rendre compte. C’est ce désagrément que j’essaie d’éviter avec cette méthode, sans prétendre avoir inventé la seule bonne façon de faire.

Ce programme reste un chantier en cours, un peu comme un terrain de jeu personnel que je continue à bricoler. Pour le moment je me concentre sur le 16×16, c’est déjà beaucoup de travail à bien faire. D’autres formats sont dans un coin de ma tête, mais un peu de patience, c’est aussi une histoire de temps disponible.

Voir le résultat concret

C’est aussi beaucoup d’heures de travail perso, souvent sur mon temps libre. Donc si cet article vous a donné envie de voir le résultat, voici les deux premiers volumes :

D’autres langues sont prévues, avec des grilles différentes à chaque fois. Suivez les nouveautés sur ma page auteur Amazon.

Et si le sujet vous intéresse ou que vous avez des questions sur le fonctionnement de l’algorithme, n’hésitez pas à m’écrire.