Un solveur informatique de nonogrammes alterne généralement entre deux tâches : résoudre chaque ligne selon les contraintes actuelles et propager chaque nouvelle case forcée vers les lignes qui la croisent. Si ce processus atteint un point fixe avant que la grille soit complète, les solveurs plus puissants peuvent tester provisoirement des hypothèses ou explorer les possibilités restantes par ramification.
Les programmes diffèrent dans leurs détails, mais la structure analyse de ligne → propagation → recherche constitue un bon modèle pour les comprendre.
1. Représenter le puzzle comme un système de contraintes
Le solveur stocke :
- les séquences d'indices des lignes ;
- les séquences d'indices des colonnes ;
- l'état actuel de chaque case : remplie, vide ou indéterminée.
Chaque ligne ou colonne est un problème unidimensionnel : trouver les placements de ses blocs d'indices qui respectent toutes les cases déjà connues.
Une grille complète n'est valide que si chaque ligne possède au moins un placement compatible et si toutes les cases concordent à l'intersection de leur ligne et de leur colonne.
2. Résoudre une ligne
Un solveur de ligne cherche à déterminer quelles cases sont forcées par les indices de cette ligne et ses états actuellement connus.
Plusieurs stratégies d'implémentation sont possibles.
Une méthode pratique documentée par pbnsolve de WebPBN consiste à trouver un placement légal avec les blocs poussés aussi loin que possible vers une extrémité, puis un autre vers l'extrémité opposée. Les cases occupées par le même bloc dans les deux placements extrêmes peuvent être marquées remplies ; certaines cases situées de façon certaine entre les mêmes blocs peuvent être marquées vides.
Des solveurs de ligne plus complets peuvent énumérer, ou calculer dynamiquement, tous les motifs de ligne valides compatibles avec l'état actuel et en prendre l'intersection.
3. Remettre les lignes croisées affectées dans la file de travail
Supposons qu'un solveur de ligne prouve que la case R4C7 est remplie.
La colonne 7 possède maintenant une nouvelle information. Une bonne implémentation n'a pas besoin de recommencer aveuglément toute la grille : elle peut simplement programmer cette colonne pour une nouvelle analyse.
Si cette colonne force ensuite des cases dans les lignes 2 et 8, ces lignes deviennent à leur tour candidates au retraitement.
C'est la version informatique du même rythme lignes-colonnes que les joueurs humains utilisent.
4. Continuer jusqu'à ce que la propagation atteigne un point fixe
Le solveur traite les lignes utiles jusqu'à ce que :
- toutes les cases soient déterminées ;
- une contradiction apparaisse ;
- aucune ligne ne puisse forcer une nouvelle case.
Le troisième état est un point fixe pour la méthode de résolution actuelle. Cela ne signifie pas automatiquement que le puzzle possède plusieurs solutions ni qu'il est impossible à résoudre logiquement. Cela signifie simplement que ce moteur d'inférence particulier ne progresse plus directement.
Un solveur de ligne plus puissant peut encore découvrir un état forcé qu'une routine plus rapide n'a pas trouvé.
5. Détecter les contradictions
Une contradiction apparaît lorsque les hypothèses actuelles rendent une contrainte impossible.
Exemples :
- une ligne ne possède plus aucun placement valide ;
- un bloc confirmé est plus long que son indice ;
- un bloc obligatoire ne peut plus tenir nulle part ;
- une case est forcée à la fois remplie et vide par des branches incompatibles.
Dans une représentation par motifs, une ligne avec zéro motif valide est impossible.
La détection des contradictions est donc utile à la fois pour valider l'état d'un joueur et pour piloter les algorithmes de recherche.
6. Utiliser le probing ou la recherche lorsque la logique directe se bloque
Un solveur général complet peut devoir explorer des alternatives.
Une approche simple en profondeur peut :
- choisir une case indéterminée ou une décision de bloc ;
- supposer un état légal ;
- relancer la propagation ;
- poursuivre si la branche reste possible ;
- revenir en arrière si elle atteint une contradiction.
Une stratégie de probing explore provisoirement des hypothèses candidates et mesure leurs conséquences avant de décider quelle branche poursuivre. pbnsolve de WebPBN documente ce type d'approche en détail.
L'idée importante est qu'un ordinateur peut utiliser la recherche pour garantir la complétude même lorsque la logique destinée aux humains n'avance plus.
7. Vérifier l'unicité
Pour valider un puzzle, trouver une solution ne suffit pas.
Un solveur peut continuer la recherche après la première solution et demander s'il existe une deuxième complétion distincte.
Les résultats possibles sont :
- zéro solution → ensemble d'indices incohérent ;
- une solution → puzzle unique ;
- deux solutions ou plus → puzzle ambigu.
Les solveurs automatisés sont donc utiles non seulement pour jouer, mais aussi pour les pipelines de création et de publication.
Tous les solveurs n'utilisent pas le même algorithme
Les nonogrammes peuvent être modélisés dans plusieurs cadres informatiques.
Les implémentations peuvent combiner :
- des solveurs de ligne spécialisés ;
- de la programmation dynamique ;
- de la programmation par contraintes ;
- des contraintes booléennes de type SAT ;
- de la programmation en nombres entiers ;
- de la recherche en profondeur ;
- de la recherche heuristique ;
- du probing et de la mise en cache.
La recherche académique a comparé des solveurs spécialisés et proposé différentes formulations mathématiques. Il n'existe pas une architecture unique obligatoire.
Ce qui définit la correction, c'est que l'algorithme respecte les indices et les états de case et que, lorsqu'il affirme être complet ou prouver l'unicité, il explore suffisamment l'espace des solutions pour justifier cette affirmation.
Logique de ligne rapide vs logique de ligne complète
Un compromis subtil apparaît dans l'implémentation : une routine de ligne très rapide ne déduit pas forcément toutes les cases forcées disponibles sur cette ligne.
WebPBN précise que sa routine de chevauchement gauche/droite est rapide mais pas complète ; pbnsolve peut donc effectuer un contrôle plus exhaustif après que la résolution ordinaire des lignes s'est bloquée.
Cela ressemble à la différence humaine entre :
- une technique visuelle peu coûteuse qui révèle rapidement beaucoup de cases ;
- une analyse complète des motifs valides, plus coûteuse mais capable de révéler des cases supplémentaires.
Comment un solveur peut évaluer la difficulté
Lorsqu'un solveur enregistre son propre travail, il peut produire des caractéristiques comme :
- nombre de résolutions de lignes ;
- nombre de tours de propagation ;
- inférence la plus forte nécessaire ;
- nombre de motifs examinés ;
- nombre de probes ou de branches ;
- profondeur maximale de recherche.
Ces caractéristiques peuvent alimenter un modèle de difficulté, même si elles décrivent toujours la difficulté relativement à l'architecture de ce solveur.
Pourquoi le problème général peut malgré tout être difficile
Un solveur spécialisé peut rendre les nonogrammes ordinaires de livres de puzzles presque triviaux, mais on ne connaît pas de méthode en temps polynomial capable de résoudre toutes les instances possibles sauf bouleversement majeur des hypothèses classiques de théorie de la complexité.
C'est une affirmation sur le pire cas, pas une déclaration selon laquelle votre nonogramme quotidien 15×15 devrait nécessiter un supercalculateur.
Pour aller plus loin
Pour comprendre la difficulté dans le pire cas, poursuivez avec Pourquoi les nonogrammes sont difficiles sur le plan informatique. Pour l'équivalent humain des hypothèses provisoires, revenez à Raisonnement par contradiction.
FAQ
Les solveurs de nonogrammes testent-ils simplement toutes les grilles par force brute ?
Les bons solveurs n'en ont pas besoin. Ils utilisent les contraintes de lignes et la propagation pour éliminer énormément de possibilités avant toute recherche, et de nombreux puzzles publiés se résolvent sans ramification profonde.
Un solveur peut-il prouver qu'un puzzle est unique ?
Oui, s'il effectue une recherche suffisamment complète pour exclure toute solution alternative.
Les méthodes informatiques et humaines sont-elles les mêmes ?
Elles se recoupent conceptuellement, surtout autour de la logique de ligne et de la propagation, mais un ordinateur peut suivre beaucoup plus d'états candidats et utiliser une recherche systématique qui serait fastidieuse pour une personne.