Les nonogrammes demandent très peu d'arithmétique pendant la partie, mais sous leur apparence simple se cache un problème combinatoire de contraintes.
Chaque indice décrit des blocs ordonnés de cases remplies sur une ligne. Les contraintes de lignes et de colonnes se croisent sur les mêmes cases, et résoudre le puzzle revient à trouver la grille binaire qui les satisfait toutes simultanément.
Les indices sont des descriptions par longueurs de séries
Une séquence d'indices enregistre les longueurs des blocs consécutifs de cases remplies.
Par exemple :
■■■ ×× ■■ × ■
3 2 1Les nombres ne donnent pas la position de départ des blocs. Ils indiquent :
- leurs longueurs ;
- leur ordre ;
- que deux blocs monochromes voisins doivent être séparés par au moins une case vide.
C'est pourquoi une séquence d'indices est bien plus qu'une simple somme.
Extension minimale
Supposons qu'une ligne possède m blocs d'indices de longueurs :
c1, c2, ..., cmLes cases remplies occupent :
c1 + c2 + ... + cmcases, et les m - 1 frontières entre blocs consécutifs exigent chacune au moins une case vide.
L'espace minimal capable de contenir tous les indices est donc :
extension minimale = somme(indices) + (nombre d'indices - 1)Pour une ligne de 10 cases avec les indices 3 2 :
extension minimale = 3 + 2 + 1 = 6Il reste donc quatre cases de liberté de placement.
Cet espace supplémentaire est la marge.
Combien de placements une séquence d'indices peut-elle avoir sur une ligne vide ?
Pour une ligne monochrome autrement sans contrainte, la marge peut être répartie :
- avant le premier bloc ;
- après le dernier bloc ;
- comme cases vides supplémentaires dans n'importe quel espace obligatoire entre les blocs.
S'il y a m blocs et une marge s, le nombre de placements complets est :
C(s + m, m)où C désigne le coefficient binomial.
Exemple : longueur 10 avec les indices 3 2
Nous avons déjà :
extension minimale = 6
marge = 10 - 6 = 4
m = 2Le nombre de motifs complets légaux sur une ligne entièrement indéterminée est donc :
C(4 + 2, 2) = C(6, 2) = 15Ce nombre décrit la ligne de départ sans autre contrainte. Dès que certaines cases sont connues comme remplies ou vides, une partie de ces 15 possibilités disparaît.
Pourquoi le chevauchement fonctionne mathématiquement
Une case est forcée remplie lorsque tous les motifs valides compatibles avec les contraintes actuelles la remplissent.
De la même façon, une case est forcée vide lorsque tous les motifs valides la laissent vide.
Le chevauchement est un raccourci humain rapide pour trouver certaines de ces cases communes sans lister explicitement toutes les possibilités.
La technique plus avancée des motifs de ligne valides rend cette idée explicite : on raisonne sur l'ensemble des motifs encore légaux, puis on conserve les états sur lesquels ils sont tous d'accord.
Lignes et colonnes forment des contraintes qui se croisent
Un indice de ligne limite une chaîne binaire horizontale. Un indice de colonne limite une chaîne binaire verticale.
Chaque case appartient exactement à une ligne et une colonne ; les deux systèmes sont donc couplés.
Quand une ligne prouve qu'une case est remplie, cette valeur devient fixe dans la colonne correspondante. Certains motifs de cette colonne disparaissent. La colonne réduite peut alors forcer une nouvelle case, qui à son tour modifie une autre ligne.
Cette réduction répétée est la propagation des contraintes.
Un nonogramme ne se résout pas en additionnant les indices
Les sommes sont utiles pour calculer l'extension minimale ou l'occupation totale, mais le puzzle dépend aussi des positions et de l'ordre.
Deux séquences d'indices peuvent avoir le même nombre total de cases remplies et se comporter très différemment :
6
3 3
2 2 2Toutes représentent six cases remplies, mais les séparateurs obligatoires et l'identité des blocs produisent des espaces de placement différents.
C'est pourquoi « les indices s'additionnent jusqu'à la longueur de la ligne » n'est suffisant que dans les cas d'ajustement exact, lorsque les séparateurs obligatoires sont eux aussi correctement comptés.
La combinatoire croît rapidement
Même une ligne individuelle peut admettre de nombreuses dispositions légales lorsqu'elle contient plusieurs petits blocs et beaucoup de marge.
À l'échelle d'une grille entière, les possibilités des lignes ne peuvent pas être choisies indépendamment puisque toutes les colonnes doivent également respecter leurs indices.
Le puzzle devient donc un système de nombreuses variables binaires interdépendantes, et non une simple collection d'exercices séparés de placement de blocs.
C'est dans cette interaction que peuvent apparaître des instances difficiles sur le plan informatique.
Pourquoi ces mathématiques aident les joueurs humains
Vous n'avez pas besoin de calculer des coefficients binomiaux pendant une partie.
Mais la structure mathématique explique plusieurs règles pratiques :
- faible marge signifie moins de placements ;
- ajustement exact signifie un seul placement ;
- chevauchement trouve des cases communes à des placements extrêmes ou valides ;
- les X éliminent des placements candidats ;
- les cases remplies restreignent l'identité des blocs capables de les atteindre ;
- le croisement lignes-colonnes transfère les contraintes entre deux systèmes ;
- une contradiction prouve qu'une branche possède zéro complétion valide.
Les techniques du reste du corpus sont des façons adaptées aux humains d'exploiter ces contraintes sans énumérer manuellement tout l'espace de recherche.
Un nonogramme est-il un puzzle mathématique ?
On peut raisonnablement le qualifier de puzzle de logique mathématique, mais aucune mathématique avancée n'est nécessaire pour résoudre les nonogrammes publiés ordinaires.
La plupart des parties reposent sur :
- compter des cases ;
- comparer des longueurs ;
- préserver l'ordre ;
- éliminer les placements impossibles ;
- propager des conséquences.
La combinatoire plus profonde devient surtout utile pour analyser les algorithmes, les générateurs, la difficulté et la complexité dans le pire cas.
Pour aller plus loin
Pour une version pratique de l'idée d'ensemble de placements, lisez Motifs de ligne valides. Pour la résolution algorithmique, poursuivez avec Comment fonctionnent les solveurs informatiques de nonogrammes. Pour la théorie de la complexité, lisez Pourquoi les nonogrammes sont difficiles sur le plan informatique.
FAQ
Quelle est la formule de l'extension minimale pour les indices d'un nonogramme ?
Pour des indices monochromes standards, additionnez toutes les valeurs puis ajoutez une case vide obligatoire pour chaque frontière entre deux blocs consécutifs.
La formule du nombre de placements s'applique-t-elle toujours ?
La formule simple C(s + m, m) s'applique à une ligne autrement sans contrainte avec la séparation monochrome standard. Les cases déjà remplies ou vides et les attributions à des segments réduisent ensuite cet ensemble.
Faut-il connaître la combinatoire pour résoudre des nonogrammes ?
Non. Les techniques standards transforment les conséquences utiles de cette combinatoire en déductions visuelles bien plus faciles à appliquer à la main.