Survo-ristikkojen ratkaisuohjelmista

[viesti Survo-keskustelupalstalla (2001-2013)]

Keväällä 2011 tuli kuluneeksi viisi vuotta siitä, kun sain ajatuksen
Survo-ristikoista. Oli tavallaan yllätys, ettei tällaista tehtävätyyppiä
näytä kukaan aikaisemmin tutkineen ja esittäneen yleisesti, vaikka
yksittäisiä esimerkkejä vastaavista tehtävistä ilmaantuikin.

On ollut ilahduttavaa havaita, että aika monet ovat kiinnostuneet
laatimaan Survo-ristikoille ratkaisuohjelmia.

Ensimmäisen tein itse heti alussa varmistuakseni siitä, että
esittämilläni ristikoilla on kullakin vain yksi ratkaisu.
Ohjelman periaate on kuvattu kirjoituksessani
Survo-ristikoista (2006)
http://www.survo.fi/papers/ristikot.pdf 
(englanninkielinen versio: On certain cross sum puzzles
www.survo.fi/papers/puzzles.pdf).
Tässä ohjelmassa luvut sijoitettiin ristikkoon aluksi umpimähkäään
ja niiden paikkoja vaihdettiin kaksittain niin, että lasketut summat
tulivat mahdollisimman lähelle annettuja reunasummia. Kun sitten
(useimmiten) jouduttiin tilanteeseen, jossa noilla vaihdoilla ei enää
päästy lähemmäksi oikeita summia, tehtiin "mutaatio", jossa kaksi
lukua vaihdettiin umpimähkään summista piittaamatta ja jatkettiin
sen jälkeen uudelleen systemaattisin vaihdoin. Tämä menettely johtaa
(lähes miljoonakertaisen kokemukseni mukaan) aina lopulta ratkaisuun,
jossa siis lasketut ja annetut summat täsmäävät.
Käytän tätä Survo-moduliksi tekemääni ohjelmaa edelleen ristikon
laadintaan ja ratkaisun yksikäsitteisyyden toteamiseen antamalla
ohjelman toistaa ratkaisun etsimisen noin 1000 kertaa.
Tarvittavien mutaatioiden lukumäärän keskiarvo toimii karkeana mittana
ristikon vaikeusasteelle. Tämä mitta ei aina anna oikeaa käsitystä
ratkaisemisen työläydestä. Se ei mm. ota huomioon ovelia oikoteitä,
joita taitavat ratkaisijat saattavat havaita.
Mitta kuvaa vaikeusastetta ehkä parhaiten silloin, kun vaaditaan, että
ratkaisija osoittaa myös ratkaisun yksikäsitteisyyden.

Avoimet ristikot
================
Jo alkuvaiheessa Reijo Sund havaitsi, että esiintyy ristikkoja,
jotka ratkeavat yksikäsitteisesti, vaikka reunasummien lisäksi
ei yhtään ristikon sisällä olevaa lukua ole annettu.
Olkoon tällaisten avointen Survo-ristikoiden lukumäärä m x n-tapauksessa
S(m,n). Reijo pystyi Survon avulla (käymällä systemaattisesti läpi
kaikki vaihtoehdot) osoittamaan, että S(3,3)=38.
Itse saatoin tämän jälkeen ensimmäisen ratkaisuohjelmani avulla
todeta, että S(3,4)=583. Tämä olisi ollut erittäin työlästä
Reijon tyyliin, sillä vaihtoehtojen lukumäärä olisi ollut
12!=479001600. Pystyin rajoittamaan hakua siten, että lähtökohtana
olivat kaikki mahdolliset reunasummien jakaumat, joita on vain
66432. Tapaus S(4,4) olisi kuitenkin ollut ylivoimainen alkuperäiselle
ratkaisuohjelmalleni.
Seminaarissamme vieraillut kombinatoristen algoritmien erikoistuntija
Petteri Kaski sai omilla ohjelmillaan tulokseksi S(4,4) = 5327.
Hän mallinsi tehtävän ns. täsmällisen peitteen ongelmaksi (exact
cover problem) reunasummien antamin lisärajoittein.

