Un nonogramme possède une solution unique lorsqu'une seule grille complète de cases remplies et vides satisfait tous les indices de lignes et tous les indices de colonnes.
Si deux grilles différentes ou davantage satisfont les mêmes indices, le puzzle est ambigu. Si aucune grille ne les satisfait, l'ensemble d'indices est contradictoire.
Pour un puzzle logique conventionnel destiné à être publié, l'unicité est normalement une condition de validité de base.
Un nonogramme ambigu minimal
Prenons une grille 2×2 avec les indices suivants :
Lignes : 1, 1
Colonnes : 1, 1Il existe deux solutions :
■ × × ■
× ■ ■ ×Chaque ligne contient une case remplie. Chaque colonne en contient également une. Rien dans les indices ne distingue les deux diagonales.
Le puzzle n'est pas « difficile parce que vous n'avez pas trouvé l'astuce ». Il est sous-déterminé : les deux réponses sont logiquement valides.
Que signifie réellement « unique » ?
L'unicité est une propriété de l'ensemble du système d'indices.
Une solution doit satisfaire simultanément toutes les contraintes de lignes et de colonnes. Le puzzle n'est unique que si toute autre grille complète viole au moins l'une de ces contraintes.
C'est plus exigeant que de dire :
- l'image prévue respecte les indices ;
- vous avez personnellement trouvé une solution ;
- l'image finale semble reconnaissable ;
- une méthode de résolution donnée a produit une réponse.
Trouver une grille valide prouve qu'une solution existe. Cela ne prouve pas qu'il n'en existe pas une autre.
Unique ne signifie pas facile
Cette distinction est fondamentale.
Un puzzle peut avoir exactement une solution tout en résistant aux déductions ordinaires ligne par ligne et colonne par colonne. La solution peut être déterminée globalement même lorsqu'aucun coup local immédiat n'est visible.
Ces affirmations sont donc différentes :
- Le puzzle possède une solution.
- Le puzzle peut être résolu avec les techniques qu'un humain ou un solveur particulier utilise.
- Le puzzle est facile pour son public cible.
Un validateur d'unicité répond à la première question. Un modèle de difficulté et une analyse du parcours de résolution s'intéressent aux autres.
Pourquoi l'ambiguïté apparaît
L'ambiguïté apparaît lorsque les indices laissent certaines structures interchangeables.
Parmi les causes fréquentes :
Alternatives symétriques
Deux groupes de cases peuvent échanger leurs positions tout en conservant exactement les mêmes longueurs de blocs dans toutes les lignes et colonnes.
Structure d'indices trop faible
De nombreux petits indices dans de grands espaces ouverts peuvent autoriser plusieurs placements que les lignes croisées ne parviennent jamais à distinguer complètement.
Régions indépendantes
Un puzzle peut contenir deux sous-structures non résolues qui peuvent chacune basculer entre plusieurs alternatives sans modifier le reste de la grille.
Modifications de construction qui préservent le comportement des indices
Changer une image ne renforce pas toujours son système de contraintes. Certaines retouches déplacent simplement l'incertitude ailleurs.
Comment les créateurs vérifient l'unicité
Pour de très petits puzzles, il est théoriquement possible d'examiner toutes les grilles.
Pour des tailles réalistes, les logiciels utilisent des méthodes plus efficaces de résolution de contraintes et de recherche. Un solveur peut :
- trouver une première solution complète ;
- poursuivre la recherche d'une solution complète différente ;
- s'arrêter dès qu'une deuxième solution est trouvée, ou prouver qu'aucune alternative ne subsiste.
Des outils comme pbnsolve de WebPBN utilisent ce type de validation pour les puzzles créés par les utilisateurs.
La logique peut-elle prouver l'unicité pendant la résolution ?
Si une suite de déductions correctes part uniquement des indices et remplit toutes les cases sans ramification, le résultat est nécessairement la seule solution compatible avec ces déductions et ces contraintes.
Mais si une méthode classique de résolution de lignes se bloque, vous ne pouvez pas conclure que le puzzle est ambigu. La déduction manquante peut exiger une logique plus forte, un solveur de ligne plus complet, un raisonnement par contradiction ou une recherche.
De même, si votre méthode trouve une réponse grâce à une ramification, cela ne prouve pas automatiquement l'unicité. Il faut tenir compte des autres branches non explorées.
Pourquoi une image reconnaissable ne résout pas l'ambiguïté
Supposons qu'une solution valide ressemble clairement à un chat et qu'une autre paraisse légèrement déformée.
Choisir le chat parce qu'il semble intentionnel n'est pas une déduction de nonogramme. Les indices n'ont pas prouvé ce choix.
Un puzzle correctement validé ne devrait jamais nécessiter une préférence esthétique pour départager plusieurs grilles légales.
L'image qui apparaît peut vous aider à vous orienter, mais elle ne constitue jamais une preuve pour l'état d'une case.
Solution unique vs parcours de résolution unique
Une solution unique n'implique pas un ordre unique de déductions.
Deux joueurs peuvent résoudre le même puzzle valide dans des séquences différentes :
- l'un commence par une longue ligne ;
- l'autre par une colonne très contrainte ;
- les deux finissent par imposer la même grille finale.
La destination est unique même si le chemin ne l'est pas.
C'est une propriété intéressante pour le design : un nonogramme peut offrir plusieurs ouvertures productives sans devenir ambigu.
Que faire si un nonogramme publié possède plusieurs solutions ?
Si les règles sont standards et que deux grilles complètes satisfont réellement tous les indices, le puzzle est ambigu, quelle que soit l'image prévue par l'éditeur.
Avant de conclure qu'un puzzle est incorrect, vérifiez que :
- l'ordre des indices est respecté ;
- les blocs consécutifs sont correctement séparés ;
- chaque X est traité comme une case vide et non comme une case indéterminée ;
- aucun bloc rempli ne dépasse accidentellement la longueur de son indice ;
- l'éditeur n'utilise pas une variante de règles.
Si les deux grilles satisfont toujours les mêmes règles standards, l'ensemble d'indices ne détermine pas une réponse unique.
Pour aller plus loin
Pour comprendre comment les créateurs détectent ces situations, lisez Comment fonctionnent les solveurs informatiques de nonogrammes. Pour voir pourquoi unicité et difficulté humaine peuvent diverger, poursuivez avec Comment la difficulté d'un nonogramme est évaluée.
FAQ
Tous les nonogrammes ont-ils une solution unique ?
Non. Un ensemble arbitraire d'indices peut avoir zéro, une ou plusieurs solutions. Les puzzles publiés et bien construits visent normalement exactement une solution.
Si je suis bloqué, cela signifie-t-il que le puzzle possède plusieurs solutions ?
Non. Il peut simplement exiger une déduction que vous n'avez pas trouvée ou un raisonnement plus puissant.
Un nonogramme peut-il avoir une solution unique tout en exigeant de deviner ?
Il peut avoir une solution unique tout en résistant à une méthode locale donnée. Appeler une analyse de cas plus forte « deviner » dépend de la façon dont le raisonnement est mené ; G-011 distingue le choix sans preuve du raisonnement fondé sur une contradiction démontrable.