Sudoku

Ett lättare sudoku

Sudoku (数独, sūdoku) är ett logikspel som går ut på att man ska placera ut siffror i ett rutmönster. Om ett korsord utgör ett bokstavspussel motsvarar ett sudoku ett sifferpussel.

Det klassiska, ursprungliga rutmönstret i ett sudoku består av 3 × 3 rutor (”lådor”) som i sin tur består av 3 × 3 rutor. Det gäller att placera in siffrorna 1 till 9 på ett sådant sätt att varje vågrät rad, lodrät rad och låda på 3 × 3 rutor innehåller varje siffra exakt en gång. En lösning till ett sudoku utgör en latinsk kvadrat.

Ett sudoku har minst 17 siffror utplacerade från början. För att det ska anses som äkta får det bara ha en lösning.

Historia

Sifferpussel dök upp i franska tidningar på 1890-talet. Le Siècle var först den 19 november 1892. Dessa krävde dock inte logik för sin lösning, utan var främst baserade på räkning. En mer sudokulik variant kom i juli 1886 i konkurrenten La France Populariteten falnade dock vid första världskriget.

Sudoku i modern version uppfanns i USA i slutet av 1970-talet, men vann då ingen popularitet. 1984 introducerades det av Nikoli i Japan, där det också fick sitt namn, ursprungligen (数字は独身に限る) suuji wa dokushin ni kagiru ("siffrorna måste förbli singlar"), vilket kortades till sū doku ("ensam siffra"). Det fick en ny blomstringsperiod i Storbritannien 2005, till stor del därför att nyzeeländaren Wayne Gould konstruerade ett datorprogram som snabbt alstrar nya pussel.

Den 2 juni 2005 började Sydsvenska Dagbladet och Svenska Dagbladet som första svenska tidningar publicera ett sudoku om dagen. I dag har de flesta svenska tidningar ett dagligt sudoku och det finns en rad specialtidskrifter som främst ägnar sig åt sudoku. Dessutom finns ett relativt stort antal sudokuböcker.

Lösning

Ett sudoku löses normalt en ruta i taget: När man funnit ett logiskt argument som bevisar att det i en viss ruta måste stå en viss siffra så skriver man in den siffran där. Detta kan i sin tur göra det tydligt vilken siffra som måste stå i en annan ruta, varför man då lämpligen fortsätter med denna, och så vidare. Ordningen i vilken rutorna fylls i är inte känd på förhand, och behöver inte vara entydig. Komplexiteten i de logiska argument man behöver ta till är i princip det som avgör ett sudokus svårighetsgrad. Det är inte nödvändigt att komma ihåg på vilka logiska argument som redan gjorda ifyllanden stödjer sig, och det kan rentav vara svårt att i efterhand rekonstruera dem om man inte har exakt koll på vilka andra rutor som då redan var ifyllda.

Taktik

Det finns i grunden två frågor att använda för att lösa sudokut:

• I vilken ruta ska denna siffra sitta?
• Vilken siffra ska sitta i denna ruta?

Med uteslutningsmetoden kan dessa frågor itereras runt på alla 9 lådor, rader och kolumner, och till sist har man löst pusslet.

Ett snabbt sätt att få några siffror på plats är att utgå från en siffras förekomst i två av tre närliggande 3 × 3-lådor. I bildexemplet kan man se att siffran 5 finns i två av de tre lådorna överst. Eftersom den också ska finnas i översta lådan till höger, så kan man i de vågräta raderna se att vågrät rad 1 och 2 är upptagna, och att 5 därför ska finnas i vågrät rad 3 för lådan till höger. Mittpositionen är upptagen av siffra 6, raden till höger är upptagen av siffran 5 i lådan längst ner till höger, vilket innebär att 5 ska placeras på plats vågrät 3, lodrät 7! Med denna teknik kan man gå igenom alla siffror och ofta komma en bra bit på vägen. Oftast tar det stopp efter ett tag, och då rekommenderas att granska täta vågräta rader, lodräta rader eller lådor, för att se om man med uteslutningsmetoden kan placera ut återstående siffror.

Om man verkligen kör fast, kan man behöva räkna på längre logiska sekvenser som leder fram till en inkonsekvens, vilket gör att det andra alternativet är det riktiga. Då krävs ofta att man noterar vilka siffror som är möjliga i varje ruta. För svåra sudoku måste man börja med att utesluta att en viss siffra kan finnas på en viss plats, och efter några sådana uteslutningar kan man komma fram till beroenden som leder till en slutsats om en viss siffra på en viss position.

