Varför tycks alla sudokun ha ett geometriskt mönster? Det kanske finns utan men alla jag sätt i tidningar har ett mönster.

De är symmetriska på båda "storaxlarna", om jag inte minns fel.
Personligen tror jag att det är av rent estetiska skäl.

Om du tänker dig en sudoku av följande utseende:

ABC
DEF
GHI

Varje bokstav motsvarar en 3x3-tabell.
Då kan man ju byta plats på två rader eller två kolumner;
DEF
ABC
GHI

Eller tänker jag fel?

Vet inte varför de är symmetriska men här är en ganska snygg (och tydligen omöjlig att lösa logiskt):

<code>
9 . . | . 4 . | . . 1
. . . | 5 . 2 | . . .
. . 8 | . . . | 3 . .
------+-------+------
. 5 . | . . . | . 7 .
1 . . | . 9 . | . . 2
. 2 . | . . . | . 4 .
------+-------+------
. . 3 | . . . | 8 . .
. . . | 7 . 6 | . . .
4 . . | . 1 . | . . 9
</code>

975 843 621
316 572 498
248 961 357

859 234 176
134 697 582
627 158 943

763 429 815
591 786 234
482 315 769

<b>>och tydligen omöjlig att lösa logiskt</b>
Kom på en matematisk sats för det där i förbifarten för ett par dar sen.

Det finns två kategorier av sudoku; "äkta" och "falska". De äkta är de som bara har en enda lösning.
En falsk skulle kunna vara för en "mini-sudoku":

1234
4321
2xx3
3xx2

vilket har lösningarna:


1234
4321
2143
3412

eller


1234
4321
2413
3142


Nåja; alla "äkta sudoku" är alltid möjliga att lösa med fixa logiska regler.

>Nåja; alla "äkta sudoku" är alltid möjliga att lösa med fixa logiska regler.

Jo det är väl så men frågan är hur långt fram man måste titta. Ovanstående sudoku går inte att lösa med de vanliga metoderna som svärdfisk och multipla färger.

När man väl har löst de två första siffrorna (9 i r2c8 och r8c2) finns det vad jag vet inget annat sätt än att prova.

Personligen tycker jag nog inte att det är någon principiell skillnad i hur man kollar. Egentligen så finns det bara tre regler;
- Varje siffra får bara förekomma en gång i varje 3x3-ruta
- Varje siffra får bara förekomma en gång i varje rad
- Varje siffra får bara förekomma en gång i varje kolumn

Står det alla siffror utom 7 på en rad så har man "under ytan" resonerat som att "1 går inte, det ger mig 2 förekomster av en etta i raden.", osv. för 2, 3 ...

Man kollar alltså bara om någon av reglerna bryts på något sätt. I princip så betraktar man hela mängden av alla 9x9-kombinationer där alla tidigare givna tal är låsta. Om det i en ruta då bara finns en enda möjlighet där inte alla sådana kombinationer bryter mot någon av reglerna, så måste det vara det talet i rutan.

Eller för att uttrycka det på ett annat sätt; det du gör är alltid att "prova", frågan är bara vad man sätter gränsen mellan att "prova" resp. ha gjort en logisk slutledning.

Ganska kul att den här tråden kom upp nu. Skrev ett program i förra veckan som "provar" alla möjliga kombinationer som finns med x antal inmatade positioner. Testade på skoj att köra det mot ett Sudoku från en tidning och den tog 9 timmar på sig att lösa det.. :)
Detta var på en hyffsat snabb dator så jag är säker på att det finns 100 sätt att göra algoritmen snabbare..

Mvh
Peter

Jag är också jätte intresserad av problemmet.Känner stor tillfredställelse
om jag lyckas skriva en algoritm som löser ett givet problem.
http://www.pellesoft.se/communicate/forum/view.aspx?msgid=201348&forumid=2&sum=0

Jobbar på en lösning.

Kolla gärna min (med god hjälp från flera (Trach) mfl. stycken här hos pelle.)
Mandelbrot:
Programarkivet:Ny Optimerad Mandelbrot
kolla även
Programarkivet:Magisk Kvadrat

