Annons

5 472 730 538 olika sudoku

Det logiska pusslet med rötter i 1700-talet är bara början.

Allt började med Leonard Euler, en schweizisk matematiker som levde mellan åren 1707 och 1783. Ett år före sin död publicerade han en artikel som handlade om "en ny sorts magiska kvadrater". I dag kallar vi dem latinska kvadrater.

En latinsk kvadrat består av ett rutnät med lika många kolumner som rader. I varje ruta ska det finnas en symbol, oftast ett tal. Antalet olika tal som får användas är detsamma som antalet rader (eller kolumner, de är ju lika många). Rutorna ska dessutom vara ifyllda på ett sådant sätt att varje symbol förekommer en enda gång i varje kolumn och på varje rad.

Miljarder sudoku

En sudoku är en speciell latinsk kvadrat med nio rader och nio kolumner, alltså 81 rutor. De ska fyllas med siffrorna 1 till 9. Det som skiljer sudoku från andra latinska kvadrater är det så kallade boxvillkoret: nätet är indelad i nio mindre kvadrater, så kallade boxar. De omfattar vardera 353 rutor, och kravet är att även de nio rutorna i varje box ska innehålla siffrorna 1-9.

Pusslet går ut på att finna slutkonfigurationen utifrån ett begränsat antal rutor som är ifyllda i förväg. Ett välkonstruerat pussel har bara en enda lösning.

Det finns 6 670 903 752 021 072 936 960 olika sudoku. Det svaret kom först alldeles nyligen från den tyske matematikern Bertram Felgenhauer. Men en hel del av dessa sudoku liknar egentligen varandra. I princip är det ingen skillnad om man byter plats på symbolerna på vissa sätt, om till exempel alla 1:or byter plats med alla 2:or. Pusslet förändras inte heller om man ändrar ordningen på de första tre raderna i nätet. Det finns ytterligare flera sådana sätt som man kan flytta om symbolerna och i grunden egentligen ha samma sudoku.

Om man i stället räknar antalet unika pussel blir antalet möjliga sudoku betydligt mindre. Ed Russell och Frazer Jarvis från Storbritannien lyckades nyligen visa att det finns 5 472 730 538 väsentligt olika sudokukonfigurationer. Men med tanke på att var och en av dessa dessutom kan vara slutprodukten av tusentals startkonfigurationer kan vi vara lugna för att antalet olika sudokupussel är tillräckligt många.

Från USA till Japan

Sudokupusslet är faktiskt inte ursprungligen japanskt utan föddes i USA för ett kvartssekel sedan. Det allra första publicerades 1979 i tidskriften Dell Puzzle Magazine under namnet Number Place, men det vann ingen större uppmärksamhet. Senare dök pusslet upp i Japan, som har en gammal tradition för liknande logiska spel.

I Japan fick pusslet först namnet Suuji wa dokushin ni kagiru, vilket betyder "siffra som måste förbli ensam". Snart förkortade man det till Su Doku, "ensam siffra". I Japan införde man också en estetisk förbättring: de från början ifyllda rutorna bildar ett symmetriskt mönster i nätet.

Efter Japan kom pusslet till Storbritannien, också ett land med lång pusseltradition. Därefter exporterades idén till bland annat Sverige.

I de sudoku som finns i dagspressen brukar antalet rutor som är ifyllda från början variera mellan 20 och 35. I de flesta fall är ett pussel med få ifyllda rutor svårare än ett med många ifyllda. Men det går att konstruera riktigt svåra pussel som också har många ifyllda rutor.

En intressant fråga är förstås hur få rutor man behöver ha ifyllda från början för att ändå få en entydig lösning. Rekordet hittills är 17, men det är inte bevisat att det inte skulle kunna vara färre. Det finns fler än 20 000 pussel med bara sjutton ifyllda rutor. Dessa pussel är dock inte symmetriskt ifyllda från början. För symmetriska pussel är det minsta antalet 18 ifyllda rutor.

En annan fråga som saknar svar handlar om det största antalet ifyllda rutor där varje ruta faktiskt behövs för en entydig lösning. Med andra ord, om man tar bort vilken som helst av de ursprungliga siffrorna så kommer pusslet att sakna en entydig lösning. För närvarande är det största antalet 32.

Ytterligare frågor som kan vara värda att närmare titta på är att konstruera sudoku med så många tomma boxar och rader som möjligt. Än så länge är det bästa resultatet ett pussel med fyra helt tomma boxar och ett pussel där antalet helt tomma boxar och rader tillsammans är nio.

