La propagazione dei vincoli è il processo ripetuto di applicare gli stati di casella appena confermati alle linee che li incrociano, trovare lì eventuali conseguenze e continuare finché non rimane alcuna deduzione immediata.
Una cascata è la catena visibile di deduzioni prodotta da questo processo.
Esempio di cascata cinque per cinque
Considera un Nonogramma monocromatico 5×5 con questi indizi:
Righe: 1, 3, 5, 3, 1
Colonne: 1, 3, 5, 3, 1
La riga 3 è un incastro esatto perché l'indizio 5 riempie tutta la linea. Marca tutte e cinque le caselle come piene.
Ora propaga:
- le colonne 1 e 5 hanno ciascuna indizio
1, già soddisfatto dalla casella piena centrale, quindi tutte le altre caselle di quelle colonne sono vuote; - la colonna 3 ha indizio
5, quindi si riempie completamente; - le righe 1 e 5 hanno ora la loro unica casella piena richiesta in colonna 3, quindi tutte le altre diventano vuote;
- le colonne 2 e 4, entrambe con indizio
3, sono ora obbligate a riempire le righe 2–4; - le righe 2 e 4 diventano blocchi completi da tre.
Una sola linea iniziale a incastro esatto risolve tutta la griglia grazie alla propagazione.
La propagazione non è una fonte di verità separata
Ogni singolo passo usa ancora deduzioni ordinarie valide: incastro esatto, blocchi completati, sovrapposizione, eliminazione degli spazi, filtraggio dei pattern e così via.
La propagazione descrive come queste deduzioni vengono programmate e concatenate attraverso la griglia condivisa.
Perché le cascate sembrano più veloci di una nuova scansione completa
Dopo che una casella cambia, solo la sua riga e la sua colonna ricevono direttamente nuova informazione.
Invece di ricominciare ogni volta dall'alto del puzzle, segui quindi le linee coinvolte. Se una di esse modifica un'altra casella, passa subito alla linea che la incrocia.
Così concentri l'attenzione dove il sistema di vincoli è realmente cambiato.
Propaga entrambi i tipi di certezza
Una cascata può essere alimentata da riempimenti o da X.
Per esempio:
- una casella piena può ancorare un blocco;
- una X può dividere un segmento;
- la divisione può assegnare un indizio;
- l'assegnazione può creare un incastro esatto;
- l'incastro può completare un blocco incrociato;
- il suo separatore può eliminare un altro spazio.
Non esiste una gerarchia in cui le caselle piene siano “vero progresso” e quelle vuote secondarie. Entrambi gli stati riducono l'insieme dei pattern legali.
Fermati solo a uno stato stabile
Un passaggio di propagazione è completo quando ogni linea influenzata dalle nuove caselle è stata riconsiderata e non segue più alcuno stato certo.
I solver informatici chiamano spesso questo stato punto fisso: ripetere le stesse deduzioni di linea non cambierebbe più la griglia.
A quel punto scegli una nuova linea irrisolta promettente oppure, nei puzzle davvero difficili, passa a un ragionamento più forte.
Una cascata può iniziare senza una linea a incastro esatto
L'esempio a diamante parte da una linea completa evidente. Le cascate più interessanti iniziano invece da una deduzione di consenso più debole.
Considera questo puzzle 5×5:
Righe: 2 1, 1 1, 2, 2, 1 1
Colonne: 1 2, 1 2, 2, 1, 2
All'inizio nessuna riga o colonna è un incastro esatto. Tuttavia la riga 1, con indizio 2 1, possiede una sola casella piena in ogni pattern iniziale valido: la casella 2.
Marca R1C2 piena e propaga solo stati di consenso. La nuova informazione restringe la colonna 2; quella colonna crea nuovi stati nelle righe 2 e 4; tali righe restringono altre colonne; il processo continua finché ogni casella è fissata.
La soluzione unica è:
■■××■
××■×■
×■■××
■■×××
■××■×
L'esempio mostra perché propagare non significa semplicemente “risolvere prima tutte le righe facili”. Una modesta deduzione di una sola linea può diventare decisiva perché la griglia la amplifica ripetutamente attraverso i vincoli perpendicolari.
Usa una coda di linee cambiate invece di riesaminare tutto
Un modo preciso di pensare alla propagazione manuale è una coda:
- quando cambia una casella, aggiungi riga e colonna alla coda;
- prendi una linea cambiata e risolvila contro gli stati correnti;
- se quella linea modifica caselle, aggiungi alla coda le loro linee perpendicolari;
- rimuovi la linea elaborata;
- continua finché la coda è vuota.
Una stessa linea può rientrare nella coda più volte quando riceve nuova informazione incrociata. È normale.
Molti solver informatici usano la stessa idea di scheduling perché una linea invariata non ha ricevuto nuova informazione e non necessita di una revisione immediata.
Un punto fisso dipende dalla forza del tuo solver di linea
C'è una sfumatura avanzata importante.
Se la tua analisi di linea controlla soltanto la sovrapposizione semplice, puoi raggiungere uno stato in cui la sovrapposizione semplice non produce nulla. Non significa che il puzzle abbia raggiunto un vero punto fisso logico.
Un solver di linea più forte, capace di considerare ogni pattern valido, può ancora trovare nuove caselle e riavviare la propagazione.
Quando dici “la propagazione è esaurita”, specifica quindi quale motore di deduzione stai propagando:
- punto fisso della sovrapposizione di base;
- punto fisso dei pattern di linea validi completi;
- oppure punto fisso più forte, multilinea/globale.
Questo spiega perché un puzzle possa sembrare bloccato anche quando non è necessario indovinare.
Propagazione e pattern di linea validi
Il ragionamento per pattern offre una vista formale molto pulita.
Ogni riga e colonna possiede un insieme di pattern validi. Quando una casella diventa piena o vuota:
- i pattern incompatibili spariscono dalla linea incrociata;
- i pattern sopravvissuti possono ora concordare su un'altra casella;
- la nuova casella forzata filtra un'altra linea perpendicolare;
- il processo si ripete.
È esattamente ciò che avviene in una cascata logica.
Flusso pratico di propagazione
- mantieni una piccola coda mentale delle linee modificate dalle ultime mosse;
- elabora una linea cambiata usando la tecnica di linea più forte applicabile;
- ogni volta che marchi una nuova casella, aggiungi alla coda la linea perpendicolare;
- evita di riesaminare continuamente linee invariate;
- continua finché la coda non produce nuovi stati;
- poi riprendi una scansione più ampia per trovare il prossimo punto di ingresso.
Nei puzzle grandi è molto più efficiente che ripartire dalla riga 1 dopo ogni deduzione.
Errori comuni
Fermarsi dopo la prima conseguenza
Una nuova casella può innescare molti altri passi. Segui la catena finché si stabilizza.
Propagare un'ipotesi incerta come se fosse un fatto
La propagazione ordinaria usa stati confermati. Se testi deliberatamente un'ipotesi, tieni quel ramo chiaramente separato: quello è ragionamento per contraddizione.
Ignorare le cascate di caselle vuote
Le X possono essere il passo chiave che divide una linea o chiude un blocco.
Riesaminare indiscriminatamente ogni linea
Dai priorità alle linee toccate da caselle cambiate.
Che cosa imparare dopo
Se la propagazione raggiunge uno stato stabile lasciando caselle irrisolte, alcuni puzzle esperti richiedono un'ipotesi controllata: prova uno stato candidato, propaga soltanto conseguenze logiche e rifiutalo se crea un'impossibilità. È il ragionamento per contraddizione.
FAQ
La propagazione dei vincoli è la stessa cosa che incrociare righe e colonne?
L'incrocio è un singolo trasferimento tra linee perpendicolari. La propagazione è il sistema ripetuto di trasferimenti fino all'esaurimento delle conseguenze immediate.
La propagazione comporta tentativi o ipotesi?
No. La propagazione standard utilizza stati già dimostrati.
Una sola deduzione semplice può risolvere un intero puzzle?
Sì. Alcuni puzzle contengono lunghe cascate in cui una prima linea forzata innesca abbastanza conseguenze da completare la griglia.