Uusi ratkaisuohjelma
====================
Kesällä 2007 rakensin uuden ratkaisuohjelman, joka on moninkertaisesti
nopeampi kuin Kasken ohjelma ja sen avulla olen saanut mm.
tuloksen S(4,5)=257773. Tapaus S(5,5) odottaa vielä vastausta, sillä
se ei ole kohtuullisessa ajassa tavoitettavissa uudella ratkaisu-
ohjelmallanikaan. Tämän ohjelman yleisen periaatteen olen kuvannut
kirjoituksessani "Enumeration of Survo puzzles"
http://www.survo.fi/papers/enum_survo_puzzles.pdf 
ja laatinut siitä tähän Survo-keskusteluun viestin:
http://www.survo.fi/arkisto/001175.html 

Håkan Kjellerstrand
===================
Ruotsalainen Håkan Kjellerstrand (jota en tunne henkilökohtaisesti)
on ohjelmoinut suuren määrän kokonaislukuoptimointiin kuuluvia
ongelmia useilla eri ohjelmointikielillä ja erilaisissa ympäristöissä.
Survo-ristikko (Survo puzzle) näyttää olevan eräs hänen suosikeistaan,
sillä (mainittuaan ohjelmoineensa 242 eri ongelmaa vähintään kahdessa
eri järjestelmässä) hän toteaa lopuksi (blogissaan tammikuussa 2011)
http://www.hakank.org/constraint_programming_blog/2011/01/some_new_answer_set_programming_programs_1.html 
"4 problems has been implemented in all 12 systems:(Survo Puzzle,
Seseman, Quasigroup Completion, and Coins Grid)."
Tässä on joitakin linkkejä Håkanin Survo-ristikkojen ratkaisuohjelmiin:
http://www.hakank.org/minizinc/survo_puzzle.mzn 
http://www.hakank.org/choco/SurvoPuzzle.java 
http://www.hakank.org/JaCoP/SurvoPuzzle.java 
http://www.hakank.org/gecode_r/survo_puzzle.rb 
http://www.hakank.org/comet/survo_puzzle.co 
http://www.hakank.org/gecode/survo_puzzle.cpp 
http://www.hakank.org/eclipse/survo_puzzle.ecl 

Timo Poranen
============
Tampereen yliopiston tietojenkäsittelytieteen lehtori Timo Poranen
valmensi Suomen edustusjoukkuetta "Tietojenkäsittelyn olympialaisiin"
kesällä 2007. Tällöin laadittiin harjoitustyönä ratkaisuohjelma, joka
perustui "simulated annealing"-menetelmään. Porasen aloitteesta
Suomen yliopistojen Tietojenkäsittelytieteen yhteisvalintakokeessa
22.5.2009 oli (yhtenä tehtävänä kolmesta) erilaisia Survo-ristikkoihin
liittyviä kysymyksiä:
http://www.tkt-yhteisvalinta.fi/valintakoe2009/tkt09_Tehtava3.pdf 

Jukka Tuomela
=============
Itä-Suomen yliopiston (Joensuu) matematiikan professori Jukka Tuomela
kirjoitti vuonna 2007 Arkhimedes-lehteen artikkelin "Survo-ristikot
ja polynomit", jossa hän esittelee oman ratkaisumenetelmänsä.
Se ei kuitenkaan vaikuta kovin tehokkaalta, koska jo 4x4-ristikkojen
ratkaiseminen ei välttämättä onnistu. Eräät Tuomelan esittämät
omituiset väitteet Survo-ristikkojen ominaisuuksista antoivat
minulle aiheen kirjoittaa vastine
http://www.survo.fi/arkisto/001157.html 
joka julkaistiin Arkhimedeksen seuraavassa numerossa.

Kimmo Vehkalahti
================
Kimmo on heti alusta lähtien ratkaissut taitavasti, osittain Survon
toimintojen avulla, hankalia ristikoita, mm. toistaiseksi ainoana
"petomaisen" 6x6-ristikon (Tehtävä 12 sivulla 25 alkuperäisessä
kirjoituksessani 2006).
Kokemustensa pohjalta hän on vähitellen kehitellyt hyvin Survo-
pitoisen, erityisesti matriisitulkkia ja COMB-operaatiota hyödyntävän
ratkaisumenettelyn. Tästä häneltä on äskettäin ilmestynyt selostus
"Survo-ristikon ratkaiseminen matriiseilla"
http://www.survo.fi/ristikot/Survo-ristikko_matriiseilla.pdf 
Kimmon ratkaisutapa ei varsinaisiin ratkaisuohjelmiin verrattuna
ole tehokas mutta survoilijoiden kannalta erittäin kiinnostava
avoimuudessaan.

                     - - -

Muita Survo-ristikon ratkaisuohjelmia ovat tehneet ainakin Jarno Tuimala
ja Janne Mattila.

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!