Les nonogrammes reposent sur un petit nombre de règles, mais leur structure logique est étonnamment riche.
Le joueur voit des lignes, des colonnes, des nombres, des cases remplies et des croix. Sous cette interface se cache un problème binaire de contraintes : chaque ligne doit correspondre à une description ordonnée de longueurs de blocs, tandis que chaque case doit satisfaire simultanément les contraintes de sa ligne et de sa colonne.
Cela soulève des questions plus profondes que « quelle case dois-je marquer ensuite ? » :
- comment produit-on les indices à partir d'une image ?
- comment sait-on qu'un puzzle possède exactement une solution ?
- pourquoi deux grilles de même taille peuvent-elles avoir des difficultés très différentes ?
- combien de motifs légaux une ligne d'indices peut-elle admettre ?
- comment un solveur informatique reproduit-il la logique de ligne et la propagation ?
- pourquoi certaines instances de nonogrammes sont-elles difficiles sur le plan informatique alors que de nombreux puzzles publiés restent accessibles aux humains ?
La section Théorie de VeyraPlay explore ces questions sans exiger de connaissances mathématiques avancées.
Les nonogrammes comme système de contraintes
Un nonogramme monochrome standard peut être modélisé avec deux états finaux pour chaque case :
- remplie ;
- vide.
L'état indéterminé existe pendant la résolution, mais une solution terminée attribue à chaque case l'un de ces deux états.
Les indices de chaque ligne horizontale limitent les motifs binaires possibles pour cette ligne. Les indices de chaque colonne imposent la même chose verticalement. Comme chaque case appartient à une ligne et à une colonne, les deux familles de contraintes se croisent.
Une technique humaine comme le chevauchement identifie un état de case commun à tous les placements pertinents. Un solveur de ligne peut généraliser cette idée en considérant tous les motifs valides encore compatibles avec les contraintes actuelles et en conservant les états sur lesquels ils concordent.
Comment les nonogrammes sont créés
La méthode de construction la plus simple part d'une image finale en cases noires et blanches.
Pour chaque ligne et chaque colonne :
- on parcourt les états finaux des cases ;
- on mesure chaque bloc consécutif de cases remplies ;
- on note la longueur de ces blocs dans l'ordre ;
- les séquences obtenues deviennent les indices du puzzle.
Ce procédé produit des indices, mais il ne garantit pas à lui seul un bon puzzle.
Le créateur doit aussi vérifier qu'une solution existe, qu'elle est unique, que le parcours de résolution correspond au niveau visé et que l'image finale reste lisible.
Créer son propre puzzle
La création manuelle ajoute des choix de conception avant et après la génération des indices.
Il faut choisir une taille de grille, dessiner une image adaptée à cette résolution, générer les indices puis résoudre et valider le puzzle sans utiliser l'image cachée comme aide.
Une modification visuelle minuscule peut modifier plusieurs indices de lignes et de colonnes et, par conséquent, changer fortement la logique du puzzle.
Solutions uniques et ambiguïté
Un puzzle conventionnel est généralement censé avoir exactement une solution.
Une image prévue par le créateur peut parfaitement respecter les indices sans être la seule grille qui les respecte. Si deux grilles complètes différentes satisfont toutes les lignes et toutes les colonnes, le puzzle est ambigu.
Il faut donc distinguer :
- trouver une solution ;
- prouver qu'au moins une solution existe ;
- prouver qu'aucune autre solution n'existe.
Pourquoi la difficulté ne se résume pas à la taille de la grille
Une grande grille peut contenir de nombreuses lignes très contraintes et se résoudre de façon régulière. Une petite grille peut au contraire comporter un goulot d'étranglement qui exige une analyse de motifs complète, une longue chaîne de propagation ou un raisonnement par contradiction.
Une évaluation de difficulté sérieuse doit donc préciser quel modèle de résolution elle mesure.
Les signaux possibles incluent le nombre de passes, la technique la plus forte nécessaire, la liberté restante dans les lignes, la longueur des cascades, les goulots d'étranglement ou la nécessité d'effectuer du probing ou une recherche.
Les mathématiques derrière les indices
Les indices sont une forme de description par longueurs de séries.
Ils permettent de calculer une extension minimale, une marge de placement et, dans certains cas simples, le nombre de dispositions possibles d'une séquence de blocs dans une ligne vide.
À mesure que des cases deviennent connues, le problème devient un système de contraintes plus riche : certaines dispositions sont éliminées et les lignes et colonnes se restreignent mutuellement.
Cette combinatoire explique pourquoi des techniques visuelles simples, comme le chevauchement, ont une base mathématique précise.
Comment fonctionnent les solveurs informatiques
Un solveur informatique n'a pas besoin de « reconnaître l'image » cachée.
Il peut :
- représenter chaque ligne comme un ensemble de motifs légaux ;
- supprimer les motifs incompatibles avec les cases connues ;
- fixer les cases identiques dans tous les motifs survivants ;
- transmettre ces nouvelles informations aux lignes perpendiculaires ;
- répéter le processus jusqu'à un point fixe ;
- utiliser du probing ou de la recherche si la logique directe ne suffit plus.
Cette architecture ressemble fortement à la résolution humaine par motifs et propagation, même si un programme peut examiner bien plus de possibilités qu'un joueur ne le ferait manuellement.
Pourquoi la complexité informatique compte
Le problème général de résolution des nonogrammes appartient à une classe de problèmes difficiles dans le pire cas. Cela n'implique pas que chaque puzzle publié soit difficile ni que tous nécessitent des essais aveugles.
La théorie de la complexité parle de familles générales d'instances et de la façon dont le coût de résolution peut croître dans les cas les plus défavorables. Les puzzles conçus pour l'humain sont souvent sélectionnés précisément parce qu'ils possèdent une structure logique beaucoup plus exploitable.
Résolution humaine et résolution informatique sont liées, mais pas identiques
Les deux approches partagent des idées fondamentales : placements légaux, états forcés, propagation et contradictions.
Mais elles peuvent différer dans leur coût mental ou informatique. Une opération très naturelle pour un humain peut être coûteuse à formaliser, tandis qu'un ordinateur peut énumérer rapidement des centaines de motifs que personne ne souhaiterait comparer à la main.
C'est pourquoi une mesure de difficulté informatique et une mesure de difficulté humaine ne sont pas automatiquement interchangeables.
Ce que la théorie ne vous dit pas automatiquement
La théorie peut expliquer qu'un puzzle est unique, combien de motifs une ligne possède ou pourquoi une méthode de résolution est complète. Elle ne garantit pas pour autant qu'un puzzle soit :
- agréable à résoudre ;
- adapté à un débutant ;
- bien rythmé ;
- visuellement satisfaisant ;
- correctement classé pour une audience donnée.
La qualité éditoriale combine logique, expérience de résolution et présentation.
Pour aller plus loin
Explorez la construction si vous voulez comprendre comment l'image devient indices. Passez à l'unicité pour distinguer validité et solvabilité, aux mathématiques pour comprendre la combinatoire, aux solveurs pour voir comment ces contraintes sont automatisées, ou à la complexité pour comprendre les limites du problème général.