Forcing

Forcing

Maestro

Tecniche associate

È un indovinare? La controversia su Catene forzate

Le Catene forzate non sono un indovinare quando vengono usate come tecnica di prova. Esamini temporaneamente ogni ramo da un punto di partenza scelto, propaghi ogni ramo logicamente e mantieni solo le conclusioni che ogni ramo sostiene o le conclusioni forzate da una contraddizione.

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

Le Catene forzate sono meno eleganti delle tecniche basate su schemi, ma le loro conclusioni sono dimostrabilmente corrette quando ogni ramo è stato verificato con precisione.

Catena di forzatura Cella

Parti da una cella a due valori {A, B}. Propaga le implicazioni per ogni ramo. Confronta i risultati.

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

Convergenza su un posizionamento: entrambi i rami forzano la stessa cifra nella stessa cella distante.

Convergenza su un'eliminazione: entrambi i rami eliminano lo stesso candidato dalla stessa cella.

Catena di forzatura per regione (catena di forzatura per cifra)

Parti dalle 2-3 posizioni di una cifra in una casa. Esplora ogni posizione come un ramo. Gli stessi tre tipi di deduzione.

La forzatura Cella è efficace quando le celle a due valori hanno implicazioni di vasta portata. La forzatura per regione è efficace quando la posizione di una cifra ha forti effetti a cascata.

Rete di forzatura: estendere il numero di rami

Rete di forzatura Cella: 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 che Catene forzate non può.

La logica è identica. Cambia solo il numero di rami.

Il motore di propagazione

Ogni ramo si propaga attraverso singoli nudi, singoli nascosti, candidati bloccati e coppie nude, in modo iterativo fino alla stabilità. Una singola assunzione può propagarsi attraverso decine 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. Questa ipotesi è falsa. Il caso più comune.

Convergenza sul posizionamento: tutti i rami forzano la stessa cifra nella stessa cella. Meno comune ma decisivo.

Convergenza sull'eliminazione: tutti i rami eliminano lo stesso candidato dalla stessa cella. Il tipo più sottile.

Quando usare le tecniche di forcing

Ultima risorsa logica. Si applica dopo il fallimento delle tecniche basate su schemi e delle catene più semplici.

I Catene forzate con 2-3 rami vengono provati per primi. Le reti di forcing con 3-6 rami sono più costose e di solito vengono riservate a dopo. Entrambi sono di livello 12 (Estremo).

Per i risolutori informatici, il forcing limitato è un potente motore di prova ma non automaticamente completo. La completezza si ottiene solo se la ricerca può espandersi abbastanza da coprire le ipotesi necessarie, il che si avvicina al backtracking esaustivo. In pratica, il forcing si descrive meglio come una ricerca logica controllata che come la garanzia che un risolutore a profondità fissa risolva ogni schema valido.

Una nota filosofica su eleganza e completezza

Le tecniche basate su schemi rivelano relazioni strutturali e sono più eleganti. Ma esistono schemi validi che richiedono una logica di livello forcing. Le tecniche di forcing sono la rete di sicurezza che cattura ogni schema che le tecniche basate su schemi non riescono a gestire.

L'approccio più soddisfacente: provare prima ogni tecnica basata su schemi, poi ricorrere al forcing solo quando lo schema lo richiede davvero.

Riepilogo

I Catene forzate e le reti di forcing 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 arrivano per contraddizione, convergenza sul posizionamento o convergenza sull'eliminazione. Sono l'ultima risorsa prima del backtracking a forza bruta; se espansi senza limiti pratici, diventano una prova di ricerca completa, ma il forcing limitato in stile umano resta una tecnica avanzata mirata.

Tecniche associate