Survo-ristikot ja polynomit

[viesti Survo-keskustelupalstalla (2001-2013)]

Fysiikan ja matematiikan aikakauslehden "Arkhimedes" uusimmassa
numerossa on Joensuun yliopiston matematiikan professorin Jukka Tuomelan
viiden sivun mittainen kirjoitus yllämainitulla otsikolla. Lehti on
ilmestynyt toukokuun alussa, mutta sain sen nähdäkseni vasta noin viikko
sitten.

Aion nyt kommentoida tuota juttua, mutta toivon, että tutustutte
siihen ainakin loppupäätelmien osalta osoitteessa
http://www.survo.fi/ristikot/Tuomela2007.pdf 
ennen huomautusteni lukemista.
(Olen saanut luvan sekä lehden toimitussihteeriltä että kirjoittajalta
siirtää kirjoituksen Survon sivuille, jotta mahdollisimman moni voi
sen nähdä. Arkhimedes ei valitettavasti ainakaan toistaiseksi ilmesty
verkkoversiona.)

Sitten noita kommentteja:
On ilahduttavaa, että Tuomela on pyrkinyt löytämään varsin omintakeisen
tavan käsitellä Survo-ristikon ratkaisemista. En lähde tässä kuvaamaan
Tuomelan lähestymistyyliä (koska se selviää lukemalla kirjoituksen),
vaan pyrin arvioimaan sen merkitystä suhteessa niihin menettelyihin,
jotka tunnen entuudestaan ja erityisesti omaan ratkaisuohjelmaani.

Tällöin huomio kiinnittyy lähinnä artikkelin viimeiselle sivulle,
jossa Tuomela toteaa, että hän pystyy kannettavallaan varsin helposti
ratkaisemaan erään avoimen 3x4-ristikon, mutta vastaavassa
4x4-tilanteessa hänen kannettavansa hyytyi muistin vähyyden takia.
Tuomelan menettely johtaa siis laskennallisiin vaikeuksiin hankalissa
Survo-ristikoissa, mikä teknisesti johtuu ns. Gröbner-kantojen
ripeästä kasvusta. On tietenkin mahdollista, että Tuomelan ratkaisutapaa
saatetaan jatkossa kehittää tehokkaampaan suuntaan, mutta siitä ei ole
mitään näyttöä hänen kirjoituksessaan.
Mainittakoon, että oma ratkaisuohjelmani selvittää omalla
kannettavallani saman avoimen 4x4-ristikon noin 0.1 sekunnissa.

Ehkä hiukan turhautuneena, kuvittelisin, Tuomela päätyy juttunsa
loppupuolella toteamaan mm.:
"Kuitenkin jos jonkin tehtävän matemaattinen rakenne on liian selkeä,
niin tehtävä väistämättä menettää mielenkiintoaan arvoituksena."
ja aivan lopussa:
"Survo-ristikoilla on (SM:n lisäys: verrattuna kolmen lineaarisen
yhtälön ryhmän ratkaisuun) samanlainen vika: kaikkien tehtävien rakenne
on sama, laskennan vaativuus vain kasvaa muuttujien määrän kasvaessa."

Mielestäni tällä asenteella mikä tahansa hyvin määritelty ongelmaperhe,
siis esim. sudokut, kakurot, jopa shakkitehtävät, voidaan altistaa
vastaavalle kritiikille. Vaikka näille ongelmille on kehitetty nopeita
ratkaisualgoritmeja, sellainen tieto ei mitenkään vähennä niiden
suosiota eikä niiden "mielenkiintoa arvoituksena".

Esim. Survo-ristikkojen ratkaisemisessa varsinainen viehätys on siinä,
että vaikka valmiilla algoritmilla tehtävät saa suoritettua välittömästi
raakaa laskentavoimaa käyttäen, taitava ratkaisija saattaa löytää
oikoteitä ja selvitä tehtävästä yllättävän vähällä vaivalla. Se tuottaa
älyllistä iloa, josta on lupa nauttia.

Sitäpaisi Tuomelan viimeinen toteamus (laskennan vaativuuden kasvusta)
ei pidä Survo-ristikoiden osalta välttämättä paikkaansa. Esim. seuraava
5x4-ristikko (palkintotehtävä 56/2007, jonka ratkaisi 8 henkilöä)

   A  B  C  D
1  *  *  *  *  48
2  *  *  *  *  22
3  *  *  *  *  56
4  *  *  *  *  40
5  *  *  *  *  44
  57 26 90 37

näyttää varsin vaikealta, mutta se ratkeaa helposti suorin päättelyin:
http://www.survo.fi/ristikot/ratkaisuja.html#56_2007 

Sitä vastoin Tuomelan turhaan yrittämä 4x4-tapaus

   A  B  C  D
1  *  *  *  *  51
2  *  *  *  *  36
3  *  *  *  *  32
4  *  *  *  *  17
  51 42 26 17

jonka olen esittänyt ensimmäisessä Survo-ristikoita kuvaavassa
kirjoituksessani
http://www.survo.fi/papers/ristikot.pdf 
(tehtävä 11 sivulla 24)
on ilmeisesti varsin hankala suorilla päättelyillä ratkaistavaksi,
vaikka se ei tuota mitään ongelmia esim. omalle ratkaisuohjelmalleni.
Tietääkseni vain Kimmo Vehkalahti on selvittänyt tehtävän
"käsipelillä" käyttämällä Survo-ohjelmistoa monipuolisesti ratkaisunsa
tukena. Vehkalahden ratkaisu on katsottavissa Flash-demona osoitteessa
http://www.survo.fi/flash/f_puzz4x4.html 

Kannattaa tutustua esim. Survon ristikkosivuilla
http://www.survo.fi/ristikot 
esitettyihin ratkaisuesimerkkeihin, ja havaita, miten erilaisilla
tavoilla tehtäviä käsitellään.

Survo-ristikot helpoimmissa muodoissaan, joissa ratkaiseminen
edellyttää vain yhteen- ja vähennyslaskutaitoa sekä yksinkertaista
loogista päättelykykyä, tarjoavat esim. koululaisille hyvää
harjoittelumateriaalia.
Aivan oman lisämausteensa antavat Survo-ristikkojen pikapelimuodot,
joista vaativin löytyy Java-sovelmana osoitteesta
http://www.survo.fi/java/pika5x5.html 

Survo-ristikkoihin liittyy myös erilaisia matemaattisesti haastavia
ongelmia, mm. olennaisesti erilaisten, avoimien, yksikäsitteisesti
ratkeavien mxn-ristikoiden lukumäärän selvittäminen. Neliömäisissä
tapauksissa (siis kun m=n) tulos tunnetaan toistaiseksi vain arvoilla
n=2,3,4.

Kyseessä on siis paljon monitasoisempi tutkimus- ja harrastuskohde
kuin mitä Tuomelan kirjoitus antaa ymmärtää.

- Seppo Mustonen

Luettelo keskustelunaiheista

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!