Hvor mange løsninger har Sudoku?

[Simen1]

Jeg satt og løste et par oppgaver ved frokostbordet i dag og begynnte å lure på hvor mange løsningsmuligheter som finnes edit: gitt at man starter med en helt blank oppgave.

 

Eksempel på en ikke blank oppgave:

 

Brettet inneholder 9x9 felter og hvert felt kan fylles ut med tallene 1-9. Det absolutte taket på antall kombinasjoner er altså 9^81. Men sudoku inneholder jo mange regler som begrenser dette yttligere. F.eks VET vi at det er nøyaktig 9 av hvert siffer. Vi VET også at sifrene ikke kan plasseres tilfeldig men må stå i bestemte posisjoner i forhold til hverandre. Til slutt vet vi at det er massevis av symetri: Man kan vri 90 grader 4 ganger for å få 4 like løsninger men sett fra forskjellige kanter av brettet. Vi vet også at vi kan bytte plass på alle 1-tallene og 2-tallene uten å bryte reglene. Det samme gjelder resten av tallene. Med andre ord 4*9! = 1451520 symmetriløsninger for hver unike løsning.

 

Hvis vi ser bort i fra symmetrien, hvor mange unike løsninger finnes?

Endret 29. desember 2005 av Simen1

[Zethyr]

Ikke helt sikker på hva du mener her.. En sudoku-oppgave konstrueres vanligvis ut fra et gitt sett med regler som gir oss kun én løsning.

[Simen1]

Beklager, jeg var litt uklar i spørsmålsformuleringen. Jeg mente: Hvor mange unike sudoku-løsninger finnes det totalt gitt at du starter med en helt blank oppgave. (ingen faste holdepunkter)

 

Tenk 8-queen problemet i sjakk. Hvor mange måter er det mulig å sette opp 8 dronninger på et sjakkbrett uten at noen av dronningene kan ta en av de andre med ett trekk? Det er mulig å sette opp dronningene på flere slike måter men det er ganske vanskelig å finne ut av.

Endret 29. desember 2005 av Simen1

[Knuta2]

Jeg har et program som teller antall løsninger ut i fra et gitt oppgavesett. Da jeg startet med et blankt ark avbrøt jeg den pga at jeg så at tiden rant av gårde. Halve arket var fremdeles likt etter en million løsninger. Bare det siste haldelen var forskjell.

 

Tipper at hvis jeg fintuner programmet, og legger til flere og raskere algoritmer så kunne det være en mulighet for å finne antall løsninger ved å telle i et år eller så.

[Simen1]

Jeg tror det er litt tungt å kjøre brute force på det. I hvertfall hvis du ikke legger inn reglene før løkkene. Da blir det 9^81 muligheter eller ca 2*10^77 muligheter. Noe som ikke vil kunne løses med alle verdens datamaskiner i løpet av jordas levetid.

 

Men legg inn reglene som kriterie for å kjøre løkkene så skal det være mulig å kutte betraktelig ned.

[DrKarlsen]

Du har 6,670,903,752,021,072,936,960 forskjellige løsninger, eller 9! * 72^2 * 2^7 * 27,704,267,971.

[Torbjørn]

kan du forklare utregningen?

[Simen1]

Du har 6,670,903,752,021,072,936,960 forskjellige løsninger, eller 9! * 72^2 * 2^7 * 27,704,267,971.

5355399[/snapback]

Hvordan kom du frem til det?

 

Jeg forstår det med 9! fordi alle settene med like tall kan byttes inbyrdes

Og 4 på grunn av symmetrien der man kan se brettet fra 4 kanter, og 2 fordi man kan speilvende brettet, altså 2^3, men hva er resten tallene?

 

Edit: Som vanlig .. Wikipedia har svaret

A valid Sudoku solution grid is also a Latin square. There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960 [7] (sequence A107739 in OEIS). This number is equal to 9! × 72^2 × 2^7 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions [8] (sequence A109741 in OEIS). The number of valid Sudoku solution grids for the 16×16 derivation is not known.

Edit2: Nå skjønner jeg hvor en til faktor på 2^2 kommer inn: Speiling via de to diagonalene.

Edit3: Nå skjønner jeg hvor en faktor 3^2 kommer inn: Rullering av hele brettet hhv. 3 og 6 celler til høyre gir ett av 3-tallene. Det andre 3-tallet kommer fra rullering av hele brettet hhv. 3 og 6 celler ned.

