Durante il gioco i Nonogrammi richiedono pochissima aritmetica, ma sotto il puzzle c'è un compatto problema combinatorio di vincoli.
Ogni indizio descrive blocchi ordinati di caselle piene su una linea. I vincoli delle righe e quelli delle colonne si sovrappongono sulle stesse caselle, e risolvere significa trovare la griglia binaria che li soddisfa tutti contemporaneamente.
Gli indizi sono descrizioni run-length
Una sequenza di indizi registra le lunghezze dei blocchi consecutivi di caselle piene.
Per esempio:
■■■ ×× ■■ × ■
3 2 1I numeri non dicono dove iniziano i blocchi. Dicono:
- le lunghezze dei blocchi;
- l'ordine dei blocchi;
- che due blocchi monocromatici consecutivi devono essere separati da almeno una casella vuota.
Per questo una sequenza di indizi è più di una semplice somma.
Estensione minima
Supponiamo che una linea abbia m blocchi indicati con lunghezze:
c1, c2, ..., cmLe caselle piene richiedono:
c1 + c2 + ... + cmcaselle, mentre i m - 1 confini tra blocchi consecutivi richiedono almeno una casella vuota ciascuno.
Lo spazio minimo capace di contenere tutti gli indizi è quindi:
estensione minima = somma(indizi) + (numero di indizi - 1)Per una linea di 10 caselle con indizi 3 2:
estensione minima = 3 + 2 + 1 = 6La linea possiede quindi quattro caselle di libertà extra nella collocazione.
Quello spazio extra è il margine.
Quante collocazioni può avere una sequenza di indizi su una linea vuota?
Per una linea monocromatica altrimenti priva di vincoli, il margine può essere distribuito:
- prima del primo blocco;
- dopo l'ultimo blocco;
- come caselle vuote aggiuntive in qualsiasi spazio obbligatorio tra i blocchi.
Se ci sono m blocchi e un margine s, il numero di collocazioni complete è:
C(s + m, m)dove C è il coefficiente binomiale.
Esempio: lunghezza 10 con indizi 3 2
Abbiamo già trovato:
estensione minima = 6
margine = 10 - 6 = 4
m = 2Il numero di pattern completi legali su una linea completamente indeterminata è quindi:
C(4 + 2, 2) = C(6, 2) = 15Questo conteggio descrive la linea iniziale senza altri vincoli. Quando alcune caselle sono note come piene o vuote, molti di quei 15 pattern possono essere eliminati.
Perché la sovrapposizione funziona matematicamente
Una casella è forzatamente piena quando ogni pattern valido sotto i vincoli correnti riempie quella casella.
Allo stesso modo, una casella è forzatamente vuota quando ogni pattern valido la lascia vuota.
La sovrapposizione è una scorciatoia umana veloce per trovare alcune di queste caselle comuni senza elencare esplicitamente tutti i pattern possibili.
La tecnica più avanzata dei pattern di linea validi rende esplicita la stessa idea: generare o ragionare sull'intero insieme dei pattern legali e poi mantenere gli stati su cui tutti concordano.
Righe e colonne formano vincoli intersecanti
Un indizio di riga, da solo, restringe una stringa binaria orizzontale. Un indizio di colonna restringe una stringa binaria verticale.
Ogni casella appartiene esattamente a una riga e a una colonna, quindi i due sistemi sono accoppiati.
Quando una riga dimostra che una casella è piena, quello diventa un valore fisso nella colonna che la incrocia. Alcuni pattern della colonna scompaiono. La colonna ridotta può poi forzare un'altra casella, che modifica un'altra riga.
Questa riduzione ripetuta è la propagazione dei vincoli.
Un Nonogramma non si risolve semplicemente sommando gli indizi
Le somme sono utili per estensione minima e conteggi di occupazione, ma il puzzle dipende da posizioni e ordine.
Due sequenze di indizi possono avere lo stesso totale di caselle piene e comportarsi in modo molto diverso:
6
3 3
2 2 2Tutte descrivono sei caselle piene, ma gli spazi obbligatori e l'identità dei blocchi creano spazi di collocazione differenti.
Per questo «gli indizi sommano alla lunghezza della riga» è sufficiente solo nei casi di incastro esatto in cui anche i separatori obbligatori vengono conteggiati correttamente.
La combinatoria cresce rapidamente
Anche singole linee possono avere molte configurazioni legali quando contengono diversi blocchi piccoli e molto margine.
Su un'intera griglia, le possibilità delle righe non possono essere scelte indipendentemente perché ogni colonna deve soddisfare a sua volta i propri indizi.
Il puzzle è quindi un problema di vincoli su molte variabili binarie interagenti, non una semplice raccolta di esercizi indipendenti di collocazione su linee.
È proprio questa interazione che può far emergere istanze computazionalmente difficili.
Perché questa matematica aiuta chi risolve a mano
Non hai bisogno di calcolare coefficienti binomiali mentre giochi.
Ma la matematica sottostante spiega diverse regole pratiche:
- poco margine significa meno collocazioni;
- incastro esatto significa una sola collocazione;
- sovrapposizione trova caselle comuni alle collocazioni estreme o valide;
- segni X eliminano collocazioni candidate;
- caselle piene restringono quali identità di blocco possono raggiungerle;
- incrocio di righe e colonne trasferisce restrizioni tra due sistemi di linee;
- contraddizione dimostra che un ramo contiene zero completamenti validi.
Le tecniche del resto del corpus sono modi adatti agli esseri umani per sfruttare questi vincoli senza enumerare manualmente l'intero spazio di ricerca.
Un Nonogramma è un puzzle matematico?
È ragionevole chiamarlo puzzle di logica matematica, ma non serve matematica avanzata per risolvere i normali Nonogrammi pubblicati.
La maggior parte del gioco consiste in:
- contare caselle;
- confrontare lunghezze;
- preservare l'ordine;
- eliminare collocazioni impossibili;
- propagare conseguenze.
La combinatoria più profonda diventa utile quando si analizzano algoritmi, generatori, difficoltà e complessità nel caso peggiore.
Cosa imparare dopo
Per una versione pratica dell'idea di insieme delle collocazioni, leggi Pattern di Linea Validi. Per la risoluzione algoritmica, continua con Come Funzionano i Solver Informatici di Nonogrammi. Per la teoria della complessità, leggi Perché i Nonogrammi Sono Computazionalmente Difficili.
FAQ
Qual è la formula dell'estensione minima per gli indizi dei Nonogrammi?
Per gli indizi monocromatici standard, somma tutti i valori e poi aggiungi una casella vuota obbligatoria per ogni confine tra blocchi consecutivi.
La formula del numero di collocazioni vale sempre?
La formula semplice C(s + m, m) vale per una linea altrimenti priva di vincoli con la separazione monocromatica standard. Caselle piene/vuote già note e assegnazioni dei segmenti riducono ulteriormente l'insieme.
Devo conoscere la combinatoria per risolvere i Nonogrammi?
No. Le tecniche standard raccolgono le conseguenze utili in deduzioni visive molto più semplici da applicare a mano.