Lösningsmetoder för sudoku

Terminologi: en sudoku (somliga föredrar ett sudoku) består av en kvadratisk spelplan med 81 rutor (eng. cell, square), som delas in i rader, kolumner och 3x3-boxar. En rad, kolumn eller box (eng. box, block) har jag valt att sammanfattande kalla en grupp (eng. unit, sector). En del rutor är ifyllda med en siffra (siffran är satt, rutan är löst), medan andra är fria (tomma). De siffror som är ifyllda från början kallas ofta givna. I de fria rutorna kan vi skriva listor med möjliga kandidater, som vi sedan skall försöka eliminera (stryka), för att komma till en entydig lösning. En äkta sudoku har bara en lösning.

Enkel eliminering innebär, att för varje satt siffra, stryks siffran ur kandidatlistorna i samma rad, kolumn och box. Sedan används de två grundläggande metoderna nedan för att sätta fler siffror. Vid manuell lösning utförs, för varje gång man klickar på Lös-knappen, metod 1 en gång för varje siffra 1–9 och på varje grupp, och metod 2 utförs en gång för varje fri ruta. Därefter görs en ny eliminering. Vid automatisk lösning görs eliminering direkt efter varje satt siffra och proceduren upprepas så länge nya siffror sätts.  
1. Enda rutan (eng. hidden single, cross-hatching). Betrakta en siffra i taget, t.ex. 2. För varje rad, kolumn och box utan 2:a försöker vi hitta en entydig ruta, där 2:an måste vara, dvs. en ruta som inte är upptagen och där inte en 2:a finns i en annan grupp, som den rutan ingår i. Om man använder kandidatlistor, räknar vi i varje grupp antalet rutor där 2 är en kandidat. Finns det bara en sådan ruta, sätter vi 2:an där.  
2. Ensam kandidat (eng. naked single, single candidature). Betrakta en ruta i taget. Om det bara finns en siffra, som inte redan är satt i samma rad, kolumn eller box som rutan, sätter vi den siffran. Den här metoden är lite svårare än metod 1, när man löser på papper och om man inte har skrivit kandidatlistor, eftersom vi letar efter en siffra som inte finns. Men på datorskärmen är det lätt att upptäcka en ruta med bara en kandidatsiffra i listan.

