Forzatura

Forzatura

Maestro

È un indovinello? La controversia di Catene forzate

Catene forzate non sono un indovinare quando vengono utilizzati come tecnica dimostrativa. Si esamina temporaneamente ogni ramo da un punto di partenza scelto, si propagano logicamente tutti i rami e si conservano solo le conclusioni condivise da tutti i rami o le conclusioni forzate da una contraddizione.

La differenza principale rispetto all'indovinare è l'impegno. Un indovinare sceglie un ramo e procede come se fosse vero. Una catena forzata confronta tutti i rami rilevanti dal punto di partenza e agisce solo quando il confronto dimostra qualcosa.

Catene forzate sono meno eleganti delle tecniche basate sui pattern, ma le loro conclusioni sono provabilmente corrette quando ogni ramo è stato verificato accuratamente.

Cella Catena di forzatura

Inizia da una cella con due valori possibili Cella {A, B}. Propaga le implicazioni per ciascun ramo. Confronta i risultati.

Contraddizione: un ramo è invalido, quindi la Cella deve essere l'altro candidato.

Convergenza sul posizionamento: entrambi i rami forzano lo stesso numero nella stessa cella distante Cella.

Convergenza sull'eliminazione: entrambi i rami eliminano lo stesso candidato dalla stessa cella Cella.

Catena di forzamento regionale (Catena di forzamento per cifra)

Inizia da 2-3 posizioni di una cifra in un insieme. Esplora ogni posizione come un ramo. Stessi tre tipi di deduzione.

Cella forzato è efficace quando le celle bivalore hanno conseguenze di ampio raggio. Forzamento regionale è efficace quando la posizione di una cifra ha effetti di cascata significativi.

Rete di forzatura: Aumentare il conteggio dei rami

Cella Rete di forzatura: celle con 3-6 candidati. Rete di forzatura per regione: case con 4-6 posizioni per una cifra. Più rami, più costoso, ma può trovare deduzioni Catene forzate non può.

La logica è identica. Solo il numero di rami differisce.

Il motore di propagazione

Ogni ramo si propaga attraverso singoli nudi, singoli nascosti, Candidati bloccati, e coppie nudi, iterativamente fino al raggiungimento dell'equilibrio. Un'unica ipotesi può propagarsi attraverso dozzine di passaggi intermedi su tutta la griglia.

Quando due rami raggiungono la stessa conclusione attraverso percorsi completamente diversi, la convergenza dimostra la conclusione con certezza.

I tre tipi di deduzione

Contraddizione: un ramo produce uno stato non valido. Quell'ipotesi è falsa. Più comune.

Convergenza sul posizionamento: tutti i rami forzano lo stesso numero nella stessa Cella. Meno comune ma decisiva.

Convergenza sull'eliminazione: tutti i rami eliminano lo stesso candidato dalla stessa Cella. Tipo più sottile.

Quando usare le tecniche di forzatura

Ultimo ricorso logico. Applicato dopo che tecniche basate sui pattern e catene più pulite non hanno funzionato.

Vengono provati per primi i Catene forzate con 2-3 rami. I forcing nets con 3-6 rami sono più costosi e di solito vengono riservati al momento successivo. Entrambi sono di livello 12 (Estremo).

Per i risolutori computerizzati, il forcing limitato è un potente motore di dimostrazione ma non è automaticamente completo. La completezza si ottiene solo se la ricerca è consentita di espandersi abbastanza da coprire le ipotesi necessarie, il che si avvicina al backtracking esaustivo. Nella pratica, il forcing è meglio descritto come una ricerca logica controllata piuttosto che una garanzia che qualsiasi risolutore con profondità fissa possa risolvere ogni puzzle valido.

Una nota filosofica sull'eleganza e sull'completezza

Le tecniche basate sui pattern rivelano relazioni strutturali ed sono più eleganti. Tuttavia esistono puzzle validi che richiedono logica di livello forzato. Le tecniche forzate sono il salvagente che cattura ogni puzzle che le tecniche basate sui pattern non riescono a gestire.

Il modo più soddisfacente: provare ogni tecnica basata sui pattern prima, poi ricorrere al forzato solo quando il puzzle lo richiede veramente.

Riassunto

Catene forzate e i forcing nets sono tra le tecniche logiche più potenti, al livello 12 (Estremo). Esplorano ogni ramo da un punto di partenza scelto, propagano le conseguenze e confrontano i risultati. Le deduzioni derivano da contraddizione, convergenza sul posizionamento o convergenza sull'eliminazione. Sono l'ultima risorsa prima del backtracking forzato; se espansi senza limiti pratici, diventano una dimostrazione completa di ricerca, ma un forcing limitato allo stile umano rimane una tecnica avanzata mirata.