Edit4: Jepp, nå tror jeg at jeg skjønner de siste symmetrifaktorene. Hvis man snur opp ned de tre første radene så har man ett av 2-tallene. På samme måte kan man snu rad 4-5-6 og 7-8-9. Altså 2 2-tall til. De siste to 2-tallene hentes fra å snu kolonne A-B-C og B-C-D. Den siste kolonnen kan ikke snues for da blir brettet lik ett av rulleringene speilvendt.

 

Da gjenstår bare forklaringen på primtallet 27 704 267 971. Er det noen som kaster seg i vei med den forklaringen

Endret 29. desember 2005 av Simen1

[DrKarlsen]

Det at tallet er primtall har kanskje ikke så mye å si, men det bare nevnes der. Hvor det kommer fra vet jeg ikke, er sikkert en eller annen fyr som har prøvd seg frem

[Zethyr]

er sikkert en eller annen fyr som har prøvd seg frem

5355708[/snapback]

En eller annen datamaskin. Stod vel det i teksten, gjorde det ikke?

The result was derived through logic and brute force computation.

Vil tro at bruteforcinga ligger i dette primtallet.

[DrKarlsen]

Hehe, datamaskinen fant vel ikke ut selv at den skulle prøve seg frem, så det var jo egentlig en fyr. Men du har selvfølgelig riktig.

[Knuta2]

Jeg finner ikke helt logikken i svaret. 6670903752021072936960 er ikke delig på 5472730538

6670903752021072936960 = 2^20 * 3^8 * 5 * 7 * 27704267971

5472730538 = 2 * 11^2 * 23 * 983243

 

 

Jeg kjøper Simen1's svar 4*9! = 1451520 om symmetriløsninger.

 

Så hvis jeg setter et sudoku ark som starter slik,

123456789

xxxxxxxxx

xxxxxxxxx

xxxxxxxxx

xxxxxxxxx

xxxxxxxxx

xxxxxxxxx

xxxxxxxxx

xxxxxxxxx

vil dette kunne utelukke alle symmetriløsninger? I så fall vil antallet begrense seg til 9^72 muligheter å teste ut. Noe som vi også kan begrense med å sette regler o.l. pluss å kjøre et sterkt modifisert program på flere maskiner for å øke ytelse.

[Brusfantomet]

kansjeprøve og finne en løsing for 6*6 først, og så bruke samme teknikk på 9*9

[Forumforumforum]

eller ca 2*10^77 muligheter. Noe som ikke vil kunne løses med alle verdens datamaskiner i løpet av jordas levetid.

 

ikke vær for sikker du nå ;p

 

var det ikke bill gates som sa at man aldri kom til å få brukt for mer enn et latterlig lavt antall mb med minne ? ;P

 

det er INGEN på forumet her som veit åssen dataene er når gjennomsnittsalderen på oss her er f.eks 75 år!

 

litt OT bare x]

[Simen1]

Knuta2: Jeg skal se litt på de tallene senere.

 

Men det med flere symmetrier enn 4*9! : Her er noen av dem, og som fint kan brukes på eksemplet ditt:

 

- Speilvend brettet om diagonalen fra øvre venstre til nedre høyre

- Speilvend brettet om diagonalen fra nedre venstre til øvre høyre

- Bytt om rad 1 og 3

- Bytt om rad 4 og 6

- Bytt rad 1-2-3 med rad 4-5-6

- Bytt kolonne 1 med kolonne 3

- Bytt kolonne 4 og 6

- Bytt kolonnene 1-2-3 med kolonnene 4-5-6

[Knuta2]

Knuta2: Jeg skal se litt på de tallene senere.

 

Men det med flere symmetrier enn 4*9! : Her er noen av dem, og som fint kan brukes på eksemplet ditt:

 

- Speilvend brettet om diagonalen fra øvre venstre til nedre høyre

- Speilvend brettet om diagonalen fra nedre venstre til øvre høyre

- Bytt om rad 1 og 3

- Bytt om rad 4 og 6

- Bytt rad 1-2-3 med rad 4-5-6

- Bytt kolonne 1 med kolonne 3

- Bytt kolonne 4 og 6

- Bytt kolonnene 1-2-3 med kolonnene 4-5-6

5373118[/snapback]

 

Nå er vel ikke disse løsningene å betrakte som symetrier? Men jeg skal i allefall nyttegjøre meg av infoen, for dette ser ut som jeg kan spare haugevis med tid når det skal beregnes antall løsninger.

 

Hvis det er av interesse, så ligger det en betaversjon av program mitt som kan hjelpe med å løse sudoku. enten du gjøre det selv eller om du får maskinen til å gjøre det. Den viser også antall løsninger om det eksisterer flere på en oppgave.

 

