Il ragionamento per contraddizione testa un'ipotesi controllata e segue soltanto deduzioni valide finché il ramo rimane possibile oppure diventa impossibile. Se un'ipotesi viola inevitabilmente i vincoli del Nonogramma, lo stato opposto è forzato.
È logica avanzata. Va usata dopo aver esaurito la normale risoluzione di linea e la propagazione dei vincoli.
La regola fondamentale
Supponiamo che una casella irrisolta possa essere soltanto piena o vuota.
Assumi temporaneamente che sia vuota.
Se questa ipotesi porta infine una riga o colonna ad avere zero pattern di linea validi, l'ipotesi non può appartenere a nessuna soluzione valida. Quindi la casella deve essere piena.
Il ragionamento funziona anche al contrario.
La prova è la contraddizione, non il fatto che un ramo “sembra peggiore”.
Esempio: un'ipotesi sbagliata distrugge un indizio
Considera questo stato parzialmente risolto di un puzzle 5×5.
Righe:
1 21241 1
Colonne:
1 11 11 21 21 1
Dopo la propagazione ordinaria, la griglia è:
???■?
???.?
.. ?■?
?■■■?
?.?.?
Per il ramo dell'esempio, assumiamo R1C1 vuota.
Questa ipotesi forza la riga 1 nel suo unico pattern rimasto, che a sua volta modifica diverse colonne. Continuando con normale logica di linea, la riga 2 finisce per contenere due caselle piene separate nonostante il suo unico indizio sia 1.
La riga 2 ha quindi zero pattern validi. Il ramo è impossibile.
L'ipotesi R1C1 = vuota è dunque falsa, e R1C1 deve essere piena.
Il punto importante è che ogni passo dopo l'ipotesi è una deduzione ordinaria forzata. Solo la scelta iniziale del ramo è provvisoria.
La contraddizione è diversa dall'indovinare alla cieca
Indovinare alla cieca significa scegliere uno stato perché sembra plausibile e proseguire come se fosse vero.
Il ragionamento per contraddizione mantiene invece l'ipotesi esplicitamente provvisoria:
- scegli uno stato candidato preciso;
- propaga soltanto conseguenze logicamente forzate;
- cerca un'impossibilità definita;
- se compare una contraddizione, annulla il ramo e conferma lo stato opposto;
- se non compare, non dichiarare l'ipotesi dimostrata soltanto perché ha superato un test breve.
Un ramo che rimane possibile non è automaticamente corretto.
Che cosa conta come contraddizione?
Esempi:
- una linea non possiede alcuna disposizione che soddisfi indizi e stati noti;
- una sequenza continua piena diventa più lunga di ogni indizio compatibile;
- i blocchi richiesti non hanno più spazio sufficiente per entrare;
- una casella piena confermata non può essere coperta da alcun blocco;
- l'ordine degli indizi diventa impossibile;
- una casella dovrebbe essere contemporaneamente piena e vuota.
Una discrepanza estetica con l'immagine emergente non è una contraddizione.
Usa l'ipotesi utile più piccola possibile
Un buon test parte di solito da una sola casella o da una collocazione di blocco molto vincolata, non da una lunga catena speculativa di scelte scollegate.
Preferisci candidati in cui entrambi i rami abbiano conseguenze immediate forti. Le contraddizioni saranno più facili da rilevare e il ragionamento più verificabile.
Propaga abbastanza in profondità, ma mantieni il ramo controllato
Dopo l'ipotesi usa gli stessi strumenti della risoluzione normale:
- pattern di linea validi;
- limiti dei blocchi;
- assegnazione ai segmenti;
- blocchi completati;
- incrocio di righe e colonne;
- propagazione dei vincoli.
Non introdurre una seconda ipotesi non supportata all'interno del primo ramo. Se il ramo si blocca senza contraddizione, torna allo stato originale a meno che tu non stia deliberatamente passando alla ricerca/backtracking.
Scegli rami informativi, non semplicemente incerti
Ogni casella indeterminata ha due stati, ma la maggior parte è una pessima candidata per un test di contraddizione.
Un ramo utile tende a trovarsi dove entrambi gli stati modificherebbero immediatamente una linea molto vincolata. Buoni candidati includono:
- una casella condivisa da soli due pattern di linea rimasti;
- l'estremità di un blocco con due sole collocazioni;
- un'assegnazione indizio-segmento con esattamente due alternative sopravvissute;
- una casella il cui stato pieno/vuoto completerebbe o romperebbe un blocco quasi fissato.
Evita di ramificare su una casella poco vincolata in una regione aperta dove entrambi gli stati lasciano decine di possibilità. Creeresti un albero speculativo lungo senza dare molta leva ai vincoli.
Separa il lookahead breve dalla ricerca completa
Una dimostrazione per contraddizione può essere molto corta:
assumi X → una linea incrociata perde l'ultimo pattern valido → rifiuta X.
Oppure può richiedere una cascata più lunga attraverso diverse righe e colonne prima che emerga l'impossibilità.
Lo status logico è lo stesso purché:
- esista una sola ipotesi provvisoria chiaramente identificata;
- ogni segno successivo sia forzato sotto quell'ipotesi;
- la contraddizione finale sia esplicita;
- nessuna seconda scelta non supportata sia nascosta nel ramo.
Quando inizi ad aggiungere scelte arbitrarie perché il primo ramo si è bloccato, ti stai spostando da una dimostrazione pulita alla ricerca/backtracking generale.
Mantieni un registro del ramo
Nei puzzle manuali difficili è utile separare mentalmente o fisicamente tre tipi di informazione:
- fatti radice — stati permanenti dimostrati prima dell'ipotesi;
- conseguenze del ramo — stati forzati soltanto mentre l'ipotesi è attiva;
- conclusione del ramo — una contraddizione esplicita oppure nessuna conclusione per ora.
Quando il ramo fallisce, elimina tutte le sue conseguenze insieme. L'unico nuovo fatto permanente è la negazione dell'ipotesi fallita.
Quando il ramo si limita a bloccarsi, elimina le conseguenze e ritorna alla radice invariata.
Questa disciplina impedisce agli stati ipotetici di contaminare il puzzle reale.
Le conseguenze condivise appartengono all'analisi di casi multilinea
Se entrambi gli stati esaustivi di una proposizione restano possibili ma forzano la stessa casella a valle, quello stato condiviso è comunque valido.
È una tecnica avanzata utile, ma la sua prova non è “un ramo è andato in contraddizione”. VeyraPlay la tratta come ragionamento multilinea/a due vie con conseguenza condivisa e ne presenta il metodo più ampio in G-040.
Metodo passo passo per la contraddizione
- esaurisci prima la propagazione normale;
- scegli una casella irrisolta o un caso di blocco molto vincolato;
- copia o isola mentalmente lo stato corrente;
- assumi uno stato candidato;
- propaga soltanto conseguenze forzate;
- fermati appena una linea ha zero pattern validi o compare un'altra contraddizione dura;
- rifiuta l'ipotesi fallita e marca lo stato opposto nel puzzle reale;
- riprendi la propagazione normale dal nuovo fatto dimostrato.
Errori comuni
Trattare “mi sono bloccato” come una contraddizione
Un ramo che smette di produrre deduzioni può essere ancora valido.
Fare più ipotesi dentro lo stesso ramo
A quel punto non sai più quale ipotesi ha causato la contraddizione.
Usare l'immagine per rifiutare un ramo
Solo i vincoli degli indizi possono dimostrare l'impossibilità.
Usare la contraddizione troppo presto
Molti apparenti vicoli ciechi spariscono dopo una scansione accurata di pattern di linea, X, assegnazioni ai segmenti e linee incrociate appena modificate.
Conservare come fatto un'ipotesi che è semplicemente sopravvissuta
Non trovare una contraddizione non è una prova, a meno di aver stabilito in modo esaustivo che l'alternativa è impossibile.
Dove si colloca nella gerarchia di risoluzione
Un ordine utile è:
- logica diretta di linea;
- logica di segmenti e intervalli dei blocchi;
- deduzioni dai pattern di linea validi;
- incrocio e propagazione;
- ragionamento multilinea e conseguenze condivise;
- contraddizione/lookahead controllato;
- ricerca o backtracking completo solo quando il puzzle o il solver lo richiede.
I puzzle progettati per persone cercano spesso di ottenere la maggior parte del progresso prima dell'ultima fase di ricerca.
Che cosa imparare dopo
Il ragionamento per contraddizione collega la risoluzione umana alle idee usate dai solver informatici: probing di stati candidati, rilevamento di rami impossibili e, infine, ricerca quando la sola propagazione non basta.
FAQ
Il ragionamento per contraddizione è indovinare?
Usa un'ipotesi temporanea, ma la conclusione è deduttiva solo quando un ramo viene dimostrato impossibile. È molto più disciplinato che impegnarsi in un tentativo e sperare che funzioni.
Che cosa succede se entrambe le ipotesi restano possibili?
Quel caso non dimostra ancora la casella scelta. Torna allo stato originale oppure cerca una conseguenza condivisa da entrambi i rami.
I principianti dovrebbero usare il ragionamento per contraddizione?
Di solito non come prima scelta. Una buona logica di linea e la propagazione risolvono una grande parte dei puzzle normali e sono più facili da verificare.