Hade faktiskt som labb i skolan för ett tag sedan att skriva ett program som löste sudokus med hjälp av sökning. Fixade det med en variant av A*-sökning och det går rent ut sagt förbannat snabbt att lösa i stort sett alla jag testat med (finns att testa här: http://student.chl.chalmers.se/~andreasd/portfolio/SudokuSolver.jar).

Rätt kul att just detta med Sudoku dyker upp här & nu.
Själv har jag bara erfarenhet av VB + lite Flash nu på slutet.

Därför ser jag ut om ett frågetecken då jag möter sånt som
"en variant av A*-sökning" och en .jar-fil. Om det nu är inom
rimliga gränser praktiskt möjligt, så får du gärna brodera ut detta
lite ytterligare + Hur/vad gör man med en .jar?

ChristerGbg

Jar-filen är egentligen bara ett arkiv med javaklasser. Om man har den senaste java-runtimen installerad (kräver 1.5) så borde det räcka med att ladda ner filen och köra den för att det skall funka och om det ändå inte gör det kör man den genom att i command skriva "java - jar SudokuSolver.jar".

A*är en metod för att hitta kortaste vägen mellan två noder i en graf. I detta fallet från det olösta startläget av sudokut till ett läge då hela är löst.

Ah! Naturligtvis!

Jag sa ju nästan exakt förutsättningarna smo gör det rimligt (jiddret om mängden av alla 9x9...) men jag kopplade aldrig den självklara idén att det faktiskt i viss mån är en path man ska hitta.

Jävligt snyggt!

Förresten, en fråga:
Hur har du löst grejen att man ju i princip inte vet var man ska?
I allmänhet används ju A* för att hitta från en given startpunkt till en given slutpunkt. Men du vet ju inte slutpunkten, bara några få egenskaper för den...?

Vad man vet är ju att när alla rutor är ifyllda enligt sudoku-reglerna har man nått målet. Att hitta vilken väg man skall gå löser A* genom att hela tiden ta den väg som ger lägst kostnad utifrån kostnaden att nå ett visst tillstånd + uppskattad kostnad för att nå målet.

I vårat (vi var två som gjorde labben tillsammans) fall så väljer vi att hela tiden titta på det block om 3x3 rutor som innehåller flest siffror och väljer att sätta ut den siffra av de tillåtna på den positionen som förekommit minst gånger totalt. Efter att det är gjort så väljer den vilket tillstånd den skall utveckla utifrån antalet ej utsatta av den minst förekommande siffran + antalet resterande tomma rutor (stämmer inte helt överens med hur A* funkar och det går säkerligen att uppskatta den bästa vägen ännu bättre men det är tillräckligt effektivt, därav "en variant av A*", antagligen hade det varit mer rätt att kalla vår algoritm för en best-first sökning inspirerad av A*). Om vi stöter på en ruta där det inte finns några möjliga siffror att sätta ut tar vi bort det senast utvecklade tillståndet och provar med det näst bästa enligt samma metod.

Min förklaring blev kanske lite rörig där, hoppas det går att förstå...

Verkligen imponerande.Mitt första test gick på < 1 sek.

Vad är .jar för typ av program ?. Skulle vara intressabt att porta koden till VB.

Sven Åke > Jar är, Som David sa, en fil med Java-klasser alltså .class filer. Jar-filer kan öppnas med WinZip och .class-filer kan dekompileras med http://www.bysoft.se/sureshot/cavaj/Cavaj. Men kanske David lämnar ut koden så du inte behöver h4x4 hans kod :)

Precis.

Lämnar mer än gärna ut koden, men jag måste kolla med min labbkamrat så det är okej först. Sen bör man väl varna att eftersom det var en tidsbegränsad labb innehåller koden en hel del skräp som vi aldrig brydde oss om att städa undan. Tror nästan att det är enklare att porta det till något annat språk genom att helt enkelt bara implementera samma algoritm och strunta i hur vår kod ser ut :P

Förresten, går AI i period 1?
Jag kommer ha min i period 4.

Jo, för oss som läser Intelligent Systems Design. Har ingen aning om hur det ser ut om man läser något annat.

<b>Men kanske David lämnar ut koden så du inte behöver h4x4 hans kod :)</b>

Näää... deras lösning är super,så halva nöjet är borta.Jag har förstått deras logiklösning
dvs det där med att börja lösa den 3*3 som har flest antal givna siffror osv. prova.

Javakoden blir svår att slå ifråga om snabbhet.
Han som höll på 9 timmar har fått något att tänka på.

Ja visst, men den går inte att lösa per logik enbart.

Javascriptbaserad sudokulösare hittas på http://www.stenkullengoik.com/tempo-bjorn/sd9.asp

Hola.

<b>>Ja visst, men den går inte att lösa per logik enbart.</b>
Jo.
Vad är logik?
Är det en äkta suduko, så är det enbart logik som krävs.

Bra Niklas,då är Vi i allafall två som vet vad ordet "logik" betyder.

Fortsätter envis som jag är med en Vb lösning.

Ang. Logik
Det ena ger det andra så fortsätter Vi !

Tror ingen ännu har svarat på den inledande frågan varför de så ofta är geometriska. Anledningen är att de flesta som skapar de sudoku du ser i tidingar med mera har som ett av sina kriterier att de skall vara just symetriskt. Det går precis lika bra, enkelt med mera att skapa osymetriska sudoku. De andra kraven som egentligen är mer vesäntliga är att det endast skall finnas en enda lösning och att man inte ska behöva ta till ren gissning vid något tillfälle för att lösa det. Sen kan man diskutera vad en "gissning" egentligen är och där finns det lite olika uppfattningar.

Tack Sam!
Där kom svaret jag sökte :P