Den svåraste sudokun

En sudoku kan göras hur svår som helst, särskilt om man betraktar sudokus med fler kolumner och rader än nio. Sudoku tillhör en klass av problem som i matematiken kallas NP-problem (nondeterministic polynomial time problems). Det innebär att tiden det tar för en dator att finna lösningen växer exponentiellt, det vill säga extremt kraftigt, som en funktion av antalet rader och kolumner hos en sudoku. Att så är fallet bevisades nyligen av Takayuki Yato och Tahashiro Seta vid Tokyos universitet.

Mer exakt bevisade de att sudoku är NP-komplett, vilket betyder att soduku tillhör gruppen av de allra svåraste problemen i NP-klassen. Och här snuddar de vid ett av de hetaste områdena inom matematikforskningen, nämligen om NP-problem kan lösas med snabbare algoritmer eller om det inte finns några sådana möjligheter. Svaret på frågan har en prislapp på en miljon dollar donerade av Clay Mathematics Institute i USA.

Ortogonal sudoku

När Euler introducerade de latinska kvadraterna år 1782 gjorde han det genom att formulera ett speciellt problem: sex regementen skickar var sin delegation bestående av sex officerare med sex olika grader till ett möte. Kan dessa 36 officerare ställas i en kvadrat på sådant sätt att ingen rad eller kolumn innehåller två officerare av samma rang och inte heller två officerare från samma regemente?

Om problemet förenklas så att man bortser från antingen officerarnas rang eller regemente kan det beskrivas som en enkel latinsk kvadrat med sex rader och sex kolumner. Det finns 812 851 200 olika sådana kvadrater.

Men om man tar hänsyn både till rang och regemente så blir problemet betydligt mer komplext. Man måste då använda två latinska kvadrater där det, om man lägger dem på varandra, inte finns två rutor som innehåller samma grad och regemente. Sådana par av kvadrater kallas för ortogonala latinska kvadrater. I Eulers fall, med sex rader och sex kolumner, finns inga sådana par av kvadrater.

Euler observerade att om hans exempel hade rört 3, 4, 5 eller 7 regementen och lika många officersgrader hade det funnits en lösning, men för just 6 regementen och 6 grader fann han ingen lösning. Det dröjde ända till år 1900 innan fransmannen Gaston Tarry bevisade att Euler hade rätt och att hans uppgift verkligen saknar lösning.

Om vi ökar antalet kolumner och rader till nio finns det däremot många par av ortogonala latinska kvadrater. Frågan är om det också går att lägga till boxvillkoret, så att det blir en ortogonal sudoku. Ingen har tidigare försökt göra ortogonala sudokupussel. Men det visar sig gå alldeles utmärkt.

Sudoku och datorer

Som med de flesta logiska pussel ligger utmaningen i sudoku inte enbart i att finna lösningen utan också i att göra det med enbart logiska resonemang. Men på riktigt svåra sudoku fungerar det inte alltid, och man kan bli tvungen att tillgripa brutalare metoder, som att använda en dator.

De flesta sudokulösningsprogram är baserade på en relativt enkel metod som prövar sig fram ruta för ruta. Sådana algoritmer leder till en lösning inom några sekunder.

Ett fåtal program innehåller dock metoder som mer liknar dem som mänskliga lösare använder. På senare tid har det dykt upp elegantare algoritmer baserade på matchning och färgläggning av grafer. Flera sudokuprogrammerare tillämpar även så kallad villkorsprogrammering. Dessa algoritmer gör att datorn oftast kan undvika den enkla prövande metoden, men inte alltid. Det svåraste pusslet som presenteras på dessa sidor är just ett sådant exempel som står emot alla i dag tillämpade algoritmer, utom den brutala metoden, förstås.

Du har just läst en artikel från tidskriften Forskning & Framsteg. Prenumerera här.

Kommentera:

6

Dela artikeln:

TIDNINGEN FÖR DIG SOM ÄR NYFIKEN PÅ ALLVAR
11 nummer 779 kr
2 nummer 99 kr
Du vet väl att du kan läsa Forskning & Framsteg i din läsplatta? Ladda ned appen från App Store eller Google Play. (Läsplatteutgåvan ingår i alla prenumerationer.)

Kommentarer

