Segmentation des lignes dans les nonogrammes

La segmentation des lignes consiste à traiter les cases vides confirmées comme des frontières rigides qui divisent une ligne ou une colonne en zones ouvertes plus petites.

Au lieu de résoudre encore et encore une longue ligne, vous résolvez une suite de segments plus courts et davantage contraints.

Schéma conceptuel

Pourquoi la segmentation est puissante

Un bloc d’indice ne peut jamais traverser une case vide confirmée. Chaque X supprime donc des placements et peut séparer des blocs qui, auparavant, se disputaient le même espace.

Lorsqu’une ligne se segmente, vous pouvez souvent déterminer :

quels indices peuvent tenir dans chaque zone ;
quels indices ne peuvent pas partager une même zone ;
si un segment constitue un ajustement exact ;
si un segment est trop court et doit rester vide ;
si un fragment rempli connu appartient à un indice précis.

La segmentation n’ajoute aucune nouvelle règle. Elle rend simplement les contraintes déjà présentes dans les indices plus visibles.

Exemple : un séparateur oblige les groupes d’indices à se répartir

Considérez une ligne de 12 cases avec les indices 4 3 et une case vide confirmée en position 6 :

????? × ??????

La ligne comporte maintenant un segment de cinq cases à gauche et un segment de six cases à droite.

Si les indices 4 3 occupaient le même segment, ils exigeraient une extension minimale de huit cases : quatre cases remplies, un séparateur obligatoire, puis trois cases remplies.

Aucun des deux segments n’atteint huit cases : les deux blocs ne peuvent donc pas se trouver du même côté du X.

Comme l’ordre des indices est fixe, le 4 doit occuper le segment de gauche et le 3 celui de droite.

Exemple de ligne

Indices43

État initial

Le séparateur a transformé un problème de 12 cases en deux problèmes de placement plus petits.

Techniques · IntermédiaireAttribuer les indices aux segmentsApprenez à attribuer les blocs d’indices aux segments ouverts grâce à l’ordre, la capacité, les blocs terminés et les cases remplies connues.

Un segment n’est pas automatiquement indépendant

Ne supposez pas que chaque zone ouverte peut être résolue sans tenir compte du reste de la ligne.

Les segments ne deviennent réellement indépendants qu’une fois établi quels blocs d’indice leur appartiennent. Tant que cette attribution n’est pas prouvée, certains indices peuvent encore avoir plusieurs segments possibles.

Par exemple, un indice court peut tenir des deux côtés d’un X tandis qu’un indice plus long ne tient que d’un seul côté. Il faut conserver à la fois l’ordre des indices et la capacité des segments jusqu’à ce que l’attribution soit déterminée.

Segmentation après des blocs terminés

Un bloc d’indice terminé, accompagné de son séparateur, agit comme une frontière structurelle.

Une fois ce bloc comptabilisé, les indices non résolus qui le précèdent doivent rester d’un côté et ceux qui le suivent de l’autre. C’est souvent plus fort qu’un X isolé, car cela indique aussi où vous vous situez dans la séquence des indices.

Techniques · DébutantBlocs terminés et séparateursReconnaissez un bloc terminé, placez les séparateurs vides obligatoires, évitez les fusions illégales et simplifiez la ligne avec les indices résolus.

Capacité d’un segment

Pour chaque segment ouvert, comparez sa longueur à l’extension minimale des groupes d’indices susceptibles de l’occuper.

Supposons un segment de longueur 7 :

l’indice 5 tient ;
les indices 2 3 demandent 2 + 1 + 3 = 6, ils peuvent donc tenir ensemble ;
les indices 3 4 demandent 8, ils ne peuvent donc pas tous deux tenir.

Ces tests de capacité constituent la base de l’attribution des indices aux segments.

Techniques · IntermédiaireExtension minimale et margeCalculez l’extension minimale et la marge, comparez la contrainte des indices, repérez ajustements exacts, chevauchements forts et segments serrés.

Ajustement exact et chevauchement à l’échelle d’un segment

Une fois qu’un indice ou un groupe d’indices est attribué à un segment, les techniques apprises sur les lignes entières peuvent être réutilisées à l’intérieur de ce segment.

Si les indices attribués consomment exactement le segment, utilisez l’ajustement exact.

S’ils disposent d’une petite marge, utilisez le chevauchement.

Si une case remplie confirmée ancre l’un des blocs, recalculez sa portée à l’intérieur du segment plutôt que sur toute la ligne d’origine.

Techniques · DébutantLignes à ajustement exactApprenez l’ajustement exact, calculez l’extension minimale, placez blocs et séparateurs et repérez aussi les ajustements exacts dans des segments.Techniques · DébutantMéthode du chevauchement dans les nonogrammesApprenez le chevauchement avec les placements extrêmes d’un bloc, comprenez pourquoi les cases communes sont forcées et utilisez-le dans des segments contraints.Techniques · IntermédiairePortée des blocs et cases inaccessiblesTrouvez l’union des placements légaux d’un bloc, repérez les cases qu’aucun indice ne peut atteindre et transformez ces positions impossibles en cases vides.

Méthode de segmentation pas à pas

marquez comme X uniquement les cases vides confirmées ;
repérez chaque segment ouvert contigu ;
listez dans l’ordre les blocs d’indice non résolus ;
calculez quels groupes d’indices peuvent tenir dans chaque segment ;
éliminez les attributions impossibles ;
dès qu’une attribution devient forcée, résolvez ce segment avec les techniques de ligne ordinaires ;
propagez les nouvelles cases remplies et vides vers les lignes croisées.

Erreurs fréquentes

Traiter des cases indéterminées comme des frontières

Seule une case vide confirmée bloque un bloc. Les cases indéterminées font toujours partie de l’espace disponible.

Attribuer les indices trop tôt

Un segment peut être assez grand pour un indice sans être son seul emplacement légal.

Oublier le séparateur obligatoire lorsqu’on teste plusieurs indices

Deux blocs monochromes nécessitent au moins une case vide entre eux, y compris lorsqu’ils partagent le même segment ouvert.

Perdre l’ordre des indices d’un segment à l’autre

L’indice non résolu le plus à gauche ne peut pas soudain apparaître après un indice ultérieur. Les attributions doivent préserver la séquence d’origine.

Que faut-il apprendre ensuite ?

L’étape suivante consiste à attribuer explicitement les indices aux segments. Cette technique transforme la capacité des segments, l’ordre des indices et les fragments remplis connus en preuves indiquant quel bloc appartient à quelle zone.

Techniques · DébutantÉlimination des espaces impossiblesComparez la longueur des segments ouverts aux indices restants pour éliminer les zones où aucun bloc ne peut encore être placé légalement.Techniques · IntermédiaireAttribuer les indices aux segmentsApprenez à attribuer les blocs d’indices aux segments ouverts grâce à l’ordre, la capacité, les blocs terminés et les cases remplies connues.Stratégies · AvancéStratégie pour les grands nonogrammesRésolvez de grands nonogrammes avec balayage par régions, segmentation, suivi des indices, propagation et récupération méthodique sur les grilles complexes.

FAQ

Chaque X divise-t-il une ligne en segments ?

Oui, d’un point de vue structurel. Mais les indices de part et d’autre ne sont pas nécessairement encore attribués.

Plusieurs indices peuvent-ils appartenir au même segment ?

Oui, tant que leurs blocs et leurs séparateurs obligatoires tiennent dans la zone et que l’attribution respecte l’ordre des indices.

Un segment peut-il ne contenir aucun indice ?

Oui. Si aucun indice non résolu compatible ne peut y tenir, l’élimination des espaces marque tout le segment vide.