Tehtävä: Ratsun reitti tarkoittaa sellaista reittiä ruudukossa, jossa ratsu aloittaa jostain ruudusta, päätyy toiseen ruutuun ja käy reitin aikana kaikissa muissa ruuduissa tarkalleen kerran. Ratsu liikkuu samaan tapaan kuin shakissa. Tässä on yksi ratsun reitti tapauksessa 5 x 5:
1 4 11 16 25 12 17 2 5 10 3 20 7 24 15 18 13 22 9 6 21 8 19 14 23
Tehtävänä on laskea ratsun reittien yhteismäärä, kun ruudukon koko on n x n.
Kuinka suurilla n:n arvoilla pystyt laskemaan ratsun reittien yhteismäärän? Kerro tässä keskustelussa tuloksistasi ja ohjelmistasi!
Tarkoitatko tarkkaa arvoa vai asymtoottista funktiota n:n suhteen? Tarkka arvo oli saavuttamatta ainakin tapauksessa n=8 vielä 26.1.2011 mikäli keskustelupalstaa on uskominen.
"Ratsun pisin leikkaamaton reitti"- probleema on muuten paljon hauskempi (IMHO):
http://en.wikipedia.org/wiki/
Ohjelman tekeminenkin on haastavampaa, kun brute-forcessa pitää löytää nopea tapa tarkistaa leikkaamattomuus ja myös heuristinen versio on haastavampi.
Lisäksi kynällä ja paperilla voi tuurilla ja taidolla myös löytää pisimmän reitin koska yksikin reitti riittää (vs. tuhannet biljardit tuossa "kautta kaikkien ruutujen"- hommelissa).
Hmm... voisi olla hauska "piirustelu"-kilpailu jossain matikkakerhossa tms.
Jaska kirjoitti:
Tarkoitatko tarkkaa arvoa vai asymtoottista funktiota n:n suhteen?
Tarkoitan tarkkaa arvoa. Olen saanut itse laskettua tapaukseen 6 x 6 asti, mutta mikään ei estä yrittämästä pidemmälle.
JaskaP kirjoitti:
"Ratsun pisin leikkaamaton reitti"- probleema on muuten paljon hauskempi (IMHO):
Tuo on myös hauska tehtävä, täytyy tutustua jossain välissä. :)
Aihe on jo aika vanha, joten et voi enää vastata siihen.