HejKul med sudokuartikeln. De flesta dagstidningssudoku blir lite väl enkla när man har löst ett antal. Jag försökte mig på att lösa några av de exempel som fanns i fof. I exempel 2, den med bara 17 givna siffror, kom jag fram till att lösningen inte är entydig! Ruta 6 och 8 i rad ett och två kan vara kan antingen 8 och 9 resp 9 och 8 eller tvärtom dvs 9 och 8 resp 8 och 9.En entydig sudoku skall väl bara ha en lösning.

Hej!Jag håller med om att artikeln var intressant, fast jag håller inte riktigt med om hur det räknas ut hur många möjliga Sudoku det finns. Det beror ju helt och hållet på efter vilka regler man räknar.@Karl Källander:Sent kommer en kommentar på ditt resultat. :DDet Sudoku du hänvisar till har visst en unik lösning! :) Jag satte mig för kul skull och testade att lösa det efter att jag hade läst din kommentar nyss.Det du pekar på är en felaktig lösning. Leta igenom ditt pussel så ser du att det skall stå en fyra på ruta åtta i rad ett.Du har garanterat en dubblett på någon rad, kolumn eller box.Undrar du mer så hör av dig på pbgm(SNABELA)algonet.se så kan jag visa mer.

Exakt så, Karl!Jag har byggt en excelkalkyl som räknar ut detta i ett nafs. MEN, när den får pussel med flera lösningar ger den upp och stannar. Jag kan gissa ett av de alternativ som finns som val, och ofta fungerar då alla alternativ kalkylen visar som val! (I regel två olika).Jag har stött på massor av dagstidnings-sudoku's som är icke-entydiga. När man löser själv ser man som regel inte den andra lösningen. Man går vidare när man funnit den första, vilken det än var.Jag vet inte varför sådana smyger sig in ibland, men skulle kunna nämna en tidning som har betydligt fler än andra här (inte FoF). Jag har sparat en del. Torde väl ha att göra med varifrån de hämtar utgångsraden, eller hur den gjordes..

Jag fyllde år i går och fick en väldigt fin present av brorsan: Forskning o framsteg 8/05.Nu kunde jag kontrollera mitt program på något svårt!Jag erhöll bl a följande lösningar till Sudoku-figurerna 1 och 3:Figur 1 har minst 4 olika lösningar, den som tidningen ger och en helt annorlunda, med 3 olika slut beroende på var den sista 9:an placeras.Slutpositioner innan 9:an placerats i nedersta raden: 8 och 2 byter plats på rad 3 beroende på var 9:an placeras.. 9:an kan vara till vänster i tomma raden nederst eller till höger. 1 och 2 kan byta plats i nedersta raden när 9:an är till höger..8715934 62452671389936_4_157543__7896267_3_541198465273319754628725386914684___735Fig 2 verkar vara entydig, jag har inte funnit någon annan lösning än den FoF visar.Fig 3: 5 lösningar med 1, 7 eller 8 i ruta 5-8.1:an i 5:8 ger en lösning, 7:a i 5:8 ger ytterligare två val på 2 och 8 nedersta raden, strax under 7:an och den till höger bredvid. När 8:an är till höger längst ned kan dessutom 8 o 1 byta plats på rad 5med rad 3:s dito (läge 5:4-5 mot 3:4-5.8:an i 5:8 ger slutligen ytterligare en til lösning.938246715412537896675___2431647__358329__54678574639217869541322436__5_95913__6_4Detta är långt från alla lösningar. Behåll raderna 1,2,3 och 7,8,9 inkl tomma härovan, samt kolumnerna 2,3, 7 och 8. Låter man nu 8:an byta plats i kol 4, rad 4,5 o 6 räcker det med att skifta runt 1,3 och 8 i första kolumnen samt 1, 7 och 8 i kolumnen längst till höger mittemot för att ta fram ett stort antal nya varianter i framförallt mitten. Vidare kan 4 och 6 i översta raden behöva skiftas emellan sig.Börja med att variera som tidigare med 1,7 och 8 i kol 5, rad 8 som förut.Jag har kontrollerat att tidningslösningarna också stämmer. Om man där kopierar endast kolumn 1, 4, 8 och 9 i fig 3-lösningen kan man direkt erhålla minst 4 lösningar genom att byta ut 8:an i kol 3, rad 2 mot en 1:a eller 2:a..Hur resonerar man när man kommer fram till att en Sudoku är entydig? För mig verkar det som att det inte finns en metod som håller helt.Eller är det någon som ser något stort fel i lösningarna? Något jag blivit "blind "av.

Hej. Skulle ni kunna lösa ett suduko åt mig om jag skickar exakt så det ser ut?

ok

Lägg till kommentar