Seppo Mustonen
Matematiikan ja tilastotieteen laitos
Helsingin yliopisto

Vastine Jukka Tuomelan kirjoitukseen Survo-ristikot ja polynomit (Arkhimedes 2/2007)

Haluamatta käyttää liikaa palstatilaa, toivon asiasta kiinnostuneiden lukijoiden lukevan tämän vastineen suoraan verkosta osoitteesta
www.survo.fi/papers/arkhimedes2007.html
jolloin jatkosssa mainitut linkit ovat välittömästi aktivoitavissa ja luettavissa.

On ilahduttavaa, että Tuomela on pyrkinyt löytämään varsin omintakeisen tavan käsitellä Survo-ristikon ratkaisemista. On aihetta arvioida 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 vie 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.

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ä paitsi 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:
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
www.survo.fi/papers/ristikot.pdf (tehtävä 11 sivulla 24)
on hankala suorilla päättelyillä ratkaistavaksi. Tällaisen ratkaisun on kuitenkin esittänyt mm. Janni Ingman
www.survo.fi/ristikot/ratkaisuja.html#65_2007
ja mikäli ratkaisussa ei edellytetä, että samalla osoitetaan se ainoaksi mahdolliseksi, löytyy ns. vaihtomenetelmään perustuva, todella lyhyt päättely
www.survo.fi/flash/f_sp_swap.html
Vaihtomenetelmästä on olemassa kuvaus
www.survo.fi/ristikot/vaihtom.html
Kannattaa myös yleensäkin tutustua esim. Survon ristikkosivuilla
www.survo.fi/ristikot
esitettyihin ratkaisuesimerkkeihin, ja havaita, miten erilaisilla tavoilla tehtäviä käsitellään. Ratkaisutapojen erilaisuus viittaa selvästi siihen, ettei mitään tasaisesti parasta menettelyä voi olla olemassakaan.

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
www.survo.fi/java/pika5x5.html

Survo-ristikkoihin liittyy myös erilaisia matemaattisesti haastavia ongelmia, mm. olennaisesti erilaisten, avoimien, yksikäsitteisesti ratkeavien mxn-ristikoiden etsintä ja niiden 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ää.




P.S.
Tämän vastineen kirjoittamisen jälkeen olen laatinut avoimien Survo-ristikoiden ratkaisemiseen aikaisempia huomattavasti nopeamman ohjelman.
Se mm. löytää kannettavallani 37 sekunnissa kaikki avoimet, yksikäsitteisesti ratkeavat 4x4-ristikot, joita on S(4,4)=5327 kpl.
Tästä aiheesta olen kirjoittanut Survo-keskusteluun seuraavat viestit:
Uusi Survo-ristikoiden ratkaisuohjelma
Lisää tästä ohjelmasta
Survo-ristikot: palkintotehtävä ym.