Matematisk bakgrund

En matris om n×n rutor, där varje ruta är tom eller innehåller en av n olika symboler samt varje symbol förekommer högst en gång i varje rad och högst en gång i varje kolumn, kallas en partiell latinsk kvadrat. En fullständig latinsk kvadrat är en partiell latinsk kvadrat där ingen ruta är tom, och alltså varje rad och varje kolumn innehåller varje symbol exakt en gång. Att fylla i de tomma rutorna i en partiell latinsk kvadrat så att man erhåller en fullständig sådan kallas att komplettera den latinska kvadraten, och är ett matematiskt problem som historiskt studerats bland annat med tanke på tillämpningar inom schemaläggning. Sett ur detta perspektiv är lösandet av ett sudoku problemet att komplettera en partiell latinsk kvadrat, under bivillkoret att varje symbol (1–9) dessutom måste förekomma exakt en gång i varje 3×3-låda. Dessutom kan ett sudoku därmed definieras som: en partiell latinsk kvadrat vilken under detta bivillkor har en unik komplettering till en fullständig latinsk kvadrat.

En latinsk kvadrat är ett begrepp med ett stort antal symmetrier. Raderna kan permuteras (dvs. ändras ordning på) helt fritt, liksom oberoende av detta kolumnerna och symbolerna. Bivillkoret med 3×3-lådor bryter delvis dessa symmetrier; rad 1 kan i ett sudoku byta plats med rad 2 eller rad 3, med inte med rad 4 eller uppåt eftersom dessa går genom andra lådor; däremot så kan blocket av raderna 1–3 byta plats med blocket av raderna 4–6, eftersom detta bevarar relationen att två rutor ligger i samma låda. Samma begränsningar gäller i ett sudoku för permutation av kolumner, medan symbolerna kan permuteras lika fritt som i en allmän latinsk kvadrat. Det senare innebär att varje sudoku är isomorft med till exempel ett sudoku där första raden i lösningen är 123456789; att på så vis normalisera sudokun kan vara praktiskt om man vill jämföra två sudokun med varandra, men det skulle förta mycket av sudokuts utmaning som logiskt pussel. Likaså kan man, även under de begränsningar som 3×3-lådorna lägger på permutationer av rader och kolumner, välja att göra vilken ruta som helst till mittrutan i mittlådan i ett isomorft sudoku.

Varianter

Det finns i dag ett stort antal varianter på sudoku. En av dem är Godoku, där siffrorna ersatts av bokstäver. En annan är samurajsudoku, som består av flera sudokuplaner där varje enskild plan har en låda gemensam med någon av de andra planerna. En tredje variant, som kan vara betydligt svårare än vanligt sudoku, är extrem sudoku.

Storleksvariation

Ett vanligt sudoku har 9×9 rutor, men en latinsk kvadrat kan ha vilken sidlängd som helst; det huvudsakliga hindret för att ändra antalet rutor på en sida är frågan om hur man skall anpassa lådvillkoret. Det enklaste är att fortsatt kräva att lådorna skall vara kvadrater, i vilket fall även sudokuts sidlängd och antalet symboler måste vara en jämn kvadrat. Termen jättesudoku förekommer för ett sudoku med 16×16 rutor, uppdelade som 4×4 lådor om 4×4 rutor vardera; som symboler i ett jättesudoku kan användas siffrorna 0–9 samt bokstäverna A–F. Nästa steg skulle ha 25×25 rutor, uppdelade på 5×5 lådor om 5×5 rutor vardera.

Det är även möjligt att ha andra sidlängder, om man släpper på kravet att lådorna måste vara kvadrater. Ett pussel med 6×6 rutor, uppdelade på 2×3 lådor om 3×2 rutor, skulle ändå vara mycket likt ett vanligt sudoku. Ytterligare varianter skulle vara möjliga om man tillåter lådor som inte är rektanglar, men sådana pussel har egenheten att vissa rutor är aningen speciella, eftersom olika rader skulle innehålla olika många rutor från en låda.

Godoku

Godoku är samma sak som sudoku fast med skillnaden att i godoku används bokstäver i stället för siffror. I ett godoku gömmer det sig ofta ett ord, men det är inget krav för att det ska kallas ett godoku. Rent logiskt har godoku precis samma svårighetsgrad som ett sudoku, men mänskligt kan ett godoku vara besvärligare eftersom varje nytt godoku har en ny uppsättning symboler.

