sudokUI › Sudokuteknikker › Slik henger de sammen
Slik henger teknikkene i sudoku sammen
Katalogen i sudokUI har 80 navngitte teknikker. Under dem ligger tre ideer og ett løfte som oppgaven gir. Lær ideene, så blir hvert navn en ny form av noe du allerede kjenner. Hver idé blir forklart to ganger her: én gang skikkelig, og én gang slik du ville forklart den for en 12-åring.
Den ene regelen
To fakta i én regel
Nøyaktig én gang er to løfter. Minst én gang: har et tall bare to plasser igjen i en enhet, må det stå på en av dem. Høyst én gang: to kandidater for samme tall i ruter som ser hverandre, fordi de deler rad, kolonne eller boks, kan ikke begge være sanne. En rute gir de samme to løftene: den har minst ett tall, og høyst ett.
Når nøyaktig to muligheter er igjen, to plasser for et tall i en enhet eller to kandidater i en rute, kaller løsere det første faktumet, minst én, for en sterk lenke, og det andre, høyst én, for en svak lenke. Nesten alle teknikkene på dette nettstedet, fra skjult singel til Forcing Net, kombinerer disse to faktaene til en kandidat er utelukket eller et tall er tvunget. Bare entydighetsteknikkene, lenger ned, legger til et eget faktum.
Spørsmålet kan stilles på to måter. Spør en rute hvilke tall den fortsatt kan ha, eller spør et tall hvor det fortsatt kan stå i en enhet. Den første måten finner de nakne mønstrene, den andre de skjulte, og gode løsere veksler mellom dem uten å tenke over det.
Låste mengder: ting som må passe inn
Singler: én ting, én plass
En naken singel er en rute med én kandidat igjen: én plass, ett tall. En skjult singel er et tall med én plass igjen i en enhet. De er de minste låste mengdene som finnes, sett fra de to retningene: spør ruten, eller spør tallet. En Full House, den siste tomme ruten i en enhet, er begge deler på en gang.
Delmengder: to, tre eller fire om gangen
Gjør singelen større. Hvis to ruter i en enhet bare kan ha de samme to tallene, blir de tallene brukt opp der, så ingen annen rute i enheten kan ha dem: et naket par. Hvis to tall bare kan stå i de samme to rutene i en enhet, er de rutene opptatt, så de kan ikke ha noe annet: et skjult par. Tripler og kvartetter virker på samme måte.
Naken og skjult er to beskrivelser av samme faktum. I en enhet med sju tomme ruter overlater en naken trippel de fire andre rutene til de fire andre tallene, og de fire rutene er en skjult kvartett. Det er også derfor ingen trenger en naken eller skjult kvintett: den andre siden av den er alltid fire eller mindre.
Der en boks krysser en linje
En boks og en rad har tre ruter felles. Hvis alle kandidatene for et tall i boksen ligger i denne skjæringen, vil boksen plassere tallet der, så resten av raden kan ikke ha det: låste kandidater (pekende). Bytt rollene, så får du låste kandidater (hevdende): en rad der alle kandidatene for et tall ligger inne i én boks, fjerner tallet fra resten av boksen. Kolonner virker på samme måte.
Det er den minste låste mengden mellom to enheter: én enhet som er tvunget til å plassere tallet sitt inne i en annen. Et låst par er et naket par som ligger i skjæringen, så det fjerner de to tallene fra resten av begge enhetene på en gang.
Fisk: ett tall, mange rader
Følg nå ett tall over hele rutenettet. Hvis tallet i to rader bare kan stå i de samme to kolonnene, bruker de to radene opp de to kolonnene, én hver, så ingen andre ruter i de kolonnene kan ha det tallet: en X-Wing. Tre rader i tre kolonner er en Swordfish, fire i fire en Jellyfish. I en Swordfish kan en rad ha to eller tre plasser; det som teller, er at alle plassene ligger i de samme tre kolonnene.
Krymp en X-Wing til én rad og én kolonne, så får du en skjult singel: en rad der tallet bare passer i én kolonne. En skjult singel er altså egentlig en 1-fisk, en X-Wing en 2-fisk og en Swordfish en 3-fisk, og rader og kolonner kan bytte roller. Låste kandidater, pekende og hevdende, er også 1-fisk, med en boks på den ene siden. En fisk som er større enn fire, trengs aldri, fordi en fisk i fem rader alltid kommer sammen med en mindre fisk i kolonnene, akkurat som en naken kvintett kommer sammen med en skjult delmengde på fire eller færre.
Samme triks, sett fra siden
Tenk deg oppgaven som en kube der de tre retningene er rader, kolonner og tall. Det vanlige rutenettet viser rader mot kolonner. Snu kuben, så ser du rader mot tall i stedet. For ett tall skriver du opp, for hver rad, kolonnene der tallet fortsatt kan stå. Hver rad blir da en liten rute med kolonnenumre som kandidater, og de ni radene oppfører seg som en enhet: hvert kolonnenummer hører til nøyaktig én av dem.
Nå er en X-Wing to slike ruter med de samme to kolonnenumrene: et naket par. En Swordfish er en naken trippel og en Jellyfish en naken kvartett. Snur du kuben en annen vei, viser den et naket par som et skjult par. Hver fisk i rader og kolonner som ikke har finne, er en delmengde i forkledning, og det samme gjelder hver delmengde i en rad eller kolonne; en delmengde inne i en boks, eller en fisk som bruker en boks, har ingen slik tvilling, fordi en boks ikke er en av kubens retninger.
Finner, og fisk med bokser
En fisk med finner er en fisk med noen få ekstra kandidater, kalt finnen, samlet i én boks. Enten er fisken ekte, eller så har finnen tallet, så en rute i fiskens kolonner, utenfor radene dens, som ser hver eneste finnerute, mister tallet uansett. En Sashimi-fisk er en fisk med finner der raden med finnen, uten finnen, bare ville hatt én plass igjen. Franken-fisk lar bokser ta plassen til rader eller kolonner.
Enten dette eller det: slik tenker kjeder, og de kommer senere. En fisk med finner er det første stedet på denne siden der en låst mengde og en kjede møtes.
Nesten låst: én for mye
Nesten låste mengder
En nesten låst mengde er N ruter i én enhet som til sammen har N+1 tall. Ta bort ett hvilket som helst av disse tallene, så blir rutene låst til resten. Den minste er en enkelt toverdirute: én rute, to kandidater.
Det gjør hver nesten låst mengde til en bryter. Viser ett av tallene seg å være umulig, blir mengden låst og plasserer alle de andre.
Bøyde delmengder: wingene
Legg en naken trippel i én rad, så er den låst. Bøy den rundt et hjørne, slik at de tre rutene ligger i to enheter, så virker den nesten fortsatt. Det er en XY-Wing eller en XYZ-Wing: tre ruter, tre tall, bøyd. Fire ruter og fire tall gir en WXYZ-Wing, en bøyd kvartett, og fem gir en VWXYZ-Wing, en bøyd kvintett.
Hvorfor det virker: i en bøyd delmengde har hvert tall unntatt ett kandidatene sine i ruter som alle ser hverandre, så det kan brukes høyst én gang. Bare ett tall, Z, kan komme mer enn én gang, fordi ikke alle rutene med Z ser hverandre. Uten Z ville rutene trenge like mange forskjellige tall som det er ruter, men ha ett tall færre å ta dem fra. Det er umulig, så Z står i mønsteret, og enhver rute som ser alle Z-ene i det, mister Z.
XY-Wing og XYZ-Wing skiller seg bare i om midtruten, pivoten, også har Z. Gjør den det, må rutene som Z fjernes fra, også se pivoten.
ALS-XZ: opphavet til alle de bøyde wingene
Ta to nesten låste mengder uten noen felles rute, der begge har tallene X og Z. Hvis hver X i den første mengden ser hver X i den andre, kan høyst én av mengdene ha X, så minst én mengde må klare seg uten. En mengde uten X blir låst til de andre tallene sine, blant dem Z. Minst én av de to mengdene plasserer altså Z, og Z kan fjernes fra enhver rute som ser alle Z-ene i begge mengdene.
Hver bøyd wing i katalogen er denne regelen, der den ene mengden er en enkelt toverdirute: en XY-Wing er en toverdirute pluss en mengde på to ruter, en WXYZ-Wing en toverdirute pluss en mengde på tre ruter. Derfor kaller noen guider, blant dem sudoku.coach, nå de større wingene bare ALS-XZ, og derfor finner sudokUI en wing på fem ruter med den formen under ALS-XZ.
Ideen vokser videre derfra. ALS-XY-Wing er en XY-Wing der de tre rutene har vokst til mengder, Death Blossom gir hver kandidat i én rute en egen mengde, og Sue de Coq fordeler de tettpakkede rutene der en boks krysser en linje, mellom én mengde i resten av linjen og én i resten av boksen.
Ikke alle wingene er bøyde
W-Wing har navnet felles med dem, men ikke ideen. Den består av to like toverdiruter forbundet med en sterk lenke på ett av tallene deres, og det gjør den til en kort kjede, ikke en større XYZ-Wing. W-en betyr ikke én bokstav til.
Kjeder: hvis ikke dette, så det
Sterke og svake lenker
En sterk lenke forbinder to kandidater der minst én er sann: et tall med to plasser igjen i en enhet, eller en rute med to kandidater. En svak lenke forbinder to der høyst én er sann: to kandidater for samme tall som ser hverandre, eller to kandidater i samme rute. En kjede veksler mellom dem, og den begynner og slutter med en sterk lenke. Er den ene enden usann, er den neste sann, så den påfølgende er usann, og så videre.
Når en kjede begynner og slutter på samme tall, er én av de to endene sann, så enhver rute som ser begge endene, mister det tallet. Når en kjede lukker seg til en sløyfe der lenkene veksler hele veien rundt, kan hver svak lenke i den fjerne egne kandidater.
Kjeder på ett tall: Kite, Skyscraper og Turbot Fish
En kjede som følger ett tall, er en X-Chain. Den korteste nyttige formen er to sterke lenker forbundet med en svak, fire kandidater i alt, og formene har egne navn: Skyscraper når de to sterke lenkene går parallelt, 2-String Kite når den ene går langs en rad og den andre nedover en kolonne og de møtes i en boks, og Turbot Fish for de andre formene.
En X-Wing er en slik kjede lukket til en sløyfe, og et Empty Rectangle deler kandidatene i én boks opp i en radgruppe og en kolonnegruppe, der minst én av dem har tallet. Lengre kjeder på ett tall er også X-Chains, og sløyfene er X-Cycles.
Fargelegging: to verdener
Start i én kandidat for et tall, følg de sterke lenkene utover fra den, og fargelegg vekselvis i to farger. Alt du når fram til, er én klynge, og i den er den ene fargen helt sann og den andre helt usann; du vet bare ikke hvilken ennå. Hvis en farge ville satt tallet to ganger i en enhet, er den fargen usann. Hvis en rute ser begge fargene, mister den tallet uansett hvilken farge som vinner. En egen klynge trenger egne farger.
Simple Colors ser på én hel klynge av sterke lenker på en gang, og finner derfor hver X-Chain som bare er bygd av lenkene i den klyngen. Multi Colors kobler sammen to klynger, og 3D Medusa fargelegger på tvers av alle tallene samtidig.
Kjeder av par
En toverdirute er en sterk lenke inne i en rute: er den ikke det ene tallet, er den det andre. Hopp fra en toverdirute til en annen toverdirute som ser den, gjennom et tall de har felles, og gå ut av hver rute med det andre tallet sitt: det er en XY-Chain. Versjonen med tre ruter er igjen XY-Wing, og slik kan ett mønster være en wing, en bøyd delmengde, to nesten låste mengder og en kjede på samme tid. En Remote Pair er en XY-Chain der alle rutene har de samme to tallene.
Én kjede som rommer dem alle
En AIC (Alternating Inference Chain, vekslende slutningskjede) tillater alle slags lenker på en gang: ett tall langs en enhet, to tall i en rute, en gruppe kandidater i en boks, til og med en hel nesten låst mengde. De fleste navngitte mønstrene er korte AIC-er eller sløyfer, blant dem X-Wing, Skyscraper, XY-Wing, W-Wing og ALS-XZ. En Nice Loop er det samme, skrevet som en sløyfe.
Forcing chains er siste steg før gjetting. Anta en kandidat og følg alle konsekvensene, og gjør så det samme for alternativene. Hvis alle grenene er enige om noe, er det sant, og hvis én gren ender i en motsigelse, var antakelsen den startet med, usann. De er kraftige, men det finnes ingen form å se etter, og derfor sparer sudokUI dem til de vanskeligste oppgavene.
Løftet: én løsning
Dødelige mønstre
Fire ruter i to rader, to kolonner og to bokser som bare kunne ha de samme to tallene, ville vært en felle: de to tallene kunne byttet plass, og begge versjonene ville passet. Det gir to løsninger, så en oppgave med én løsning havner aldri der. Hvis tre hjørner i rektangelet bare har 1 og 2 og det fjerde har 1, 2 og 5, må det fjerde være 5. Det er et unikt rektangel. BUG+1 bruker det samme løftet på en felle som dekker hele rutenettet, og de unngåelige rektanglene bruker det på rektangler der det blant hjørnene er tall du har plassert selv.
Disse teknikkene er bare gyldige når oppgaven virkelig har én løsning. sudokUI godtar bare oppgaver som har det, så her er de alltid trygge.
Under det hele
Sannheter og lenker
Allan Barkers mengdelogikk beskriver nesten alt dette på en gang. En sannhet er en gruppe kandidater der nøyaktig én er sann: kandidatene i en rute, eller plassene for ett tall i en enhet. En lenke er en svak lenke strukket ut over en hel gruppe: av alle kandidatene i den er høyst én sann. Hvis N sannheter som ikke deler noen kandidat, dekkes av N lenker, bruker sannhetene opp hver eneste lenke, så alle andre kandidater i de lenkene er usanne. Denne ene regelen er hver låst mengde og hver fisk uten finne.
Tillat én lenke mer enn det er sannheter, så får du kjedene, fiskene med finner og wingene, der en kandidat bare faller hvis den ligger i to av lenkene samtidig. De fleste teknikknavn er korte måter å si hvor sannhetene og lenkene ligger.
Hvorfor navnene er et rot
X-Wing kom først
Allerede i juni 2005 regnet en fast forumdeltaker X-Wing og Swordfish blant de få navnene som de fleste spillere var enige om, og ingen i den tråden kunne si hvem som hadde funnet på dem. Fisken med to rader var kjent og hadde fått navn før spillerne så at tre eller fire rader også virker, så familien ble navngitt rundt den: Swordfish, Jellyfish, og så Squirmbag, Whale og Leviathan for størrelser ingen trenger. Derfor er X-Wing en fisk og ikke en wing.
Squirmbag var upopulært, og mot slutten av 2005 foreslo spillere Starfish i stedet. X-en står mest sannsynlig for den diagonale formen som de fire hjørnene danner. Star Wars-jageren og dobbeltdekkeren Fairey Swordfish er populære historier uten kjent kilde, så regn dem som folklore.
Bokstaver som teller tall
I wingene teller bokstavene nesten antallet tall. XYZ-Wing, WXYZ-Wing og VWXYZ-Wing bruker tre, fire og fem tall, så som bøyde delmengder er de en trippel, en kvartett og en kvintett. XY-Wing bruker også tre tall og er en bøyd trippel, som XYZ-Wing, men bokstavene navngir bare de to tallene i pivoten. Y-Wing er ikke en annen eller nyere teknikk. Navnet oppsto i 2005 som en kortform for XY-Wing på forumene, og begge navnene er fortsatt i bruk. De større wingene, fra VWXYZ og oppover, har også navn, men de blir funnet som ALS-XZ, regelen de kommer fra, og noen guider bruker nå bare det navnet.
W-Wing bryter mønsteret: den er en kjede, og W-en teller ingenting.
Navn som lærer bort
Den 26. desember 2005 la en forumbruker ved navn Havard ut Skyscraper og 2-String Kite, og innrømmet samtidig at begge var Turbot Fish. En annen fast deltaker spurte hvorfor en teknikk som allerede fantes, trengte nye navn, og listet opp ti navn som allerede var i bruk for den samme familien. Havard svarte at navnene hjelper folk å huske mønsteret. Navnene som beskriver formen, vant, fordi de lærer bort bedre.
Sue de Coq sies vanligvis å være oppkalt etter forumnavnet til spilleren som først la den ut, da under navnet Two-Sector Disjoint Subsets. Bob Hanson ga selv 3D Medusa navnet: en tredimensjonal visning fikk ham til å tenke på Medusa og håret hennes.
Hvordan sudokuløsing endret seg
Teknikkene kom som separate triks med separate navn, og teorien som binder dem sammen, kom senere. Den rekkefølgen er grunnen til at katalogen minner om en dyrehage.
- Midten av 2005
- X-Wing og Swordfish er allerede standardnavn, og fisk på opptil fem rader har navn på et programmererforum.
- Høsten 2005
- Navnene er fortsatt ikke på plass: én spiller kaller hver fisk på tre eller flere rader en Swordfish, en annen sier at han fant X-Wing på egen hånd og kalte den et rektangel. Sue de Coq blir lagt ut som Two-Sector Disjoint Subsets.
- November 2005
- BUG-prinsippet: hvis hver uløst rute har to kandidater og hver kandidat forekommer to ganger i hver enhet, kan rutenettet ikke ha nøyaktig én løsning.
- Desember 2005
- Skyscraper og 2-String Kite får navnene sine. 3D Medusa, Bob Hansons fargelegging på tvers av alle tallene, er allerede et av navnene som er i bruk.
- Januar 2006
- En fast forumdeltaker oppsummerer det spillerne har lagt merke til: XY-Wing er bare en kort forcing chain, og X-Wing og Turbot Fish er X-Cycles.
- Rundt 2006 og 2007
- En forumguide om fisk tar for seg bokser (Franken- og mutantfisk) og Kraken-fisk, og Empty Rectangle er i bruk.
- Siden da
- Samlende ideer tar over: nesten låste mengder viser at de bøyde wingene er én regel, mengdelogikk viser at fisk, delmengder og kjeder er én telleidé, og poengskalaen i Sudoku Explainer blir den felles målestokken for vanskelighet.
Bli rask
Vanskelig å se er ikke vanskelig å forstå
Sudoku Explainer setter naket par til 3,0, X-Wing til 3,2 og skjult par til 3,4, selv om alle tre, i en rad eller kolonne, er ett og samme mønster sett fra ulike sider. Der får Turbot Fish 6,6, men andre guider, blant dem HoDoKu, lærer den bort tidlig. Slike poengsummer måler hvor vanskelig et mønster er å få øye på, ikke hvor dypt det er. Når du kjenner ideen, slutter et nytt mønster å være noe du må pugge, og blir noe kjent på et nytt sted.
Let derfor etter ideer, ikke navn. Tell først: singler. Se så etter låste mengder: par og tripler i en enhet, et tall som er begrenset til skjæringen mellom en boks og en linje, ett tall som havner i de samme kolonnene i flere rader. Se deretter etter nesten låste mengder: en toverdirute er den minste nesten låste mengden og starten på hver wing og hver XY-Chain. Følg til slutt lenkene: et tall med to plasser i en enhet er en sterk lenke som venter på å bli en del av en kjede.
Fanen Slik løser du viser hvordan de beste løserne ordner dette i praksis, og øvingsmodusen gir deg de fleste teknikkene, én om gangen, som det aller neste trekket.