[viesti Survo-keskustelupalstalla (2001-2013)]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 29.8.2007 15:52 |
Survo-ristikoita on nyt ollut tarjolla hieman yli vuoden verran.
Jo näin lyhyenä aikana on esitetty erilaisia menettelyjä
ja ovelia ideoita, miten näitä ristikoita selvitetään
suorilla päättelyillä ilman varsinaisia ratkaisuohjelmia.
Silti on kiinnostavaa pohdiskella myös erilaisia tietokoneen
avulla tapahtuvia ratkaisukeinoja. Tähän mennessä on
syntynyt muutamia, hyvin erityyppisiä ratkaisuohjelmia.
Heti alussa (huhtikuussa 2006) oli tarpeen laatia sellainen
ohjelma, jonka avulla voin riittävällä varmuudella tarkistaa,
että tehtävä ratkeaa yksikäsitteisesti. Päädyin silloin
nopeasti puolittain satunnaistettuun menettelyyn, jonka periaatteen
olen kuvannut kirjoituksessani
http://www.survo.fi/papers/ristikot.pdf
sivulla 11.
Se on edelleenkin tärkein apuvälineeni Survo-ristikkotehtäviä
laatiessani ja riittää varsin hyvin kaikkiin niihin tapauksiin,
jotka on tarkoitettu selvitettäväksi ilman apuvälineitä.
On kuitenkin luonnollista, että paitsi itselleni, myös eräille muille
Survo-ristikoista kiinnostuille on syntynyt halu löytää tätä
alkuperäistä ratkaisumenetelmää tehokkaampia ratkaisualgoritmeja.
Pian nimittäin ilmeni, että alkuperäinen ohjelmani olisi vienyt
kohtuuttomasti aikaa esim. sen seikan selvittämiseen, mitä on S(4,4)
eli paljonko löytyy aidosti erilaisia, avoimia, yksikäsitteisesti
ratkeavia 4x4-ristikoita.
Seminaarissani toukokuussa 2006 vieraillut kombinatoriikan
asiantuntija Petteri Kaski pystyi (muuntamalla tehtävän ns.
täydellisen peitteen ongelmaksi ja käyttäen omia erikoisohjelmiaan)
selvittämään yhden illan aikana, että S(4,4) on 5327. Hänen
ratkaisutapansa oli tässä tapauksessa ainakin 100 kertaa tehokkaampi
omaani verrattuna.
Oli kuitenkin jo silloin ilmeistä, että tätäkin nopeampia
ratkaisumenettelyjä on mahdollista laatia osaamalla käyttää hyväksi
Survo-ristikolle ominaisia piirteitä.
Mielessäni on muhinut jo vuoden verran, alkaen tehtävään 3/2006
(2x10-ristikko) antamastani raa'an suoraviivaisesta ratkaisusta
http://www.survo.fi/ristikot/ratkaisuja.html#3_2006
ajatus yleistää tämä menettely ja saattaa se ratkaisuohjelman
muotoon. Vasta kuluneen kesän aikana olen ryhtynyt tuumasta toimeen
ja saanut ohjelman toimimaan viime päivinä. Olen iloisesti yllättynyt,
sillä mm. tuon S(4,4)-ongelman uusi ohjelma näyttää selvittävän yli 50
kertaa nopeammin kuin mikään aikaisempi ohjelma.
S(4,4)-ongelma ratkeaa Kasken ohjelmalla omalla koneellani hieman
alle 4 tunnissa, mutta uusi ohjelmani kuittaa sen 159 sekunnissa.
Sain aikoinaan alkuperäisellä ohjelmallani selville (noin parissa
tunnissa), että S(3,4) on 583. Uusi ohjelmani tuottaa saman tuloksen
sekunnin neljäsosassa.
Uuden ohjelman SP_SOL periaate on varsin yksinkertainen, mutta tuloksen
laatu riippuu olennaisesti siitä, miten hyvin ratkaisun eri vaiheet
toteutetaan.
Ohjelman pääidean kuvaan tässä vain seuraavalla esimerkillä:
Tarkastelen tehtävää 65/2007
http://www.survo.fi/ristikot/index.html#110607
Laskennan kannalta on hyvä asettaa summat nousevaan
suuruusjärjestykseen eli ratkaistavana on tehtävä
A B C D
1 * * * * 17
2 * * * * 32
3 * * * * 36
4 * * * * 51
17 26 42 51
jolloin sen ainoa ratkaisu on
A B C D
1 2 1 5 9 17
2 3 6 10 13 32
3 4 7 11 14 36
4 8 12 16 15 51
17 26 42 51
Aluksi ei kiinnitetä lainkaan huomiota sarakesummiin
vaan pyritään tarkastelemaan kaikkia sellaisia
alustavia ratkaisuja, jotka antavat oikeat rivisummat
17,32,36,51.
Aloitetaan ensimmäisestä rivistä, jolle löytyvät mm.
Survon COMB-ohjelmalla seuraavat 11 vaihtoehtoa
(lukujen järjestystä vaille):
COMB P,CUR+1 / P=PARTITIONS,17,4 DISTINCT=1 MAX=16
Partitions 4 of 17: N[P]=11
1 2 3 11
1 2 4 10
1 2 5 9 !
1 2 6 8
1 3 4 9
1 3 5 8
1 3 6 7
1 4 5 7
2 3 4 8
2 3 5 7
2 4 5 6
Näistä jokainen tulee vuorollaan ottaa käsittelyyn,
mutta oikaisen tässä valitsemalla suoraan ainoan,
joka tuottaa tässä tehtävässä ratkaisun eli
kolmantena olevan (!) 1 2 5 9.
..................................
Seuraavaksi etsitään kaikki vaihtoehdot riville 2,
jolle summaksi tulisi saada 32 ehdolla, ettei
siinä saa olla riville 1 valittuja lukuja 1,2,5,9.
Vaihtoehdot syntyvät seuraavasti:
OFF=1,2,5,9
COMB P,CUR+1 / P=PARTITIONS,32,4 DISTINCT=1 MAX=16
Partitions 4 of 32: N[P]=16
3 4 10 15
3 4 11 14
3 4 12 13
3 6 7 16
3 6 8 15
3 6 10 13 !
3 6 11 12
3 7 8 14
3 7 10 12
3 8 10 11
4 6 7 15
4 6 8 14
4 6 10 12
4 7 8 13
4 7 10 11
6 7 8 11
Jälleen jokainen näistä tulisi tutkia erikseen,
mutta valitsen taas ainoan oikean eli
kuudentena olevan (!) 3 6 10 13.
..................................
Vastaavalla tavalla saadaan ottaen huomioon
kahden ensimmäisen rivin valinnat kolmanneksi riviksi
OFF=1,2,5,9,3,6,10,13
COMB P,CUR+1 / P=PARTITIONS,36,4 DISTINCT=1 MAX=16
Partitions 4 of 36: N[P]=1
4 7 11 14
eli tässä tapauksessa sattuu olemaan vain yksi mahdollisuus.
..................................
Viimeiselle riville tulevat suoraan pelkät puuttuvat luvut
eli tässä tapauksessa
8 12 15 16
Yhtenä ehdotuksena saadaan siis
A B C D
1 1 2 5 9 17
2 3 6 10 13 32
3 4 7 11 14 36
4 8 12 15 16 51
16 27 41 52 lasketut summat
17 26 42 51 oikeat summat
-1 1 -1 1 virhe
Ratkaisujen on löydyttävä tekemällä kussakin ehdokkaassa
pelkästään rivien sisäisiä lukujen paikanvaihtoja.
Nyt on välittömästi pääteltävissä, että vaihdoilla
(1,2),(15,16) ja vain näillä päästään ratkaisuun.
Jotta ratkaisu, ilman edellä tehtyjä "oikaisuja", syntyy
ja osoitetaan yksikäsitteisksi, ratkaisuohjelman SP_SOL
on käytävä läpi vaiheittain kaikki vaihtoehdot.
Tällöin erilaisia alustavia ratkaisuja, jotka toteuttavat
rivisummat, löytyy 394 kappaletta, tuon oikean ohella esim.
A B C D
1 1 2 3 11 17
2 5 6 9 12 32
3 4 8 10 14 36
4 7 13 15 16 51
17 29 37 53
17 26 42 51
0 3 -5 2
Tässä tapauksessa ensimmäinen sarakesumma on oikea, mutta
toinen on auttamattomasti liian suuri, sillä sitä ei saada
vähenemään millään rivien sisäisillä lukujen vaihdoilla.
Näin tästä ehdokkaasta ei synny kelvollista ratkaisua.
Yhtä huonosti käy kaikille muillekin näistä 394 ehdokkaasta
tuota alussa mainittua lukuunottamatta.
Ohjelman SP_SOL toiminnassa vuorottelee kaksi rekursiivisesti toimivaa
algoritmia. Ensimmäinen etsii rivisummat toteuttavat ehdokkaat ja
toinen hakee kunkin ehdokkaan osalta rivien sisäisten vaihdoin kaikki
sarakesummat toteuttavat ratkaisut.
Kyse on kahdesta eri tavoin rajoitettuja kokonaislukujen osituksia
(restricted integer partitions) luettelevasta algoritmista. En ole
kirjallisuudesta löytänyt näihin tarkoituksiin mitään valmiita
ratkaisuja.
Vaikka SP_SOL on nopea ratkaisuohjelmaksi, se ei sisällä juuri mitään
sellaista "älykkyyttä tai oivallusta", joka on tyypillistä hyvälle
"inhimilliselle" ratkaisutavalle.
Ohjelmalla löydetään haluttaessa annetun avoimen Survo-ristikon
kaikki ratkaisut tai sitä voi käyttää kaikkien yksikäsitteisesti
ratkeavien, olennaisesti erilaisten, avoimien mxn-ristikoiden
luettelointiin ja lukumäärän laskemiseen.
Arvelisin, että SP_SOL saattaa selvittää "äärellisessä ajassa"
mitä on S(4,5), mutta S(5,5) taitaa olla senkin ulottumattomissa.
Olen juuri pannut hitaamman koneeni käsittelemään tapausta S(4,5)
sopivina kerta-annoksina ja karkean arvioni mukaan kokonaisaika tulee
olemaan noin 10 vuorokautta.
Verrattuna S(4,4):n laskemiseen (alle 3 minuutissa) tämä osoittaa,
kuinka rankasti tehtävä vaikeutuu ristikon koon kasvaessa.
Vielä epämääräisempi on tuntumani S(4,5):n suuruusluokasta.
Tämänhetkisen käsitykseni mukaan S(4,5) on noin 60000.
* * *
Totean lopuksi, mitä olen saanut tietooni muista tähän mennessä
kehitetyistä Survo-ristikkojen ratkaisuohjelmista.
Janne Mattila on blogissaan
http://blogs.msdn.com/jannemattila/archive/2007/01/07/
solving-small-puzzles-with-just-a-few-lines-of-code.aspx
esittänyt oman rekursiivisen ratkaisuohjelmansa.
Ohjelma on taidokkaasti suunniteltu mutta se lienee selvästi hitaampi
kuin SP_SOL, sillä (mikäli olen tulkinnut oikein) hän mainitsee
ristikon
A B C D E (vaikeusaste 8700)
1 * * * * * 21
2 * * * * * 42
3 * * * * * 64
4 * * * * * 83
21 37 42 49 61
ratkeavan omalla ohjelmallaan 2 sekunnissa. SP_SOL ratkaisee
sen 0.02 sekunnissa ja osoittaa samalla ratkaisun yksikäsitteisyyden.
Jukka Tuomelan Arkhimedes-lehdessä esittämä ratkaisutapa
(kts. kirjoitustani "Survo-ristikot ja polynomit" näillä palstoilla)
on periaatteessa mielenkiintoinen, mutta käytännössä se lienee hidas
ja syö liikaa muistia.
Valmennettessa hiljakkoin Suomen tietotekniikka-olympialaisjoukkuetta on
ainakin Otto Ebeling kirjoittanut ns. simuloituun jäähdytykseen
(simulated annealing) perustuvan ohjelman.
Omaa alkuperäistä ratkaisuohjelmaani voidaan pitää tämän menettelyn
alkeellisena erikoistapauksena ja uskoisin tuon ohjelman silloin
olevan omaani nopeampi. Se ei kuitenkaan käsitykseni mukaan voi yltää
nopeudessa läheskään uuden SP_SOL:in tasalle.
* * *
Tulen kertomaan lisää uudesta ohjelmastani kerättyäni enemmän tuloksia
ja tietoa sen toimintakyvystä. Toivon saavani kuulla mahdollisista
muista tehdyistä tai tekeillä olevista Survo-ristikkojen
ratkaisuohjelmista. Ainakin Joonas Kauppinen, Risto Nieminen ja
Kimmo Vehkalahti ovat ristikkoratkaisuissaan esittäneet keinoja, joita
ehkä saattaisi kehittää ohjelmalliseen muotoon.
Seppo Mustonen
| 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!