Ce qui rend un nonogramme facile ou difficile
La « difficulté » d'un nonogramme ne tient pas qu'à la taille de la grille. Un 20×20 peut se résoudre presque tout seul, tandis qu'un 10×10 peut vous faire batailler pour chaque case. Ce qui détermine vraiment la difficulté, c'est la profondeur du raisonnement nécessaire pour trouver le prochain coup forcé. Ce guide décortique ce qui la gouverne réellement — et partage une découverte surprenante de la recherche sur la rareté avec laquelle un casse-tête équitable réclame quoi que ce soit d'astucieux.
La taille n'en est qu'une partie
Une grille plus grande signifie effectivement plus de lignes à suivre et plus de vérifications croisées, donc les grands casse-têtes prennent plus de temps. Mais la longueur seule ne rend pas une ligne difficile — une rangée de 20 de large avec une seule grande séquence est triviale, alors qu'une rangée courte bourrée de petites séquences et d'espaces serrés peut exiger une vraie réflexion. La taille influe bien plus sur le temps que prend un casse-tête que sur la difficulté de chaque étape.
Il s'agit en réalité de la profondeur des déductions
La mesure la plus juste de la difficulté est le type de raisonnement qu'exige le casse-tête. Les plus faciles sont « résolubles par ligne » : vous pouvez les terminer en regardant une rangée ou une colonne à la fois, en remplissant ce que cette seule ligne force, sans jamais avoir à garder deux lignes en tête en même temps. La plupart des casse-têtes doux sont exactement cela.
Les plus difficiles exigent de combiner les informations — de remarquer que l'état d'une case ne devient forcé que lorsque vous considérez une rangée et une colonne ensemble, ou un petit groupe de lignes à la fois. Plus cette combinaison doit aller en profondeur avant que la case suivante soit forcée, plus le casse-tête paraît difficile, quelle que soit sa taille.
Ce que dit la recherche sur le tâtonnement
Voici la partie rassurante. Les travaux universitaires sur la résolution des nonogrammes (Batenburg and Kosters, 2012) ont mesuré combien de raisonnement les casse-têtes à solution unique exigent réellement. Au-delà de la simple résolution ligne par ligne, l'étape suivante est une technique bien définie et encore déterministe — combiner des paires de lignes — et leur énumération exhaustive a constaté que 93.8–95.5% des casse-têtes non simples sont résolubles exactement par cette méthode, sans aucun tâtonnement.
Plus frappant encore : seulement environ 0.06–0.14% de tous les casse-têtes à solution unique ont besoin de quoi que ce soit au-delà de ce raisonnement sur les paires de lignes. Autrement dit, l'écrasante majorité des nonogrammes bien formés — y compris chaque casse-tête difficile que vous rencontrerez en jeu normal — peut être résolue par une logique pure et bornée. Le véritable essai-erreur est extrêmement rare dans un casse-tête équitable, et c'est pourquoi « ne jamais deviner » est un conseil si fiable.
« Difficile » a aussi ici un sens formel
Sous tout cela se trouve un résultat théorique. Déterminer si un ensemble arbitraire d'indices de rangées et de colonnes possède ne serait-ce qu'une solution a été prouvé NP-complet (Ueda and Nagao, 1996) — la même classe de complexité que des problèmes notoirement tenaces comme celui du voyageur de commerce. En clair : personne ne connaît de méthode qui résolve rapidement tout nonogramme concevable, et dans le pire des cas le travail nécessaire explose à mesure que la grille grandit.
Cela paraît alarmant jusqu'à ce que vous remarquiez la différence entre « tout nonogramme concevable » et « les nonogrammes que les gens publient réellement ». Le résultat de NP-complétude porte sur des ensembles d'indices arbitraires et adverses — dont beaucoup n'ont aucune solution, ou plusieurs. Un vrai casse-tête est construit à l'envers : il part d'une image, et il n'est publié que s'il a exactement une solution que la logique peut réellement atteindre. C'est pourquoi les chiffres de la section précédente tiennent en pratique, et pourquoi le casse-tête devant vous est presque certainement équitable, même quand il semble brutal.
La densité et la forme comptent aussi
Au-delà de la profondeur de déduction, quelques caractéristiques de surface font pencher la difficulté. Les images très clairsemées (surtout vides) et très denses (surtout remplies) tendent à être plus faciles, car les extrêmes fournissent tôt beaucoup de cases forcées. Les casse-têtes les plus délicats se situent généralement au milieu, avec un mélange équilibré de rempli et de vide et de nombreuses séquences courtes et morcelées qui résistent aux coups d'ouverture rapides. Un sujet net et reconnaissable aide aussi le solveur à rester orienté, même s'il ne change rien à la logique sous-jacente.
Comment nous étiquetons facile, moyen et difficile
Sur ce site, la note d'un casse-tête découle de la profondeur du raisonnement nécessaire pour le résoudre, combinée à des statistiques de forme comme le taux de remplissage de la grille. Les casse-têtes résolubles par ligne atterrissent en facile ; ceux qui exigent une véritable combinaison entre lignes se déplacent vers difficile ; tout ce qui exigerait de deviner est rejeté d'emblée plutôt que publié. Le processus complet est décrit sur la page « comment nous créons nos nonogrammes » — mais la version courte est qu'ici la difficulté est mesurée, pas devinée.