Il n'existe aucune formule universelle de difficulté pour les nonogrammes. Un système d'évaluation doit d'abord définir ce qu'il appelle « difficile » : davantage de déductions, des déductions plus avancées, des goulots d'étranglement plus longs, davantage de recherche, des temps de résolution humains plus élevés, ou une combinaison de ces facteurs.
C'est pourquoi deux éditeurs peuvent attribuer des niveaux différents au même puzzle sans qu'aucun ne viole les règles.
La difficulté dépend d'un modèle de résolution
Imaginez deux solveurs.
Le solveur A connaît uniquement le chevauchement de base et la logique des blocs terminés. Le solveur B peut énumérer tous les motifs de ligne valides et utiliser le raisonnement par contradiction.
Le même puzzle peut bloquer le solveur A et se résoudre sans difficulté particulière pour le solveur B.
Un score de difficulté dépend donc en partie de ce que le solveur utilisé pour mesurer est autorisé à faire.
Les travaux académiques sur les nonogrammes rendent ce point explicite en définissant des classes précises de raisonnement, puis en évaluant les puzzles relativement à ces classes.
Signaux courants pour estimer la difficulté
Nombre de passes ou de déductions
Un modèle simple peut compter combien de balayages lignes/colonnes sont nécessaires avant de terminer le puzzle.
Batenburg et ses collègues ont étudié une classe de nonogrammes résolubles par raisonnement local de ligne et défini une mesure de difficulté fondée sur des passages horizontaux et verticaux répétés. Cette mesure est utile précisément parce que la procédure de résolution est définie à l'avance.
Davantage d'étapes signifie généralement davantage de travail dans ce modèle, mais le simple nombre d'étapes ne décrit pas toute l'expérience humaine.
Technique la plus avancée nécessaire
Un puzzle entièrement résolu grâce aux ajustements exacts et aux chevauchements évidents sera généralement plus accessible qu'un puzzle exigeant l'énumération complète des motifs de ligne ou un raisonnement par contradiction.
Un produit peut donc attribuer des poids aux familles de techniques, ou utiliser la technique la plus forte requise comme l'une des composantes de son classement.
Degré de liberté des indices
Les lignes avec peu de marge ont moins de placements possibles. Les lignes qui conservent beaucoup de placements révèlent souvent moins d'information.
On peut mesurer notamment :
- l'extension minimale ;
- la marge ;
- le nombre de motifs de ligne valides ;
- la vitesse à laquelle ces motifs disparaissent lorsque les lignes croisées apportent de nouvelles informations.
Longueur des chaînes de propagation
Certains puzzles révèlent beaucoup de cases immédiatement. D'autres reposent sur de longues chaînes dans lesquelles une petite déduction débloque exactement une ligne croisée, qui en débloque une autre, et ainsi de suite.
Une longue chaîne de dépendances peut augmenter la difficulté même si chaque étape prise isolément reste élémentaire.
Goulots d'étranglement
Un puzzle peut être simple sur 90 % de la grille et tout de même sembler difficile parce qu'un seul état exige une déduction subtile avant que le reste puisse avancer.
Le travail moyen et la difficulté maximale ponctuelle sont donc deux métriques différentes.
Un bon système d'évaluation devrait tenir compte des deux.
Besoin de ramification, de probing ou de contradiction
Si un solveur logique donné atteint un point fixe avec encore des cases indéterminées, une procédure plus forte peut explorer provisoirement des hypothèses ou des branches de recherche.
La présence, la profondeur et la fréquence de cette recherche peuvent constituer des signaux puissants pour une évaluation automatique.
Il faut toutefois les interpréter avec prudence : un solveur limité peut devoir ramifier sur un puzzle qu'un humain résout directement grâce à une technique plus forte.
Pourquoi la taille de la grille est un mauvais score à elle seule
Une grande grille contient davantage de cases et prend souvent plus de temps, mais cela ne signifie pas qu'elle est logiquement plus difficile.
Un grand puzzle avec de longs indices informatifs peut offrir une progression constante. Un puzzle compact composé de petits indices avec beaucoup de marge peut créer un goulot d'étranglement bien plus exigeant.
La taille reste utile comme contexte pour :
- la durée attendue ;
- la charge visuelle ;
- l'effort de balayage ;
- le nombre de lignes à gérer.
Elle ne devrait pas devenir un score logique autonome.
Difficulté humaine vs difficulté informatique
Un ordinateur et une personne n'expérimentent pas un puzzle de la même manière.
Un programme peut exécuter des millions d'opérations pour une procédure conceptuellement simple. Un humain peut percevoir la même déduction presque immédiatement.
À l'inverse, un ordinateur peut comparer parfaitement des centaines de motifs de ligne alors que ce suivi serait épuisant à faire manuellement.
Une évaluation orientée humain peut donc intégrer :
- les temps de résolution observés ;
- les taux de réussite ;
- l'utilisation des indices ou aides ;
- les taux d'erreur ;
- le niveau des joueurs ;
- les déductions réellement remarquées par les personnes.
Ces données complètent les caractéristiques fournies par un solveur plutôt qu'elles ne les remplacent.
La difficulté peut être ciblée pendant la génération
La difficulté n'est pas seulement quelque chose que l'on mesure après la création d'un puzzle.
Des travaux de recherche ont utilisé des solveurs proches du raisonnement humain à l'intérieur même de systèmes de génération : les nonogrammes candidats sont évalués selon la progression du solveur modélisé, puis l'image ou le puzzle est modifié pour se rapprocher d'une plage de difficulté souhaitée.
D'autres méthodes d'optimisation recherchent également des puzzles évalués comme difficiles et intéressants selon un modèle choisi.
Cela renforce un principe important :
une étiquette de difficulté n'a de sens que relativement à un modèle et à un processus de calibration définis.
Ce qu'une future évaluation VeyraPlay devrait considérer
Cette Guide ne fige pas la formule de production de VeyraPlay. Celle-ci devra être calibrée avec le moteur réel et, plus tard, avec des données de joueurs.
Un système robuste pourrait combiner :
- la solvabilité avec des ensembles de techniques progressivement plus puissants ;
- le nombre total de déductions forcées ;
- le nombre et la sévérité des goulots d'étranglement ;
- le nombre de motifs de ligne ;
- la profondeur de propagation ;
- les besoins en contradiction ou recherche ;
- la taille de la grille comme contexte de charge de travail ;
- les comportements réels des joueurs lorsque suffisamment de données existeront.
La décision architecturale importante consiste à séparer l'étiquette de difficulté des preuves de difficulté, afin que le classement puisse évoluer sans modifier l'identité logique du puzzle.
Idées reçues fréquentes
« Difficile signifie grand »
Grand signifie souvent plus long. Pas nécessairement plus difficile logiquement.
« Unique signifie assez facile à résoudre »
L'unicité indique qu'il existe une seule réponse, pas la difficulté nécessaire pour la prouver.
« Une note générée par ordinateur est objective »
Elle est reproductible selon son algorithme, mais cet algorithme contient toujours des choix sur les opérations comptées et leur pondération.
« La technique la plus difficile suffit pour noter le puzzle »
Deux puzzles peuvent exiger la même technique tout en différant fortement par sa fréquence, sa visibilité et la longueur de la chaîne de dépendances nécessaire.
Pour aller plus loin
Pour l'aspect algorithmique, poursuivez avec Comment fonctionnent les solveurs informatiques de nonogrammes. Pour comprendre pourquoi certaines instances deviennent difficiles en théorie, lisez Pourquoi les nonogrammes sont difficiles sur le plan informatique.
FAQ
Existe-t-il une norme officielle Facile/Moyen/Difficile pour les nonogrammes ?
Non. Les éditeurs peuvent définir et calibrer leurs propres échelles.
Peut-on calculer la difficulté avant que des joueurs résolvent le puzzle ?
Oui. Un modèle fondé sur un solveur peut l'estimer. Les données de joueurs peuvent ensuite améliorer la calibration.
Deux nonogrammes de même taille peuvent-ils avoir des difficultés très différentes ?
Absolument. Leur structure d'indices, leurs placements valides, leurs chaînes de propagation et les raisonnements nécessaires peuvent être très différents.