[viesti Survo-keskustelupalstalla (2001-2013)]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 3.4.2006 16:59 |
Sudoku on harvinaisen suuren suosion saavuttanut peli,
jossa täydennetään annettu ruudukko (tavallisesti 9x9)
numeroin (1,2,3,4,5,6,7,8,9) noudattaen annettuja ehtoja.
Tarkat tiedot pelin säännöistä, sen historiasta ja
levinneisyydestä löytyvät suomeksi esim. sivulta
http://fi.wikipedia.org/wiki/Sudoku
Itse en ennen viime viikonvaihdetta ollut Sudokuja
ratkaissut, koska vältän addiktoitumista peleihin;
Survon (kehittämisen) parissa riittää pelaamista kylliksi.
Koska eräät tuttuni ja jopa survoilijat ilmoittavat Sudokuja
harrastaneensa, päätin rakentaa Survoon ohjelman, joka
tukee pelin ratkaisemista ja selvittää sen halutessa
kokonaan 9x9-, 16x16- ja 25x25-ruudukoilla.
Uuden SUDOKU-komennon saa liitettyä omaan Survoonsa
(SURVO MM, normaali versio) siirtämällä verkosta tiedoston
www.survo.fi/sudoku/_sudoku.exe
SURVO MM:n ohjelmahakemistoon <Survo>\U\
Sudoku-tehtävä annetaan toimituskentässä esim. seuraavasti
kirjoittamalla tyhjiin ruutuihin nollan:
(esimerkkinä Helsingin Sanomien tämänpäiväinen tehtävä)
700000163
010980000
023600500
900830021
060204070
840091005
005009280
000075010
694000007
Tehtävä tulee tallettaa Survon matriisiksi esim. HS030406
lisäämällä toistuvalla INSERT-komennolla (lyh. I) välit tyyliin
I _
7 0 0 000163
0 1 0 980000
0 2 3 600500
9 0 0 830021
0 6 0 204070
8 4 0 091005
0 0 5 009280
0 0 0 075010
6 9 4 000007
antamalla otsikon
MATRIX HS030406 ///
7 0 0 0 0 0 1 6 3
0 1 0 9 8 0 0 0 0
0 2 3 6 0 0 5 0 0
9 0 0 8 3 0 0 2 1
0 6 0 2 0 4 0 7 0
8 4 0 0 9 1 0 0 5
0 0 5 0 0 9 2 8 0
0 0 0 0 7 5 0 1 0
6 9 4 0 0 0 0 0 7
sekä tallettamalla komennolla
MAT SAVE HS030406
Tehtävän ratkaisee silloin komento
SUDOKU HS030406
joka antaa ratkaisutaulukon toimituskenttään
SUDOKU HS030406
Solution: time=0.000
MATRIX SUDOKU.M ///
7 8 9 5 4 2 1 6 3
5 1 6 9 8 3 7 4 2
4 2 3 6 1 7 5 9 8
9 5 7 8 3 6 4 2 1
3 6 1 2 5 4 8 7 9
8 4 2 7 9 1 6 3 5
1 7 5 3 6 9 2 8 4
2 3 8 4 7 5 9 1 6
6 9 4 1 2 8 3 5 7
ja samalla tallettaa sen matriisitiedostona SUDOKU.M.
Haluttaessa nähdä ratkaisun eri vaiheet annetaan täsmennys RESULTS=100,
jolloin jatkoksi ilmestyvät toimituskenttään ratkaisun kulkua kuvaavat taulukot:
7 : 5 8 : 89| 45 : 2 45 : 2 |1 : 6 : 3 |
45 :1 : 6 | 9: 8 : 23 7 | 4 7 : 4 : 2 4 |
4 : 2 : 3 | 6 :1 4 : 7 | 5 : 4 9: 4 89|
------------------------------------------------------------------------------------------
9: 5 7 : 7 | 8 : 3 : 67 | 4 6 : 2 :1 |
1 3 5 : 6 :1 | 2 : 5 : 4 | 3 89: 7 : 89|
8 : 4 : 2 7 | 7 : 9:1 | 3 6 : 3 : 5 |
------------------------------------------------------------------------------------------
1 3 : 3 7 : 5 |1 34 :1 4 6 : 9| 2 : 8 : 4 6 |
23 : 3 8 : 2 8 | 34 : 7 : 5 | 34 6 9:1 : 4 6 9|
6 : 9: 4 |1 3 :12 : 23 8 | 3 : 3 5 : 7 |
------------------------------------------------------------------------------------------
(1,6)=2
7 : 5 8 : 89| 45 : 45 : 2 |1 : 6 : 3 |
45 :1 : 6 | 9: 8 : 3 7 | 4 7 : 4 : 2 4 |
4 : 2 : 3 | 6 :1 4 : 7 | 5 : 4 9: 4 89|
------------------------------------------------------------------------------------------
9: 5 7 : 7 | 8 : 3 : 67 | 4 6 : 2 :1 |
1 3 5 : 6 :1 | 2 : 5 : 4 | 3 89: 7 : 89|
8 : 4 : 2 7 | 7 : 9:1 | 3 6 : 3 : 5 |
------------------------------------------------------------------------------------------
1 3 : 3 7 : 5 |1 34 :1 4 6 : 9| 2 : 8 : 4 6 |
23 : 3 8 : 2 8 | 34 : 7 : 5 | 34 6 9:1 : 4 6 9|
6 : 9: 4 |1 3 :12 : 3 8 | 3 : 3 5 : 7 |
------------------------------------------------------------------------------------------
(2,3)=6
jne. (poistettu noin 40 välivaihetta)
(9,8)=5
7 : 8 : 9| 5 : 4 : 2 |1 : 6 : 3 |
5 :1 : 6 | 9: 8 : 3 | 7 : 4 : 2 |
4 : 2 : 3 | 6 :1 : 7 | 5 : 9: 8 |
------------------------------------------------------------------------------------------
9: 5 : 7 | 8 : 3 : 6 | 4 : 2 :1 |
3 : 6 :1 | 2 : 5 : 4 | 8 : 7 : 9|
8 : 4 : 2 | 7 : 9:1 | 6 : 3 : 5 |
------------------------------------------------------------------------------------------
1 : 7 : 5 | 3 : 6 : 9| 2 : 8 : 4 |
2 : 3 : 8 | 4 : 7 : 5 | 9:1 : 6 |
6 : 9: 4 |1 : 2 : 8 | 3 : 5 : 7 |
------------------------------------------------------------------------------------------
SUDOKU näyttää aluksi taulukon, jossa nollien paikalle on asetettu Sudokun sääntöjen
mukaan mahdolliset vaihtoehtoiset numerot ja ilmoittaa sitten, mitä on tehtävissä.
Turhien vaihtoehtojen eliminointi osoittaa, että ruutuun (1,6), joka oli alunperin tyhjä,
on jäänyt vain yksi vaihtoehto (2), joka siis valitaan lopullisesti ja päästään
poistamaan kakkoset rivistä 1, sarakkeesta 6 ja vastaavasta 3x3-lohkosta.
Koska kyseessä on yhden tähden tehtävä, se ratkeaa suoraan tällä perustekniikalla.
Vaikeammissa Sudokuissa tämä ei riitä vaan joudutaan käyttämään mutkikkaampia,
alkuperäisiin ehtoihin perustuvia loogisia sääntöjä.
Perehdyttäessä niihin ehkä paras tietolähde on Andrew Stuartin verkkosivu
http://www.scanraid.com/sudoku.htm
Se mm. esittelee säännöt, joilla ilmeisesti mikä tahansa Sudoku-tehtävä ratkeaa
ilman arvailuja.
Survon SUDOKU-ohjelma ei käytä näitä mutkikkaampia sääntöjä lainkaan.
Perusehtojen ohella se havaitsee vain seuraavat:
Jos esim. jossain sarakkeessa mahdollisten vaihtoehtojen joukossa
tietty numero esiintyy vain kerran, tulee valita tuo numero ja poistaa sama numero
vaihtoehtojen joukosta vastaavalta riviltä ja vastaavasta 3x3-lohkosta.
Samanlaista sääntöä sovelletaan ainutkertaisiin numeroihin riveillä ja 3x3-lohkoissa.
Mutkikkaammat säännöt, joita Survon SUDOKU ei siis käytä, koskevat mm. numeroparien
ja -kolmikoiden esiintymistä.
SUDOKU käyttää tilanteissa, joissa eivät em. perussäännöt enää pure, raakaa voimaa.
Etsitään avoimista ruuduista sellainen, jossa on vähiten vaihtoehtoja.
Valitaan (arvataan) niistä yksi ja jatketaan ratkaisua, kunnes joko päästään lopputulokseen
tai jodutaan vaikeuksiin eli syntyy tilanne, jossa jostain ruudusta vaihtoehdot
loppuvat kokonaan. Tässä jälkimmäisessä tilanteessa tulee palata takaisin
edelliseen arvaukseen ja arvata uudelleen. Tätä sanotaan backtrack-menettelyksi.
Se johtaa aina lopulta ratkaisuun eikä ole välttämättä edes kovin hidas, mutta
varmasti vastoin monen Sudoku-harrastajan pyhiä periaatteita.
SUDOKU mittaa myös varsinaiseen ratkaisuun (ilman syöttö- ja tulostusvaiheita)
kuluvan ajan sekunteina. Vaikeinkin 9x9-tehtävä ratkeaa koneellani 0.1 sekunnissa,
vaikka en ole optimoinut ohjelmaa ajankäytön suhteen.
Näytteenä hankalammasta tehtävästä on alla Hesarin aprillipäivän 5-tähtinen:
MATRIX HS010406 ///
0 0 1 3 0 0 7 0 2
0 0 6 2 0 0 0 1 0
0 2 0 0 0 0 0 0 4
2 0 0 6 0 1 3 0 9
0 0 0 0 0 0 0 0 0
4 0 3 8 0 9 0 0 7
1 0 0 0 0 0 0 8 0
0 5 0 0 0 6 4 0 0
9 0 4 0 0 8 5 0 0
MAT SAVE HS010406
SUDOKU HS010406 / RESULTS=100
Solution: n[quess]=1 max_depth=1 time=0.010
MATRIX SUDOKU.M ///
8 4 1 3 6 5 7 9 2
7 3 6 2 9 4 8 1 5
5 2 9 1 8 7 6 3 4
2 8 5 6 7 1 3 4 9
6 9 7 4 3 2 1 5 8
4 1 3 8 5 9 2 6 7
1 7 2 5 4 3 9 8 6
3 5 8 9 2 6 4 7 1
9 6 4 7 1 8 5 2 3
5 8 : 4 89:1 | 3 : 456 89: 45 | 7 : 56 9: 2 |
3 5 78 : 34 789: 6 | 2 : 45 789: 45 7 | 89:1 : 3 5 8 |
3 5 78 : 2 : 5 789|1 5 7 9:1 56789: 5 7 | 6 89: 3 56 9: 4 |
------------------------------------------------------------------------------------------
2 : 78 : 5 78 | 6 : 45 7 :1 | 3 : 45 : 9|
5678 :1 6789: 5 789| 45 7 : 2345 7 : 2345 7 |12 6 8 : 2 456 :1 56 8 |
4 :1 6 : 3 | 8 : 2 5 : 9|12 6 : 2 56 : 7 |
------------------------------------------------------------------------------------------
1 : 3 67 : 2 7 | 45 7 9: 2345 7 9: 2345 7 | 2 6 9: 8 : 3 6 |
3 78 : 5 : 2 78 |1 7 9:123 7 9: 6 | 4 : 23 7 9:1 3 |
9: 3 67 : 4 |1 7 :123 7 : 8 | 5 : 23 67 :1 3 6 |
------------------------------------------------------------------------------------------
(5,1)=6 (unique on this column)
-- 5 vaihetta poistettu --
5 8 : 4 89:1 | 3 : 456 89: 45 | 7 : 6 9: 2 |
3 78 : 34 789: 6 | 2 : 4 789: 4 7 | 89:1 : 5 |
5 78 : 2 : 5 789|1 5 7 9:1 56789: 5 7 | 6 89: 3 : 4 |
------------------------------------------------------------------------------------------
2 : 78 : 5 78 | 6 : 45 7 :1 | 3 : 45 : 9|
6 : 7 9: 5 7 9| 45 7 : 2345 7 : 2345 7 |1 : 2 45 : 8 |
4 :1 : 3 | 8 : 2 5 : 9| 2 6 : 2 56 : 7 |
------------------------------------------------------------------------------------------
1 : 3 67 : 2 7 | 45 7 9: 2345 7 9: 2345 7 | 2 6 9: 8 : 3 6 |
3 78 : 5 : 2 78 |1 7 9:123 7 9: 6 | 4 : 2 7 9:1 3 |
9: 3 67 : 4 |1 7 :123 7 : 8 | 5 : 2 67 :1 3 6 |
------------------------------------------------------------------------------------------
guess (1,1)=8 depth=1
8 : 4 9:1 | 3 : 456 9: 45 | 7 : 6 9: 2 |
3 7 : 34 7 9: 6 | 2 : 4 789: 4 7 | 89:1 : 5 |
5 7 : 2 : 5 7 9|1 5 7 9:1 56789: 5 7 | 6 89: 3 : 4 |
------------------------------------------------------------------------------------------
2 : 78 : 5 78 | 6 : 45 7 :1 | 3 : 45 : 9|
6 : 7 9: 5 7 9| 45 7 : 2345 7 : 2345 7 |1 : 2 45 : 8 |
4 :1 : 3 | 8 : 2 5 : 9| 2 6 : 2 56 : 7 |
------------------------------------------------------------------------------------------
1 : 3 67 : 2 7 | 45 7 9: 2345 7 9: 2345 7 | 2 6 9: 8 : 3 6 |
3 7 : 5 : 2 78 |1 7 9:123 7 9: 6 | 4 : 2 7 9:1 3 |
9: 3 67 : 4 |1 7 :123 7 : 8 | 5 : 2 67 :1 3 6 |
------------------------------------------------------------------------------------------
(8,3)=8 (unique on this row)
--- 45 vaihetta poistettu ---
8 : 4 :1 | 3 : 6 : 5 | 7 : 9: 2 |
7 : 3 : 6 | 2 : 9: 4 | 8 :1 : 5 |
5 : 2 : 9|1 : 8 : 7 | 6 : 3 : 4 |
------------------------------------------------------------------------------------------
2 : 8 : 5 | 6 : 7 :1 | 3 : 4 : 9|
6 : 9: 7 | 4 : 3 : 2 |1 : 5 : 8 |
4 :1 : 3 | 8 : 5 : 9| 2 : 6 : 7 |
------------------------------------------------------------------------------------------
1 : 7 : 2 | 5 : 4 : 3 | 9: 8 : 6 |
3 : 5 : 8 | 9: 2 : 6 | 4 : 7 :1 |
9: 6 : 4 | 7 :1 : 8 | 5 : 2 : 3 |
------------------------------------------------------------------------------------------
Tässä jouduttiin siis arvaamaan kerran ja osuttiin heti oikeaan!
................................................................
Sivulla
http://sudoku.sourceforge.net/
(kohta Brain of Britain) mainitaan seuraava tehtävä vaikeimmaksi koskaan havaituista.
MATRIX HARDEST ///
0 2 0 0 0 0 0 0 0
0 0 0 6 0 0 0 0 3
0 7 4 0 8 0 0 0 0
0 0 0 0 0 3 0 0 2
0 8 0 0 4 0 0 1 0
6 0 0 5 0 0 0 0 0
0 0 0 0 1 0 7 8 0
5 0 0 0 0 9 0 0 0
0 0 0 0 0 0 0 4 0
MAT SAVE HARDEST
SUDOKU HARDEST
Solution: n[quess]=148 max_depth=10 time=0.100
MATRIX SUDOKU.M ///
(Katkaisen tulostuksen tähän, jotta asianharrastajat voivat yrittää omin keinoin.)
Yllä max_depth=10 tarkoittaa, että pahimmillaan oli 10 sisäkkäistä arvausta
valittuna!
Hankala on myös seuraava 16*16-ruudukko, jonka selvittämiseen SUDOKU tarvitsee
koneellani peräti 20 sekuntia ja josta em. verkkosivuilla todetaan, ettei sitä
ole tarkoitettukaan "käsin ratkaistavaksi" vaan ratkaisuohjelmien testaamiseen:
MATRIX A16 ///
0 10 0 0 16 0 0 14 0 0 0 0 15 13 0 0
0 11 6 0 2 0 1 0 0 4 0 0 0 9 0 0
0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 7
13 0 0 0 0 10 0 0 0 0 15 0 5 3 8 0
0 0 0 8 6 0 0 11 4 3 0 14 0 0 0 0
0 15 0 0 0 0 8 2 13 0 0 0 14 1 4 0
0 0 16 7 0 5 0 0 0 1 0 0 0 2 0 13
0 14 0 0 12 0 0 0 16 9 10 0 0 0 0 0
0 0 0 0 0 13 7 3 0 0 0 4 0 0 11 0
5 0 12 0 0 0 15 0 0 0 8 0 10 14 0 0
0 2 9 14 0 0 0 10 3 16 0 0 0 0 12 0
0 0 0 0 14 0 4 5 1 0 0 6 16 0 0 0
0 16 13 9 0 8 0 0 0 0 14 0 0 0 0 6
12 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0
0 0 4 0 0 0 9 0 0 11 0 7 0 15 3 0
0 0 1 3 0 0 0 0 5 0 0 2 0 0 7 0
MAT SAVE A16
SUDOKU A16
Solution: n[quess]=20014 max_depth=34 time=20.229
MATRIX SUDOKU.M ///
2 10 8 12 16 9 6 14 7 5 11 3 15 13 1 4
15 11 6 5 2 3 1 7 8 4 13 16 12 9 14 10
4 9 3 16 13 15 5 8 10 14 1 12 2 11 6 7
13 7 14 1 11 10 12 4 2 6 15 9 5 3 8 16
9 13 5 8 6 1 10 11 4 3 2 14 7 12 16 15
6 15 10 11 3 16 8 2 13 12 7 5 14 1 4 9
3 12 16 7 4 5 14 9 15 1 6 11 8 2 10 13
1 14 2 4 12 7 13 15 16 9 10 8 3 6 5 11
16 1 15 10 9 13 7 3 14 2 12 4 6 8 11 5
5 4 12 6 1 2 15 16 11 7 8 13 10 14 9 3
7 2 9 14 8 6 11 10 3 16 5 15 13 4 12 1
8 3 11 13 14 12 4 5 1 10 9 6 16 7 15 2
11 16 13 9 7 8 3 1 12 15 14 10 4 5 2 6
12 5 7 15 10 4 2 6 9 8 3 1 11 16 13 14
10 8 4 2 5 14 9 13 6 11 16 7 1 15 3 12
14 6 1 3 15 11 16 12 5 13 4 2 9 10 7 8
..............................................................
SUDOKU-komento on käytettävissä myös omaehtoisen ratkaisemisen tukena
antamalla täsmennys GUESS=0.
Tällöin SUDOKU lopettaa toimintansa heti, kun se joutuisi
tekemään arvauksen. Täsmennyksellä RESULTS=100 syntyvästä
pelipöytäkirjasta näkee, missä ollaan, ja siitä vain
ratkaisemaan omin avuin eteenpäin! SUDOKU siis hoitaa
pelin "tylsät" perusvaiheet ratkaisijan puolesta.
Esim. HS010406-esimerkissä käy näin:
SUDOKU HS010406 / GUESS=0 RESULTS=100
Partial Solution: time=0.000
MATRIX SUDOKU.M ///
0 0 1 3 0 0 7 0 2
0 0 6 2 0 0 0 1 5
0 2 0 0 0 0 0 3 4
2 0 0 6 0 1 3 0 9
6 0 0 0 0 0 1 0 8
4 1 3 8 0 9 0 0 7
1 0 0 0 0 0 0 8 0
0 5 0 0 0 6 4 0 0
9 0 4 0 0 8 5 0 0
--- välivaiheet poistettu ---
5 8 : 4 89:1 | 3 : 456 89: 45 | 7 : 6 9: 2 |
3 78 : 34 789: 6 | 2 : 4 789: 4 7 | 89:1 : 5 |
5 78 : 2 : 5 789|1 5 7 9:1 56789: 5 7 | 6 89: 3 : 4 |
------------------------------------------------------------------------------------------
2 : 78 : 5 78 | 6 : 45 7 :1 | 3 : 45 : 9|
6 : 7 9: 5 7 9| 45 7 : 2345 7 : 2345 7 |1 : 2 45 : 8 |
4 :1 : 3 | 8 : 2 5 : 9| 2 6 : 2 56 : 7 |
------------------------------------------------------------------------------------------
1 : 3 67 : 2 7 | 45 7 9: 2345 7 9: 2345 7 | 2 6 9: 8 : 3 6 |
3 78 : 5 : 2 78 |1 7 9:123 7 9: 6 | 4 : 2 7 9:1 3 |
9: 3 67 : 4 |1 7 :123 7 : 8 | 5 : 2 67 :1 3 6 |
------------------------------------------------------------------------------------------
...............................................
Tässähän aikaisemmin SUDOKU valitsi ruutuun (1,1) numeron 8 ja onnistui.
Jos nyt tähänastinen ratkaisu SUDOKU.M kopiodaan matriisiksi A ja
valitaan tuo toinen vaihtoehto (1,1)=5 esim. komennoilla
MAT A=SUDOKU.M / *A~Partial_Sudoku_solution_of_HS010406 9*9
MAT A(1,1)=5
niin jatkettaessa
SUDOKU A / GUESS=1
tulee ilmoitus "Mission Impossible!". Tehtävällä ei siis ole tässä muodossa ratkaisua.
Näin tapahtuu aina, jos tehtävä on mahdoton.
Kun taulukko on alunperin virheellinen, tulee heti virheilmoitus, joka on esim. muotoa
Error: (3,4)=(3,8)=7
eli numero 7 esiintyy ainakin kahdessa eri paikassa rivillä 3.
..............................................
Toinen tapa rajoittaa ratkaisun etenemistä on antaa STEPS-täsmennys.
Esim. STEPS=10 tuottaa vain ratkaisun 10 ensimmäistä askelta.
* * *
Survon editoriaalinen käyttöliittymä suosii Sudoku-tehtävien ratkaisijaa.
On helppo myös toimia käsin kopioimalla ja supistamalla pelitaulukkoa
toimituskentässä.
SUDOKU tuo tähän oman lisänsä, josta ratkaisija saattaa ottaa hyödykseen sen
verran kuin haluaa.
Ainakin alkeellisimmat vaiheet kannattanee jättää SUDOKUn tehtäväksi.
Seppo
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!