Forzatura

È un indovinello? La controversia su Catene forzate

N. Catene forzate esplorano ogni possibilità simultaneamente senza assumere nulla. Confrontano tutti i rami e agiscono solo quando i rami convergono. Tre proprietà distintive: esplorazione esaustiva, conclusione deterministica e correttezza dimostrabile. Catene forzate sono meno eleganti delle tecniche basate sui pattern, ma sono dimostrabilmente corrette.

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 tutti gli altri metodi falliscono. Catene forzate (2-3 rami) viene provato per primo. La Rete Forzata (3-6 rami) viene usata solo quando falliscono le Catene. Entrambi sono di livello 12 (Estremo). Per i risolutori computerizzati, la forzatura garantisce completezza: la certezza che la logica da sola possa risolvere qualsiasi 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 la rete di forzatura sono le tecniche logiche più potenti, al livello 12 (Estremo). Esplorano ogni possibilità da un punto di partenza, 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, garantendo completezza per qualsiasi puzzle Sudoku valido.