Avancerad eliminering går ut på att titta på flera rutor eller siffror samtidigt, och se om det leder till att vi kan stryka (eliminera) en eller flera siffror som kandidater i vissa rutor. (Terminologin och metoderna ansluter i stora delar till Paul Vaderlinds sudokuskola i SvD.)  
3. Den första avancerade metoden används när en siffra inte kan begränsas till en ruta, men väl till en tredjedel av en rad/kolumn/box. Den kallas "rader versus boxar" i avsnitt 5 av Vaderlinds sudokuskola, och finns i fyra varianter: rad mot box, kolumn mot box, box mot rad och box mot kolumn. Jag kallar metoden snitt (eng. intersection, single sector candidates), eftersom man betraktar snittet (skärningen) av två grupper. T.ex. innebär box mot kolumn, att en siffra bara är kandidat i vänster-, mitten- eller högerdelen av en box. Då kan vi stryka siffran som kandidat i de två andra boxarna i den kolumn, där siffran är kandidat, dvs. maximalt i sex rutor.  
4. Nästa metod är matchande mängder (eng. disjoint subsets, naked/hidden pairs/triples/quads). Paul Vaderlind talar om bundna par och tripplar respektive gömda par och tripplar. Ett bundet par är när listorna i två rutor i en grupp utgör samma två siffror, så att dessa siffror kan strykas från övriga listor i aktuell rad/kolumn/box. En matchande mängd är mer allmänt när ett antal rutor i en rad/kolumn/box tillsammans innehåller lika många kandidatsiffror som antalet rutor. Gömda mängder har jag inte använt i programmet, eftersom det är i princip samma sak. Om det finns f fria rutor i en grupp och en gömd mängd med n siffror (i n av de f rutorna), finns en motsvarande bunden (f  n)-mängd. T.ex. motsvarar ett gömt par i en rad med fem fria rutor (fyra rutor är redan lösta) en matchande mängd med 5  2 = 3 siffror, dvs. en bunden trippel i samma rad.  
5. Den enklaste varianten av xy-vingar består av tre rutor med två kandidater i varje, A:xy, B:xz, C:yz. Här är A och B i samma grupp, och A och C i samma grupp. (Det är däremot inte alla tre rutorna, ty då skulle vi ha en matchande mängd i stället.) Då kan vi stryka z som kandidat i alla rutor som ligger i samma rad, kolumn eller box som både B och C (elimineringsrutor, E). A kallas pivotrutan, då allting rör sig kring den. Vilket värde vi än prövar i A, elimineras z i E.  
En naturlig variant på denna metod är xyz-vinge, där A även innehåller z (A:xyz, B:xz, C:yz). Då måste rutan E även ligga i samma grupp som A, vilket begränsar metodens användbarhet något.  
En tredje variant är när pivotrutan har fler än två kandidater förutom z, t.ex. A:xyw(z), med B:xz, C:yz, D:wz. Även här måste rutor, där z kan strykas, på motsvarande sätt ligga i samma grupp som alla vingens rutor som innehåller z (dvs. E är i samma rad, kolumn eller box som B, C, D och eventuellt pivotrutan A).  
6. Den andra klassen vingar kallar Vaderlind X-vinge och svärdfisk (eng. X-wing, swordfish, jellyfish). Jag kallar dem 2-vinge, 3-vinge, 4-vinge eller sammanfattande n-vinge, där man betraktar n rader eller kolumner. T.ex. innebär en 4-vinge på rader att en siffra, t.ex. 3, bara finns som kandidat på högst fyra ställen i fyra olika rader, och dessa ställen är i fyra olika kolumner. Då kan vi stryka 3:orna från de fem andra raderna i dessa kolumner. För närmare beskrivning, se t.ex Paul Vaderlinds sudokuskola, del 6–7. Om man löser en sudoku med större boxar (t.ex. 3x4 som i DN:s julsudoku nr 6), kan man gå vidare med n > 4 och även betrakta n-vingar på boxar, men det tillför inget för normala sudoku med 3x3-boxar (bevisa det!). N-vinge är ett specialfall av nishiokedjor.  
7. Nishio (efter den japanske sudokuexperten Tetsuya Nishio) innebär att vi sätter en kandidatsiffra i en ruta, och ser vad det får för effekter för samma siffra i övriga rutor. Vi betraktar alltså en siffra i taget: 1, 2, ..., 9. När en siffra är satt i en ruta kontrollerar programmet vilka strykningar detta leder till i samma grupper som rutan. Sedan används två av metoderna ovan. Om siffran därmed blir ensam i någon grupp, sätts den rekursivt (metod 1), dvs. en ny kontroll görs och siffran sätts i fler grupper osv. Om det blir två eller tre rutor kvar i en grupp, och dessa finns i snittet med en annan grupp, stryks siffran som kandidat i övriga rutor i denna andra grupp (metod 3), varpå en ny kontroll görs. Om vi hittar en motsägelse, så att siffran saknas som kandidat i någon grupp trots att den inte är satt i gruppen, eliminerar vi siffran i den ursprungliga rutan. När rekursionen stannar, och ingen motsägelse hittas, kan det finnas grupper kvar med mer än en kandidatruta. Detta utgör en liten begränsning av metoden på samma sätt som för kandidatprövning i ett steg. I version 4.3 skall jag därför gå vidare med nishio i flera steg, så att man avgör definitivt om den prövade rutan kan ingå i en giltig konfiguration för den aktuella siffran. (Det finns 46 656 konfigurationer för varje siffra.)  
8. I version 4.2 av lösaren används en begränsad variant av tvingande kedjor (eng. forcing chain) enligt följande: Betrakta alla rutor med två kandidatsiffror, och pröva en ruta i taget (med kandidaterna xy). Sätt en av siffrorna i rutan (t.ex. x), och genomför strykningar i övriga rutor (med två kandidater). Varje strykning medför att en ruta bara får en kandidat, så att vi kan sätta den rutan och fortsätta kedjan, eventuellt med förgreningar om det blir mer än en strykning samtidigt. När kedjan är slut, görs strykningar i hela spelplanen, för att söka efter motsägelser. Om x-kedjan inte medför motsägelser, sätter vi y på samma vis. Om inte heller y-kedjan medför motsägelser, jämför vi de två spelplanerna och söker efter gemensamma strykningar (både x och y leder till att samma siffra elimineras).  
Egentligen har vi alltså två metoder här. Antingen eliminerar vi x eller y om någon av dem leder till motsägelse (ett slags begränsad kandidatprövning), eller så eliminerar vi siffror i andra rutor om både x och y leder till samma resultat (som i matchande mängder och xy-vinge). Jag hittade olika definitioner på internet av vad tvingande kedjor är, så jag valde att implementera båda.  
I version 4.3 kommer en vidare definition, där vi även betraktar siffror med två alternativa rutor, som i kandidatprövningen nedan.  

