Survo-ristikot: palkintotehtävä ym.

[viesti Survo-keskustelupalstalla (2001-2013)]

Viime viikolla Survon ristikkosivuilla
http://www.survo.fi/ristikot 
olen antanut tavallista vaativamman palkintotehtävän, joka
ei ole tarkoitettu käsivaraisesti ratkaistavaksi vaan se
antaa haasteen ratkaisuohjelmien laatijoille.
Toivon, että tieto tästä tehtävästä leviäisi mahdollisimman
laajalle ja että se innostaisi ohjelmointia osaavia kehittämään
entistä tehokkaampia menettelyjä.

Vielä suurempi haaste on allaolevan taulukon täydentäminen.
Siinä ovat tällä hetkellä tietämäni S(m,n)-arvot.
Luku S(m,n) tarkoittaa  avoimien, olennaisesti erilaisten
ja yksikäsitteisesti ratkeavien mxn-ristikoiden lukumäärää.
Reijo Sund selvitti jo huhtikuussa 2006, että S(3,3)=38 ja
Petteri Kaski toukokuussa 2006, että S(4,4)=5327.
Itse saatoin siinä välissä laskea hitaalla, alkuperäisellä
ratkaisuohjelmallani luvun S(3,4)=583.
Nopeimmin näitä lukuja löytää tällä hetkellä uusi ohjelmani
SP_SOL, jolla tunnettujen S(m,n)-arvojen taulukko on
laajentunut seuraavaksi:

m/n       2      3      4      5      6      7      8      9
 2        1     18     62    278   1146   5706  28707 154587
 3       18     38    583   5337  55815
 4       62    583   5327
 5      278   5337
 6     1146  55815
 7     5706
 8    28707
 9   154587

Vaikka SP_SOL laskee luvun S(4,4)=5327 ja tallettaa samalla
tiedostoon kaikki nuo kiinnostavat ristikot 37 sekunnissa,
näyttää siltä, että luvun S(4,5) laskemiseen kuluisi aikaa yli
kuukausi! (Simulointikokeilla olen päätynyt siihen, että
S(4,5) jää suurella todennäköisyydellä alle 300000.)
Tarvitaan siten todella vielä lisää oivalluksia, jotta voisi edes
kuvitella esim. luvun S(5,5) laskemista.

Toivoisin myös, että esim. arvo S(3,6)=55815 saisi vahvistuksen
jollain toisella, mieluiten täysin erilaisella periaatteella
toimivalla ohjelmalla kuin SP_SOL, josta olen kertonut viime
viikkoina. Olen kyllä laskenut tuon arvon erikseen 3x6- ja
6x3-ristikoille ja saanut saman tuloksen, mikä on lisännyt
luottamusta ohjelman toimivuuteen. Käytännössä nämä tavat
nimittäin eroavat melkoisesti, sillä 3x6-tapaus vie aikaa noin
kolme kertaa enemmän kuin 6x3. Tämänkaltaisen eron ymmärtää, jos
perehtyy käyttämääni ratkaisutapaan, sillä rivisummavaatimukset
täyttäviä ratkaisuehdokkaita syntyy 6x3-tapauksessa vähemmän kuin
3x6-tapauksessa.

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!