Le problème général des nonogrammes est difficile sur le plan informatique : des résultats formels établissent la NP-complétude de formulations décisionnelles standards, et la recherche ultérieure décrit couramment la résolution générale des nonogrammes comme NP-difficile.
Cela ne signifie pas que chaque nonogramme est difficile, que les ordinateurs ne savent pas les résoudre, ni qu'un puzzle 10×10 exige forcément un temps exponentiel en pratique. La théorie de la complexité étudie le comportement des instances les plus difficiles lorsque la taille du problème augmente.
Quel problème la théorie de la complexité analyse-t-elle ?
Un résultat de complexité doit porter sur une question informatique précise.
Une version décisionnelle simplifiée est :
Étant donnés les indices de lignes et de colonnes d'un nonogramme, existe-t-il au moins une grille remplie/vide qui les satisfasse tous ?
Une grille complète proposée peut être vérifiée efficacement : il suffit de parcourir chaque ligne et chaque colonne et de comparer les longueurs de ses blocs avec les indices.
La partie difficile consiste à trouver une solution, ou à décider si elle existe, pour l'ensemble de tous les jeux d'indices possibles.
Que signifie NP-complet ici ?
De façon informelle, un problème décisionnel est NP-complet lorsque :
- une solution proposée peut être vérifiée efficacement ;
- le problème est au moins aussi difficile que tous les problèmes de la classe NP via des réductions en temps polynomial.
Le rapport technique de Ueda et Nagao de 1996 a établi des résultats de NP-complétude pour les nonogrammes à l'aide de réductions parcimonieuses. Des travaux ultérieurs sur les nonogrammes citent ce résultat lorsqu'ils discutent de la difficulté du problème général.
Vous n'avez pas besoin de théorie de la complexité pour jouer. Ce résultat est utile parce qu'il explique pourquoi on ne peut pas s'attendre à ce qu'une petite collection de techniques locales résolve efficacement toutes les instances possibles.
NP-complet ne signifie pas « toujours difficile »
C'est l'idée reçue la plus importante à éviter.
Le Sudoku, SAT et beaucoup d'autres problèmes NP-complets possèdent d'immenses familles d'instances faciles. Les nonogrammes ne font pas exception.
Les éditeurs construisent volontairement des puzzles avec une structure exploitable :
- des indices informatifs ;
- des chevauchements forts ;
- une propagation productive entre lignes et colonnes ;
- des goulots d'étranglement contrôlés ;
- souvent un parcours logique adapté aux humains.
Batenburg et Kosters opposent explicitement les nonogrammes de livres de puzzles, souvent résolubles par raisonnement local répété sur les lignes, au problème général difficile.
Pourquoi l'espace de recherche peut-il devenir énorme ?
Chaque ligne peut admettre plusieurs dispositions légales. Sur une grille complète, ces choix interagissent via les cases partagées.
Une décision qui semble légale dans une ligne peut contraindre plusieurs colonnes ; ces colonnes en contraignent d'autres lignes ; et une contradiction peut n'apparaître qu'après une longue chaîne.
Dans le pire cas, un solveur doit distinguer un grand nombre de combinaisons de motifs ou explorer des alternatives par ramification.
Le nombre brut de grilles binaires complètes est déjà énorme : une grille r × c possède 2^(r·c) affectations possibles remplies/vides avant que les indices n'en éliminent la majorité.
Les bons solveurs ne les énumèrent jamais aveuglément, mais ce chiffre illustre pourquoi les contraintes et l'élagage sont essentiels.
Pourquoi la logique de ligne résout-elle autant de puzzles réels ?
Les nonogrammes conçus pour les humains ne sont pas des instances aléatoires choisies pour réaliser le pire cas.
Les créateurs veulent souvent une image reconnaissable et un parcours de résolution satisfaisant. Cette pression de design favorise des structures que la logique de ligne ordinaire peut exploiter.
Un solveur peut répéter :
- résoudre les lignes contraintes ;
- transférer les cases forcées vers les colonnes ;
- résoudre les colonnes modifiées ;
- propager à nouveau.
Pour de nombreux puzzles publiés, cela suffit.
La théorie de la complexité affirme seulement que certaines entrées valides échappent à toute stratégie universellement efficace, sous l'hypothèse standard P ≠ NP.
NP-difficile et NP-complet : quelle différence ?
Les deux termes apparaissent dans la littérature sur les nonogrammes.
- NP-difficile signifie qu'un problème est au moins aussi difficile que les problèmes les plus difficiles de NP.
- NP-complet ajoute que le problème décisionnel appartient lui-même à NP.
Pour le problème décisionnel habituel d'existence d'une solution, la formulation NP-complète est appropriée dans le résultat cité. Les articles qui parlent plus largement de résolution utilisent souvent NP-difficile comme terme englobant plus prudent.
L'unicité rend-elle le problème plus facile ?
Pas automatiquement.
Un puzzle dont on promet qu'il possède une seule solution peut toujours être difficile à résoudre. Déterminer s'il existe une autre solution est lui-même lié à des problèmes difficiles de type « autre solution » étudiés en théorie de la complexité.
Pour l'édition, la conclusion pratique est plus simple :
unique, résoluble par un humain et facile sont trois affirmations différentes.
Pourquoi les solveurs informatiques fonctionnent-ils malgré tout très bien ?
La difficulté du pire cas n'empêche pas l'existence d'algorithmes pratiques puissants.
Les solveurs exploitent :
- la propagation de contraintes au niveau des lignes ;
- la programmation dynamique ou le filtrage de motifs ;
- la planification intelligente des lignes modifiées ;
- la mise en cache ;
- les vérifications de contradictions ;
- les heuristiques de ramification ;
- le probing ;
- des technologies générales de résolution de contraintes.
Les collections réelles de puzzles contiennent en outre beaucoup plus de structure que des instances théoriques adversariales.
Un solveur peut donc traiter rapidement de nombreux grands puzzles conçus pour l'humain, même si aucune garantie polynomiale n'existe pour le cas général.
Pourquoi cela compte pour la conception de puzzles
Les résultats de complexité ne sont pas qu'une curiosité abstraite.
Ils expliquent pourquoi un générateur doit valider ses candidats au lieu de supposer que tout ensemble d'indices se comportera bien. Un candidat peut être :
- incohérent ;
- ambigu ;
- unique mais très dépendant de la recherche ;
- unique et résoluble de manière fluide.
Les systèmes de construction combinent donc génération, solveur de validation et estimation de difficulté.
Idées reçues fréquentes
« NP-complet signifie que personne ne peut résoudre les nonogrammes efficacement »
Non. Cela signifie qu'aucun algorithme en temps polynomial n'est connu pour toutes les instances, et qu'en trouver un aurait des conséquences majeures en théorie de la complexité.
« Une grille plus grande est exponentiellement difficile par définition »
Non. La taille augmente l'espace de recherche possible, mais une structure d'indices précise peut rendre une grande instance facile.
« Si un puzzle se résout sans deviner, les nonogrammes ne peuvent pas être NP-difficiles »
Des sous-classes faciles peuvent exister à l'intérieur d'un problème général difficile. Les puzzles publiés sont souvent volontairement choisis dans ces régions plus favorables.
« NP signifie non polynomial »
Non. NP est le nom d'une classe de complexité, communément caractérisée par des solutions pouvant être vérifiées en temps polynomial.
Pour aller plus loin
Pour les algorithmes qui rendent la résolution pratique, lisez Comment fonctionnent les solveurs informatiques de nonogrammes. Pour les briques combinatoires derrière les possibilités d'une ligne, consultez Nonogrammes et mathématiques.
FAQ
Les nonogrammes sont-ils NP-complets ?
La forme décisionnelle standard du problème général possède des résultats de NP-complétude dans la littérature. On résume également souvent le problème de résolution plus largement comme NP-difficile.
Cela prouve-t-il que chaque puzzle exige de deviner ?
Non. De nombreux nonogrammes publiés sont volontairement conçus pour être résolus par des déductions logiques locales et de la propagation.
Un ordinateur peut-il tout de même résoudre des nonogrammes difficiles ?
Oui. La NP-complétude n'empêche pas de résoudre efficacement des instances particulières ; elle signifie qu'on ne connaît pas de garantie efficace pour toutes les instances sous les hypothèses classiques de complexité.