Fullständig eliminering. Om man väljer fullständig eliminering utförs kandidatprövning, som Paul Vaderlind med flera kallar "gissning", när andra metoder inte ger en lösning. Den finns i två varianter: enkel (i ett steg) och rekursiv (i flera steg).  
9. Kandidatprövning i ett steg innebär att programmet prövar en kandidat i taget, ruta för ruta, som om användaren själv hade skrivit in den, och ser vad det leder till i övriga rutor. Vid kontrollen används metod 1–3, samt 4–8 i den mån de är valda, upprepade gånger (i version 3 av lösaren dock endast metod 1–2). Prövning i ett steg kan ge tre utfall: en lösning hittas, en motsägelse hittas eller det finns kandidater kvar i flera rutor. Om det blir motsägelse elimineras kandidaten, annars görs ingenting. Vid automatisk lösning uppdateras listorna efterhand, medan vid manuell lösning alla elimineringar görs efter att kandidaterna har prövats en gång. I version 3.0–4.1 prövas alla kandidater i alla fria rutor, men i version 4.2 prövas först en begränsad mängd: dels båda kandidaterna i rutor med två alternativ, dels alla siffror som är kandidat i två rutor i samma grupp (t.ex. om 3 är kandidat i två rutor i en rad, men inte i övriga sju rutor, prövas en 3:a på båda ställena). På så vis leder varje eliminering till att minst en ruta kan lösas. Först när tvåkandidatsprövning inte leder vidare, görs en prövning av alla kandidater (eventuellt flera gånger tills ingen eliminering sker), men detta krävs bara för ett fåtal extremt svåra sudoku.  
10. Kandidatprövning i flera steg innebär att programmet sätter en av kandidaterna i en ruta, och om det efter att alla tillgängliga metoder har använts fortfarande finns kandidater kvar på spelplanen, tittar man på en ruta som inte är löst. Där gör man en rekursiv kandidatprövning på alla rutans kandidater (prövningen upprepas gång på gång på nästa fria ruta, och rekursionen stannar först när så många rutor fyllts i att man får motsägelse eller lösning). Om någon av kandidaterna leder till lösning avbryts proceduren, och den ursprungliga kandidaten får vara kvar. Om alla kandidaterna i rutan ger motsägelse elimineras den ursprungliga kandidaten. Här finns alltså bara två utfall för varje kandidat på spelplanen: leder till minst en lösning eller leder till motsägelse. Efter att alla kandidater har prövats rekursivt, kan man konstatera att de som är kvar leder till minst en lösning.  
Jag har ännu inte sett någon äkta sudoku, som är så svår att den kräver kandidatprövning i flera steg. Jag har ändå tagit med metod 10 för fullständighetens skull, och vid enstaka tillfällen kan den behövas för att eliminera kandidater i en oäkta sudoku (med flera lösningar).

© Mats Anderbok
Senast ändrad 2006-04-15.