Les indices d’un nonogramme ne donnent pas seulement la longueur des blocs. Ils fixent aussi l’ordre de ces blocs. Cet ordre crée une position légale la plus tôt et la plus tard pour chaque bloc d’indice, même avant que sa position exacte soit connue.
Exemple : indices 2 3 sur une ligne de dix cases
Prenez une ligne vide de 10 cases avec les indices 2 3.
Le premier bloc peut commencer dès la case 1. Mais il ne peut pas commencer arbitrairement tard : il doit laisser au moins un séparateur et suffisamment de place au bloc de trois qui suit.
Son dernier départ possible est la case 5 ; sa portée potentielle couvre donc les cases 1 à 6.
Le second bloc ne peut pas commencer avant la case 4, car le premier bloc de deux et un séparateur obligatoire doivent apparaître avant lui. Son dernier départ possible est la case 8, ce qui lui permet d’atteindre la case 10.
Aucune case n’est nécessairement forcée remplie à ce stade, mais les deux blocs possèdent déjà des territoires légaux différents parce que l’ordre des indices leur interdit d’échanger leur place.
Placement le plus tôt
Le placement le plus tôt d’un bloc est la position la plus à gauche ou la plus haute qu’il puisse occuper tout en conservant une solution possible pour tous les indices précédents, séparateurs, cases remplies et X connus.
Pour les blocs tardifs, cette limite dépend de tout ce qui doit les précéder.
Placement le plus tard
Le placement le plus tard est la position la plus à droite ou la plus basse qu’un bloc puisse occuper tout en laissant suffisamment d’espace légal pour chaque indice qui suit.
Pour les blocs précoces, cette limite dépend fortement des blocs placés après eux.
Pourquoi l’ordre est essentiel sur les lignes à plusieurs indices
Si une ligne possède les indices 2 5 3, il ne s’agit pas de trois blocs interchangeables. Le 2 doit venir en premier, le 5 en deuxième et le 3 en dernier.
Un fragment rempli proche du bord droit peut physiquement tenir dans un bloc de longueur 2, mais il ne peut pas être l’indice 2 si cette attribution ne laisse plus aucune place aux indices 5 3 ensuite.
C’est pourquoi la portée des blocs doit être calculée avec leur identité dans la séquence et leur ordre, pas uniquement avec leur longueur.
Exemple détaillé : des cases connues resserrent trois plages ordonnées
Prenez une ligne de 12 cases avec les indices 2 4 2. La case 4 est confirmée vide et la case 8 confirmée remplie :
???×???■????
Il reste exactement six motifs de ligne complets compatibles avec ces états.
Dans ces six motifs, les positions de départ légales sont :
| Bloc d’indice | Départ le plus tôt | Départ le plus tard |
|---|---|---|
premier 2 | 1 | 2 |
4 central | 5 | 6 |
dernier 2 | 10 | 11 |
L’identité des blocs compte. Nous ne cherchons pas où « un bloc de 2 » peut aller, mais où peuvent aller le premier et le dernier bloc de 2 tout en gardant le 4 central entre eux.
Ces limites impliquent immédiatement plusieurs états communs :
- la case 2 est couverte par le premier bloc dans tous les motifs valides ;
- les cases 6 à 8 sont couvertes par le bloc central dans tous les motifs valides ;
- la case 11 est couverte par le dernier bloc dans tous les motifs valides ;
- la case 4 reste vide d’après la contrainte donnée.
Les limites ne sont donc pas de simples plages descriptives. Lorsqu’elles deviennent assez étroites, elles révèlent le chevauchement propre à chaque bloc ordonné.
Les limites sont couplées, pas indépendantes
Il est tentant de calculer une plage pour chaque indice puis de traiter ces plages séparément. Sur une ligne à plusieurs indices, cela peut être faux.
Déplacer un bloc plus tard peut pousser le bloc suivant plus loin, car un séparateur obligatoire doit rester entre eux. Déplacer le dernier bloc plus tôt peut tirer le bloc précédent vers la gauche pour la même raison.
Imaginez les blocs ordonnés comme une chaîne de plages couplées :
- les blocs précoces poussent les blocs tardifs vers la droite ou le bas ;
- les blocs tardifs poussent les blocs précoces vers la gauche ou le haut ;
- les X et les frontières de segment peuvent découper la chaîne en sous-problèmes ;
- des fragments remplis connus peuvent ancrer un bloc et resserrer ses deux voisins.
C’est pourquoi recalculer les limites depuis les deux extrémités est plus fiable que d’estimer séparément la portée de chaque indice.
Limites de placement ou analyse complète des motifs valides ?
Deux lignes peuvent avoir les mêmes limites extrêmes tout en différant dans les combinaisons intermédiaires qui restent légales. Les placements extrêmes compressent l’information ; ils peuvent donc manquer des déductions qui n’apparaissent qu’en examinant tous les motifs complets.
Utilisez les limites lorsqu’elles donnent une preuve claire. Passez aux motifs de ligne valides lorsque les extrêmes laissent trop d’ambiguïté ou que les cases connues créent des possibilités de placement non continues.
Les limites se resserrent au fil de la résolution
Chaque état confirmé peut modifier les plages :
- un X peut repousser un bloc vers l’intérieur ;
- un fragment rempli peut obliger un bloc à couvrir une zone précise ;
- un bloc terminé peut fixer l’identité d’un indice et diviser la séquence restante ;
- une attribution de segment peut limiter un indice à une zone plus petite ;
- une déduction provenant d’une ligne croisée peut supprimer des placements qui étaient auparavant possibles.
Recalculez les limites chaque fois qu’une ligne reçoit une information importante.
Les limites créent du chevauchement
Lorsque vous connaissez le placement le plus tôt et le plus tard du même bloc d’indice, comparez-les.
Les cases occupées par ce bloc dans tous les placements légaux sont forcées remplies. Il s’agit d’une version plus générale de la méthode du chevauchement vue précédemment.
Les limites peuvent aussi créer des cases vides forcées
Si une case se trouve hors de la portée légale de tous les blocs d’indice, elle est forcément vide.
Les limites de placement servent donc les deux côtés de la résolution d’une ligne :
- intersection des placements légaux d’un bloc → case remplie forcée ;
- hors de l’union de toutes les portées → case vide forcée.
Analyse des limites pas à pas
- conservez l’identité des indices dans leur ordre fixe ;
- placez tous les indices précédents aussi tôt que légalement possible pour déterminer la limite la plus tôt d’un bloc ;
- placez tous les indices suivants aussi tard que possible pour déterminer sa limite la plus tard ;
- respectez les X et fragments remplis déjà connus dans les deux calculs ;
- comparez la plage légale de chaque bloc ;
- ne marquez que les états partagés par tous les placements valides ;
- recommencez après chaque nouvelle déduction.
Cette méthode est étroitement liée à l’approche « placement le plus à gauche / le plus à droite » utilisée par de nombreux solveurs informatiques de nonogrammes.
Erreurs fréquentes
Traiter des indices de même taille comme interchangeables
Même deux indices portant le même nombre ont des identités différentes parce que leur ordre est fixe.
Calculer une limite sans réserver de place aux indices suivants
Un bloc ne peut pas occuper des cases qui rendraient impossible le reste de la séquence.
Ne regarder que les positions extrêmes de départ
Le bloc complet occupe plusieurs cases. Les limites décrivent des plages pour l’ensemble du bloc, pas seulement pour sa première case.
Remplir toutes les cases entre la portée la plus tôt et la plus tard
Cet intervalle représente une occupation possible, pas garantie. Pour une case remplie forcée, utilisez l’intersection des placements.
Que faut-il apprendre ensuite ?
Les limites de placement constituent une représentation compacte de nombreuses possibilités. Les motifs de ligne valides vont plus loin en listant ou en raisonnant sur toutes les dispositions complètes qui respectent les indices et les états déjà connus.
FAQ
Les placements extrêmes suffisent-ils à résoudre toutes les lignes ?
Non. Les méthodes fondées sur les extrêmes sont puissantes mais pas complètes pour toutes les lignes contraintes. Certaines déductions exigent l’ensemble des motifs valides.
Les limites s’appliquent-elles autant aux lignes qu’aux colonnes ?
Oui. « Plus tôt » signifie le plus à gauche pour une ligne et le plus haut pour une colonne ; « plus tard » signifie le plus à droite ou le plus bas.
Les limites d’un bloc peuvent-elles se réduire à un seul placement ?
Oui. Si les placements le plus tôt et le plus tard coïncident, la position exacte du bloc est fixée.