La propagation des contraintes est le processus répété qui consiste à appliquer les nouveaux états de case confirmés à leurs lignes croisées, à y chercher leurs conséquences puis à poursuivre jusqu’à ce qu’aucune déduction immédiate ne reste.
Une cascade est la chaîne visible de déductions produite par ce processus.
Exemple de cascade sur une grille cinq par cinq
Considérez un nonogramme monochrome 5×5 avec les indices suivants :
Lignes : 1, 3, 5, 3, 1
Colonnes : 1, 3, 5, 3, 1
La ligne 3 est un ajustement exact puisque l’indice 5 remplit toute la ligne. Remplissez ses cinq cases.
Propagez maintenant :
- les colonnes 1 et 5 ont chacune l’indice
1, déjà satisfait par la case centrale remplie : toutes leurs autres cases sont donc vides ; - la colonne 3 possède l’indice
5et se remplit entièrement ; - les lignes 1 et 5 ont maintenant leur unique case requise en colonne 3 : leurs autres cases deviennent vides ;
- les colonnes 2 et 4, chacune avec l’indice
3, sont désormais forcées à remplir les lignes 2 à 4 ; - les lignes 2 et 4 deviennent des blocs complets de trois.
Une seule ligne en ajustement exact résout toute la grille grâce à la propagation.
La propagation n’est pas une source de vérité séparée
Chaque étape individuelle utilise toujours une déduction ordinaire et valide : ajustement exact, bloc terminé, chevauchement, élimination des espaces, filtrage de motifs, etc.
La propagation décrit comment ces déductions sont ordonnées et enchaînées à travers la grille partagée.
Pourquoi les cascades semblent plus rapides qu’un nouveau balayage complet
Après le changement d’une case, seules sa ligne et sa colonne reçoivent directement une nouvelle information.
Plutôt que de recommencer tout le puzzle depuis le début, suivez donc les lignes affectées. Si elles modifient une autre case, examinez ensuite la ligne croisée de cette case.
Votre attention reste ainsi concentrée là où le système de contraintes a réellement changé.
Propagez les deux formes de certitude
Une cascade peut être déclenchée aussi bien par des remplissages que par des X.
Par exemple :
- une case remplie peut ancrer un bloc ;
- un X peut diviser un segment ;
- cette division peut attribuer un indice ;
- cette attribution peut créer un ajustement exact ;
- l’ajustement exact peut terminer un bloc croisé ;
- son séparateur peut éliminer une autre zone.
Il n’existe pas de hiérarchie où les cases remplies constitueraient le « vrai progrès » et les cases vides un détail secondaire. Les deux réduisent l’ensemble des motifs légaux.
Arrêtez seulement à un état stable
Une passe de propagation est terminée lorsque chaque ligne affectée par de nouvelles cases a été réexaminée et qu’aucun nouvel état certain n’en découle.
Les solveurs informatiques appellent souvent cela un point fixe : répéter les mêmes déductions de ligne ne modifierait plus la grille.
À ce moment, choisissez une nouvelle ligne non résolue prometteuse ou, sur un puzzle réellement difficile, passez à un raisonnement plus fort.
Une cascade peut commencer sans aucune ligne en ajustement exact
L’exemple du losange commence par une ligne entièrement évidente. Les cascades plus intéressantes peuvent partir d’un consensus beaucoup plus faible.
Considérez ce puzzle 5×5 :
Lignes : 2 1, 1 1, 2, 2, 1 1
Colonnes : 1 2, 1 2, 2, 1, 2
Aucune ligne ni colonne n’est un ajustement exact au départ. Pourtant, dans la ligne 1 avec l’indice 2 1, une seule case est remplie dans tous les motifs initiaux valides : la case 2.
Marquez R1C2 remplie et ne propagez que les états obtenus par consensus. Cette nouvelle information restreint la colonne 2 ; cette colonne crée de nouveaux états dans les lignes 2 et 4 ; ces lignes contraignent d’autres colonnes ; et le processus continue jusqu’à ce que chaque case soit fixée.
La solution unique est :
■■××■
××■×■
×■■××
■■×××
■××■×
Cet exemple montre pourquoi la propagation est plus que « résoudre d’abord toutes les lignes faciles ». Une modeste déduction sur une ligne peut devenir décisive parce que la grille l’amplifie continuellement via les contraintes perpendiculaires.
Utilisez une file de lignes modifiées au lieu de tout rebalayer
Une façon précise de penser la propagation manuelle est une file :
- lorsqu’une case change, ajoutez sa ligne et sa colonne à la file ;
- prenez une ligne modifiée et résolvez-la avec l’état actuel ;
- si cette ligne modifie des cases, ajoutez leurs lignes perpendiculaires ;
- retirez la ligne traitée ;
- continuez jusqu’à ce que la file soit vide.
Une même ligne peut revenir plusieurs fois dans la file à mesure que de nouvelles informations croisées arrivent. C’est normal.
Les solveurs informatiques emploient souvent le même principe d’ordonnancement : une ligne inchangée n’a reçu aucune information nouvelle et n’a donc pas besoin d’être immédiatement recalculée.
Un point fixe dépend de la puissance du solveur de ligne utilisé
Il existe ici une nuance avancée importante.
Si votre analyse de ligne ne vérifie que le chevauchement simple, vous pouvez atteindre un état où le chevauchement simple ne produit plus rien. Cela ne signifie pas qu’un véritable point fixe logique a été atteint.
Un solveur de ligne plus fort, qui considère tous les motifs valides, peut encore trouver de nouvelles cases et relancer la propagation.
Lorsque vous dites « la propagation est épuisée », précisez donc quel moteur de déduction vous êtes en train de propager :
- point fixe du chevauchement de base ;
- point fixe de l’analyse complète des motifs de ligne ;
- ou point fixe plus fort, multilignes/global.
Cela explique pourquoi un puzzle peut sembler bloqué alors qu’aucune devinette n’est réellement nécessaire.
Propagation et motifs de ligne valides
Le raisonnement par motifs fournit une vue formelle très claire.
Chaque ligne et colonne possède un ensemble de motifs valides. Lorsqu’une case devient remplie ou vide :
- les motifs incompatibles disparaissent de la ligne croisée ;
- les motifs survivants peuvent alors s’accorder sur une autre case ;
- cette nouvelle case forcée filtre une autre ligne perpendiculaire ;
- le processus recommence.
C’est exactement ce qu’accomplit une cascade logique.
Flux pratique de propagation
- gardez une petite file mentale des lignes modifiées par vos derniers mouvements ;
- traitez une ligne modifiée avec la technique de ligne la plus forte qui s’applique ;
- chaque fois que vous marquez une nouvelle case, ajoutez sa ligne perpendiculaire à la file ;
- évitez de recontrôler sans cesse des lignes inchangées ;
- continuez jusqu’à ce que la file ne produise plus d’état nouveau ;
- reprenez ensuite le balayage général pour chercher un nouveau point d’entrée.
Sur les grandes grilles, ce flux est bien plus efficace que de recommencer à la première ligne après chaque déduction.
Erreurs fréquentes
S’arrêter après la première conséquence
Une nouvelle case peut déclencher plusieurs étapes supplémentaires. Suivez la chaîne jusqu’à ce qu’elle se stabilise.
Propager une hypothèse incertaine comme si elle était un fait
La propagation ordinaire utilise des états confirmés. Si vous testez volontairement une hypothèse, gardez cette branche clairement séparée : c’est du raisonnement par contradiction.
Ignorer les cascades de cases vides
Les X peuvent être l’étape décisive qui divise une ligne ou termine un bloc.
Recontrôler toutes les lignes sans discrimination
Donnez la priorité aux lignes touchées par les cases modifiées.
Que faut-il apprendre ensuite ?
Si la propagation atteint un état stable tout en laissant des cases non résolues, certains puzzles experts exigent une hypothèse contrôlée : testez un état candidat, propagez uniquement ses conséquences logiques et rejetez-le s’il produit une impossibilité. C’est le raisonnement par contradiction.
FAQ
La propagation des contraintes est-elle la même chose que le croisement lignes-colonnes ?
Le croisement est un transfert entre deux lignes perpendiculaires. La propagation est le système répété de transferts jusqu’à ce qu’aucune conséquence immédiate ne reste.
La propagation implique-t-elle de deviner ?
Non. La propagation standard utilise uniquement des états de case déjà prouvés.
Une seule déduction simple peut-elle résoudre tout un puzzle ?
Oui. Certains puzzles contiennent de longues cascades où une seule ligne forcée au début produit suffisamment de conséquences pour terminer toute la grille.