Extremsudoku

Extremsudoku (engelska: killer sudoku eller sumdoku; japanska: サムナンプレ samunanpure) är en svårare variant av sudoku. Till skillnad från ett vanligt sudoku ges inga hjälpsiffror alls från början. I stället är hela sudokuplanen indelad i grupper som markeras av streckade linjer. I varje grupps övre vänstra hörn anges den summa som siffrorna i gruppen skall ge.

I övrigt gäller de normala sudokureglerna: Varje rad, kolumn och block skall innehålla siffrorna 1-9 exakt en gång. För extrem sudoku gäller dessutom att en grupp inte får innehålla samma siffra mer än en gång.

Några lösningsmetoder

Extrem sudoku, detalj

• Börja med att leta efter block med en enda grupp där en enda siffra går över blockgränsen. Eftersom totalsumman i varje block skall vara 45, blir det lätt att upptäcka vilken siffra som skall stå i den gränsöverskridande rutan. I bilden ser vi att det nedersta blockets grupper ger totalsumman 41. Därför måste den ensamma rutan från blocket ovanför innehålla en 4. Därmed blir det även klart att det övre blockets övre vänstra ruta måste innehålla 5.
• Sök efter gruppsummor där gruppen måste innehålla bestämda siffror. Exempel på detta: En grupp med summan 3 måste bestå av 1 och 2, en grupp med summan 4 måste bestå av 1 och 3, en grupp med summan 23 måste bestå av 6, 8 och 9. Undersök om dessa "tvingande siffror" utesluter förekomsten av andra "tvingande siffror" i samma block, rad eller kolumn. I bilden ser vi att det övre blockets vänstra kolumn innehåller en grupp med summan 5. Denna summa måste bildas av 1 och 4 eller av 2 och 3. Eftersom gruppen redan innehåller 1, måste 5-gruppen bestå av 2 och 3.
• Sök efter grupper med lika totalsumma och lika antal rutor inom ett och samma block. I bilden ser vi att det nedersta blocket innehåller två 2-rutorsgrupper med totalsumman 14. 14 på två rutor kan bara bestå av 5 och 9 eller 6 och 8. Eftersom det övre blockets översta vänstra ruta måste innehålla 5, kan den lodräta 14-gruppen i det nedre blocket bara bestå av 6 och 8. Detta i sin tur gör att den vågräta 14-gruppen måste bestå av 5 och 9. Eftersom 5 redan finns i den vänstra kolumnen, måste 5 i den vågräta 14-gruppen stå i den högra rutan.
• Man har mycket stor hjälp av att lära sig de sifferkombinationer som med olika rutantal blir de enda möjliga för att åstadkomma bestämda gruppsummor.
• Glöm inte att de vanliga sudokureglerna gäller. Du kan därför dessutom använda alla de normala lösningsmetoderna.

Samurajsudoku

Ett samurajsudoku med 5 ihopkopplade sudoku.

Samurajsudoku, eller familjesudoku, är en variant av sudoku som under år 2005 spred sig explosionsartat från Japan över världen. Den här varianten kännetecknas av flera överlappande sudoku, ihoplagda så att varje plan har minst ett hörnblock gemensamt med ett hörnblock i en annan plan. Ofta saknas givna siffror helt och hållet i de för flera planer gemensamma blocken.

Varje enskild sudokuplan i ett samurajsudoku består av 9 x 9 rutor, uppdelade i 3 x 3 block med 9 rutor i varje. För var och en av planerna gäller de normala sudokureglerna: Man skall placera siffrorna 1 till 9 i de tomma rutorna. Varje rad, spalt och block skall innehålla alla nio siffrorna exakt en gång.

Den vanligaste varianten av samurajsudoku består av fem planer, i Japan kallat Gattai 5 sudoku ("fem kopplade sudoku"). I Japan är det dock inte ovanligt med tjugo eller fler hopkopplade planer.

Se även

• Kakuro ("Efterföljare" till sudoku)
• Korsord

Externa länkar

• Eurosudoku (engelska)
• 4th World Sudoku Championship (en, sv)
• Sudoku på Open Directory Project (engelska)
• Forum för sudokuprogrammerare - Ogiltig länk 2016-07-15 (engelska)