Peli uusiksi

[vastaus aiempaan viestiin]

Kiitoksia Kimmolle ja Reijolle kommenteista.

Kimmo kysyi, tekisinkö vastaavaa Kakurolle. Kakuro on hiukan ikävän
oloinen ohjelmoitavaksi ja niinpä päätin "keksiä" pelin, joka on
tavallaan jotain Sudokun ja Kakuron välimaastosta.
On erittäin todennäköistä, että peli tunnetaan ennestään,
sillä ainakin omasta mielestäni se vaikuttaa jännältä.

Tehtävänä on yksinkertaisesti täyttää m x n -taulukko luvuilla
1,2,...,m*n siten siten, että jokainen näistä luvuista esiintyy vain
kerran ja että rivi- ja sarakesummat täsmäävät reunoilla annettuihin
lukuihin.
Lisäksi taulukkoon on sijoitettu joitakin lukuja jo valmiiksi, jotta
ratkaiseminen ei olisi liian hankalaa eikä mahdollisia ratkaisuja olisi
liikaa.

Tässä esimerkkinä 3 x 4 -taulukko:

       *  6  *  *  30
       8  *  *  *  18
       *  *  3  *  30
      27 16 10 25

Siis esim. 1. rivin lukujen summa on 30 eli puuttuvien kolmen luvun
summa on 24.
Vastaavasti 2. sarakkeen summa on 16, joten puuttuvien kahden luvun
summa on 10.

Tämä lienee helppo tapaus ja siihen on ainakin kaksi ratkaisua.

Peli vaikeutuu taulukon suuretessa.
Esim. seuraava 5 x 5 -taulukko on jo varmaankin paljon hankalampi
täydentää:

         24  *  *  *  * 60
         19  *  * 11 13 88
          * 21  *  *  * 40
          *  * 14  6  * 70
          * 12  *  * 17 67
         64 84 56 36 85

Olen tehnyt pelille alustavan, yleisen ratkaisuohjelman, joka keksii
tälle 5 x 5 -taulukolle vain yhden ratkaisun, mutta niitä saattaa olla
lukuisia, sillä ohjelma löytää edellä olevalle 3 x 4 -taulukollekin
vain yhden ratkaisun.

Mm. Survon editoriaalisesta ja kosketuslaskennasta on hyötyä
tällaisten tehtävien käsittelyssä.

Kertokaa, oletteko tavanneet tätä peliä jossain muualla.
Jään joka tapauksessa odottelemaan, kuka ensimmäisenä selvittää
tuon 5 x 5 -taulukon.

-Seppo

P.S. Muodollisesti kysymys on lineaarisen, diofanttisen yhtälöryhmän
ratkaisemisesta. Esim. tuossa 5 x 5 -taulukossa on 16 tuntematonta,
mutta yhtälöitä vain 10. Ratkaisu täsmentyy sitä kautta, että tiedetään
sen olevan 1,2,3,4,5,7,8,9,10,15,16,18,20,22,23,25, mutta
missä järjestyksessä?  Koska fact(16)=20922789888000 siis noin 2*10^13,
on täysin toivotonta käydä mekaanisesti kaikkia vaihtoehtoja läpi.

• Re: Peli uusiksi (Seppo Mustonen 6.4.2006 15:13)

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!