http://www.knuta.no/sudoku.zip

 

Forslag og ønsker mottas med takk

[kjellfp]

Det er riktignok 2 1/2 måned siden sist innlegg, men jeg tenkte likevel jeg kunne utdype litt om beregninger, tallsammenhenger/symmetrier og historien bak tallet 6670903752021072936960.

 

Jeg er aktivt med på forumsiden på www.sudoku.com, der framgangsmåter ble diskutert og Felgenhauer og Jarvis første gang annonserte det endelige tallet i mai 2005. Tellingen tok rundt 10 timer første gang. Jeg har selv vært med på å korte ned denne tiden, og pr idag er det (så vidt jeg vet) jeg som har den raskeste tellingen, på 13.3 millisekunder (3GHz CPU), diskutert i denne tråden. For tiden jobber jeg med 4x3-tellingen (12x12-brett delt opp i bokser på størrelse 4x3, skal fylles inn med tall fra 1 til 12 der hver rad, kolonne og boks har forskjellige tall). Selv om 3x3-tellinga tar langt under et sekund, regner vi med at 4x3 tar rundt 100 dager. 4x4-tellinga er det ingen som har noen tro på at er mulig.

 

Effektiv Sudoku-telling gjøres ved at man teller hvert bånd (tre bokser ved siden av hverandre) hver for seg. Man ser på en kolonnekonfigurasjon av et bånd, dvs. man spesifiserer hvilke tall som skal være i hver kolonne i hver boks, men ikke i hvilken rekkefølge de kommer innenfor hver slik "bokskolonne". Dette er nemlig eneste informasjon som er nødvendig for å kunne fylle inn neste kolonnekonfigurasjon, og så den siste. Deretter multipliserer man bare sammen antall måter en konfigurasjon kan omformes til et bånd som faktisk følger sudoku-reglene (ingen like numre på hver rad).

 

Først av alt er det 44 essensielt forskjellige måter å velge den øverste kolonnekonfigurasjonen (konfigurasjoner delt inn i ekvivalensklasser, der to elementer i samme ekvivalensklasse gir like mange løsninger). Dernest er det 56 måter å velge kolonnekonfigurasjonen for hver boks i midterste rad, men man kan så dele på 2 pga symmetrien i at bånd to og tre kan bytte plass. Dette blir m.a.o. 28*56*56 forskjellige valg for midterste kolonnekonfigurasjon. Og da er nederste kolonnekonfigurasjon gitt. Totalt må det kjøres 44*28*56*56 = 3863552 iterasjoner der man summerer et produkt av to tall i innerste løkke. Dette er ingenting for et program skrevet i C.

 

Om symmetrier: På et komplett sudokubrett kan man gjøre totalt 9! * 6^8 * 2 operasjoner som leder til (som regel) forskjellige sudokubrett: 9! er permutasjoner av tallene 1...9. Det er 6 måter å permutere radene innenfor hvert av de tre båndene. Der er også mulig å permutere båndene (f.eks. at øverste og midterste bånd bytter plass), totalt gir dette 6^4 operasjoner. Like mange operasjoner kan gjøres på kolonner og "stacks" (tre bokser oppo hverandre), totalt 6^8 operasjoner. Den siste 2-faktoren er å speile hele brettet om en diagonal.

 

Øvrige operasjoner (rotering av brett, speiling langs midtraden, etc) er bare kombinasjoner av de som er nevnt ovenfor. For så og si alle brett gir dette utelukkende forskjellige brett, men det er noen unntak som andre har nevnt her.

 

Om symmetrier som garantert gir forskjellige løsninger, og derfor må være en faktor i det endelige svaret: For et brett vil enhver av de 9! tall-permutasjonene nødvendigvis gi forskjellige brett. Det er også mulig å permutere radene i midterste og nederste bånd, eller i de "stacks" som er i midten og lengst til høyre. Det er også mulig å bytte midtre og høyre stack, eller midtre og nedre bånd.

 

Flere operasjoner er det ikke mulig (iallefal ikke for meg) å se som garantert alltid gir forskjellige løsninger. Så det endelige nummeret 6670903752021072936960 er dermed iallefall delelig på 9! * 6^4 * 2 * 2. Deler man ut med dette får man altså 2^7 * 27704267971 der sistnevnte er et primtall. Det er ingen vits i å prøve å forstå hvor det tallet kommer fra, det er bare slik det endelige resultatet er.

 

Skal dere slå opp på Wikipedia for mer, er det meste stoffet ikke å finne under Sudoku, men under Mathematics of Sudoku.

[Simen1]

Applaus for et veldig grundig og lærerikt svar