Tvingning

Är det gissning? Det kontroversiella kring Tvingande kedjor

No. Tvingande kedjor utforskar alla möjligheter samtidigt utan att binda sig till någon antagande. De jämför alla grenar och agerar endast när grenarna sammanförs. Tre utmärkande egenskaper: utfattande utforskning, bestämd slutsats och bevisbar korrekthet. Tvingande kedjor är mindre eleganta än mönsterbaserade tekniker men är bevisligen korrekta.

Cell Tvingande kedja

Börja med ett tvåvärdes Cell {A, B}. Följ med konsekvenser för varje gren. Jämför resultaten. Motstridighet: en gren är ogiltig, så Cell måste vara det andra kandidatvärdet. Konvergens vid placering: båda grenarna tvingar samma siffra in i samma avlägsna Cell. Konvergens vid eliminering: båda grenarna eliminera samma kandidat från samma Cell.

Regionens tvingande kedja (siffertvingande kedja)

Börja med en siffra i 2-3 positioner i en ruta. Utforska varje position som en gren. Samma tre typer av slutsatser. Cell tvingande är effektivt när tvåvärdesceller har långsträckta konsekvenser. Regiontvingande är effektivt när en siffras plats har starka kaskadverkningar.

Tvingande nät: Förstorar grenantalet

Cell Tvingande nät: rutor med 3-6 kandidater. Regionstyrande nät: hus med 4-6 platser för en siffra. Fler grenar, mer kostsam, men kan hitta slutsatser som Tvingande kedjor inte kan. Logiken är densamma. Endast antalet grenar skiljer sig.

Propagationsmotorn

Varje gren sprider sig genom nakna enskilda, dolda enskilda, Låsta kandidater, och nakna par, iterativt tills det är stabilt. En enskild antagande kan sprida sig genom tiotals mellansteg över hela brädet. När två grenar når samma slutsats genom helt olika vägar, bevisar konvergensen slutsatsen med säkerhet.

De tre typerna av slutsatser

Motstrid: En gren producerar ett ogiltigt tillstånd. Antagandet är felaktigt. Mest vanligt. Konvergens vid placering: Alla grenar tvingar samma siffra in i samma Cell. Mindre vanligt men avgörande. Konvergens vid eliminering: Alla grenar eliminierar samma kandidat från samma Cell. Subtilaste typen.

När ska man använda tvingande tekniker

Sista logiska utvänt. Tillämpas efter alla andra tekniker misslyckas. Tvingande kedjor (2-3 grenar) testas först. Tvingande nät (3-6 grenar) endast om kedjor misslyckas. Båda är Nivå 12 (Extrem). För datorlösare ger tvingande fullständighet: garantin att logik ensam kan lösa alla giltiga pussel.

En filosofisk anteckning om elegans och fullständighet

Mönsterbaserade tekniker avslöjar strukturella relationer och är mer eleganta. Men det finns giltiga pussel som kräver tvingande logik på nivå. Tvingande tekniker är skyddsnätet som fångar varje pussel som mönsterbaserade tekniker inte kan hantera. Den mest tillfredsställande metoden: prova alla mönsterbaserade tekniker först, och återgå till tvingande endast när pusslet verkligen kräver det.

Sammanfattning

Tvingande kedjor och tvingande nät är de mest kraftfulla logiska teknikerna, på nivå 12 (extrem). De undersöker varje möjlighet från ett utgångsläge, sprider konsekvenser och jämför resultat. Slutsatser kommer genom motsägelse, konvergens vid placering eller konvergens vid eliminering. De är det sista alternativet innan brutt-force bakåtspårning, och ger fullständighet för alla giltiga Sudoku-pussel.