Kirjastossa satuin lukemaan Tiede-lehteä ja huomasin siinä mielenkiintoisen uutisen uudesta löytyneestä taikakuutiosta (tämä tosin oli oikeasti tapahtunut jo puoli vuotta sitten). Taikaneliö on neliönmuotoinen ruudukko, jonka ruutuihin on sijoitettu numerot yhdestä eteenpäin. Erikoista on se, että kaikkien pysty-, vaaka- ja vinorivien summa on sama. Taikakuutio taas on sama juttu kolmiulotteisena: summa on sama, vaikka numerot lukisi missä suunnassa tahansa.
Äskettäin löytyneen kuution sivunpituus on 5, ja se on pienin mahdollinen taikakuutio. Kuution olemassaolo oli kiehtonut matemaatikkoja 150 vuoden ajan, suurempia kuutiota tunnettiin ennestäänkin. Kuution löysivät saksalainen Walter Trump ja ranskalainen Christian Boyer, ja laskemiseen kului viideltä tietokoneelta monta viikkoa.
Asiaan liittyviä linkkejä:
http://www.tiede.fi/keskustelut/keskustelu.asp?
http://www.zeit.de/2003/50/N-Mathew_9frfel
http://mathworld.wolfram.com/news/2003-11-18/magiccube/
http://www.multimagie.com/English/Perfectcubes.
Rupesin myös miettimään, kuinka taikaneliöitä tai -kuutioita kannattaisi etsiä tietokoneella. Johdin ensin kaavan, jolla yhden rivin numeroiden vaaditun summan voi laskea:
s = (p ^ (u + 1) + p) / 2, jossa p = sivunpituus ja u = ulottuvuudet
Esim. 4x4-neliön summa on siis (4 ^ (2 + 1) + 4) / 2 = 34 ja 5x5x5-kuution summa on (5 ^ (3 + 1) + 5) / 2 = 315.
Tein sitten yksinkertaisen ohjelman, joka muodostaa kaikki mahdolliset neliöt ja näyttää ne, joiden numeroiden summat ovat oikeat. 3x3-neliöllä ohjelma toimi ihan hyvin, laskeminen kesti kymmenisen sekuntia. Muodostettavien yhdistelmien määrä kuitenkin kasvaa aivan liian nopeasti. 3x3-neliöllä niitä on 9! eli 362880, 4x4-neliöllä 16! eli 20922789888000 ja esim. 5x5x5-kuutiolla 125! eli hirveän paljon. Jo kaikkien 4x4-neliöiden laskemiseen tällä tavalla kuluisi aikaa 10 s * (16! / 9!) eli yli 1579660 vuotta!
Tarvitaan siis paljon parempi algoritmi. Eräs helppo parannus liittyy siihen, että kun tarpeeksi moni numero on tiedossa, muut voidaan laskea niiden perusteella. Esim. 3x3-neliössä täytyy laskea vain kolme numeroa, jotta muut voidaan päätellä. 4x4-neliössä vastaava luku näyttäisi olevan kahdeksan.
Muita ohjelmia en kuitenkaan ole vielä tehnyt. Olisikin kiva kuulla, jos joku muukin on koettanut tehdä tällaisia ohjelmia, millä algoritmeilla ja millä menestyksellä?
Mielenkiintoista.. Pitää jossain vaiheessa lukea ihan ajan kanssa.
No joo voisihan sitä lukea jos jaksaa...
Aihe rupesi kiinnostamaan.
Kertoisitko, miten johdit kyseiset kaavat?
Edit: Tuli tässä mieleen, että ongelman ratkaisua voisi lähestyä näin:
esim 3x3 neliö(rivin arvo 15):
taulukoidaan kaikki luku triot luvuista jotka ovat 0 < x <= 9(3*3), jotka muodostavat luvun 15.
Sitten sovitetaan ne yhteen, niin kuin rsitisanaa tehdessä.
On kyllä mielenkiintoinen aihe. Voisin yrittää väsätä jonkinmoisen algoritmin ainakin tuolle neliölle. Kuutiosta en sitten vielä tiedä. Ja muuten, kai matikassa voi laskea myös neliulotteisesti, vaikkei sellaista muotoa pystykään ajattelmaan, koska sellaista ei voi olla.
hunajavohveli kirjoitti:
... kai matikassa voi laskea myös neliulotteisesti, vaikkei sellaista muotoa pystykään ajattelmaan, koska sellaista ei voi olla.
Monimutkaista =S
peki kirjoitti:
Kertoisitko, miten johdit kyseiset kaavat?
Numeroiden määrä (ja suurin numero) on p ^ u. Numeroiden summa voidaan sen vuoksi laskea lausekkeella ((p ^ u) * (p ^ u + 1)) / 2. Erillisten rivien määrä (kaikki numerot kuuluvat yhteen mutta vain yhteen riviin) taas on p ^ (u - 1). Tästä saadaan lauseke, jota voidaan sieventää: ((p ^ u) * (p ^ u + 1)) / (2 * p ^ (u - 1)) = (p * (p ^ u + 1)) / 2 = (p ^ (u + 1) + p) / 2
Kertoma tulee tietysti siitä, että esim. 3x3-neliössä ensimmäinen numero voidaan laittaa yhdeksään paikkaan, toinen kahdeksaan, kolmas seitsemään jne., ja viimeinen sitten vain yhteen paikkaan. Näin saadaan yhdistelmien määrä.
peki kirjoitti:
taulukoidaan kaikki luku triot luvuista jotka ovat 0 < x <= 9(3*3), jotka muodostavat luvun 15.
Sitten sovitetaan ne yhteen, niin kuin rsitisanaa tehdessä.
Kuulostaa ihan hyvältä, kokeiletko tehdä ohjelmaa tähän perustuen?
Voisin kokeilla.
Luku triojen muodostaminen on helppoa, mutta se triojen yhdistäminen saattaa tuottaa hankaluuksia.
Enpä tuota osannut tehdä.
Olisi pitänyt koodata tekoäly, joka yhdistelee trioja älykkäästi.
Ei onnistunut.
Edit: Myös triojen muodostamisessa on ongelmia.
tässä koodi:
Dim i, j, a, b As Integer
Dim index As Integer
Dim olemassajo As Boolean = False
Dim triot(900, 2) As Integer
For i = 1 To 9
For j = 1 To 9
For a = 1 To 9
If i + j + a = 15 Then
If i <> j And i <> a And j <> i And j <> a Then
' Jos trio jo olemassa(luvut eri järjestyksessä)
For b = 0 To index
If triot(b, 0) = i Or triot(b, 0) = j Or triot(b, 0) = a Then
If triot(b, 1) = i Or triot(b, 1) = j Or triot(b, 1) = a Then
If triot(b, 2) = i Or triot(b, 2) = j Or triot(b, 2) = a Then
olemassajo = True
End If
End If
End If
Next
If olemassajo = False Then
triot(index, 0) = i
triot(index, 1) = j
triot(index, 2) = a
index += 1
End If
olemassajo = False
End If
End If
Next
Next
NextTuossa on joku käsittämätön ongelma.
Yhdistelmien muodostamisen tekisin ainakin itse rekursiivisella eli itseään kutsuvalla aliohjelmalla, koska nuo sisäkkäiset silmukat ovat vähän hankalia. Silloin myös on helppoa muodostaa eri pituisia yhdistelmiä.
Enpä taida tuota osata rekursiolla tehdä.
Pitää koettaa, kun on enemmän aikaa :(
Yritysten määrää voisi pudottaa melko hyvin myös sellaisella optimoinnilla, ettei se laske erikseen neliöitä, jotka ovat toistensa peilikuvia tai jotka saadaan kiertämällä jotain muuta kuviota.
Esimerkki parista peilikuvasta/kierrosta:
1 2 3
4 5 6 (alkutila)
7 8 9
-------
7 4 1
8 5 2 (kierretty 90 astetta oikealle)
9 6 3
-------
3 2 1
6 5 4 (peilattu pystyakselin suhteen)
9 8 7
Hyvä huomio. Esim. noita 3x3-neliöitä ohjelma löysi kahdeksan, mutta kaikki olivat toistensa kiertoja tai peilikuvia. Itse asiassa 3x3-neliössä taitaa riittää, että numeron 1 paikka on kulmassa, sivulla ja keskellä. Yksistään tämä pienentää ohjelman suoritusajan kolmannekseen.
Ei mulla oikeen onnistu =/ 3x3 tein päässä ja menikin ekalla yrityksellä läpi mutta 4x4 ei enää onnistu... ja jos noin huonosti menee niin turha edes yrittää jotain laskukaavaa tietokoneelle tehdä...
Mainiossa Antero Vipusessa on eräs esimerkki 4x4-taikaneliöstä.
16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1
Paitsi että vaaka- ja pystyrivien sekä lävistäjien summa on 34, keskellä olevan pienemmän neliön lukujen ja nurkissa olevien lukujen summa on myös 34. Ja jos neliö jaetaan neljään pienempään neliöön, on niiden kaikkien lukujen summa 34. Tämä neliö on osa Albrecht Dürerin kuparipiirrosta, joka valmistui vuonna 1514 (sama luku löytyy alimmalta riviltä).
Antti Laaksonen kirjoitti:
Mainiossa Antero Vipusessa on eräs esimerkki 4x4-taikaneliöstä.
Enpä tuota muistanutkaan, vaikka minulla tuo kirja onkin. Pitää katsoa.
Olen keksinyt tällaisen keinon(oli turnauksessa vähän vapaa-aikaa :D)
Tässä ratkaisu 3x3 neliöön.
Ensiksi muodostetaan jokaisesta luvusta niin monta trioa, kuin mahdollista:
ensimmäisen trion rajoitukset(pätee kaikkiin trioihin, kunhan ykköstä kasvatetaan aina sopivaan indeksiin)
1 + x => 5 ja 1 + x <= 15 (suurempi kuin viisi, koska triossa on 3 numeroa,
ja 1, 9 on kymmenen, joten kolmannen numeron on oltava vähintään 5)
1:n triot: 1, 9, 5 1, 8, 6 kaksi trioa -> "sivupala" 2:n triot 2, 7, 6 2, 8, 5 2, 4, 9 kolme trioa -> "kulmapala" 3:n triot 3, 4, 8 3, 5, 7 kaksi trioa -> "sivupala" 4:n triot 4, 2, 9 4, 3, 8 4, 5, 6 kolme trioa -> "kulmapala" 5:n triot 5, 1, 9 5, 2, 8 5, 3, 7 5, 4, 6 neljä trioa -> "keskuspala" 6:n triot 6, 1, 8 6, 2, 7 6, 4, 5 kolme trioa -> "kulmapala" 7:n triot 7, 2, 6 7, 3, 5 kaksi trioa -> "sivupala" 8:n triot 8, 1, 6 8, 2, 5 8, 3, 4 kolme trioa -> "kulmapala" 9:n triot 9, 1, 5 9, 2, 4 kaksi trioa -> "sivupala"
Nyt tiedämme, mihin jokaiset numerot kuuluvat.
Sovitetaan ne paikalleen:
koska 5 kuuluu keskelle -> laitetaan se keskelle.
_____ |_|_|_| |_|5|_| |_|_|_|
etsitään trio, jossa on numero viisi, ja on "sivupala"
_____ |_|3|_| |_|5|_| |_|7|_|
etsitään toinen trio, jossa on numero viisi, ja on "sivupala"
_____ |_|3|_| |1|5|9| |_|7|_|
etsitään trio, jossa on numero viisi, ja on "kulmapala"
_____ | |3|4| |1|5|9| |6|7|_|
etsitään toinen trio, jossa on numero viisi, ja on "kulmapala"
_____ |8|3|4| |1|5|9| |6|7|2|
VALMIS!!
Tietokoneella voisi tehdä reittipuut, ja valita niistä reitin, joka johtaa tähän tulokseen.
Edit: Toivottavasti ei ole liian pitkä.
Laskemiseen kuluvaa aikaa voidaan vähentää, jos lasketaan monella koneella.. Meilla on koulun Labrassa 15*2000Mhz konetta, joille voisin antaa tehtäväksi laskea 4x4-neliön. Vertaa Antti sun koneen tehoihin ja laske kauanko menisi...
peki kirjoitti:
Tässä ratkaisu 3x3 neliöön.
Ensiksi muodostetaan jokaisesta luvusta niin monta trioa, kuin mahdollista:
Hieno ratkaisutapa, ja tuohon ei tarvita edes tietokonetta. Suurempienkin neliöiden ratkaisuun tuosta on varmaan myös apua, joskaan paikat eivät silloin selviä yhtä helposti.
ez kirjoitti:
Meilla on koulun Labrassa 15*2000Mhz konetta, joille voisin antaa tehtäväksi laskea 4x4-neliön. Vertaa Antti sun koneen tehoihin ja laske kauanko menisi...
Suoraan megahertsien perusteella nopeutus olisi kymmenkertainen, eli laskuaika olisi "vain" 157966 vuotta. Tämä siis sillä hitaimmalla algoritmilla, jota ei tietenkään kannata käyttää.
En tuota omaa keinoani osaa toteuttaa rekursiolla. Onko se mahdollista toteuttaa silmukoin? Jos on, niin miten?
Menee tuon algoritmin koodaaminen vähän yli hilseen.
Tämä laskee kaikki 4x4 -neliön ratkaisut omalla koneellani (P3 500Mhz) alle kolmeen sekuntiin. 5x5 -neliöllä en päässyt ensimmäistä pistettä (testaa niin valkenee) pidämmälle. Koodi on valitettavasti kommentoimatonta ja optimoimisen varaakin kyllä vielä olisi. Kääntyy ainakin Dev-c++ :lla mutta luulisin toimivan muillakin ongelmitta.
#include <iostream>
#include <cstdlib>
#include <ctime>
const int sivu = 3; //neliön sivun pituus
const int ruutuja = sivu * sivu;
const int summa = ((ruutuja/2)*(ruutuja+1)+(ruutuja%2)*(ruutuja/2+1)) / sivu;
int maara = 0;
bool kaytetty[ruutuja];
int nelio[ruutuja];
int ratkaisu[ruutuja];
int jarjestys[ruutuja];
int xNum[sivu], yNum[sivu], dNum1 = -1, dNum2 = -1;
int xSum[sivu], ySum[sivu], dSum1 = 0, dSum2 = 0;
// xSum: -
// ySum: |
// dSum1: \
// dSum2: /
int min[sivu], max[sivu];
void Alusta()
{
for( int i = 0; i < ruutuja; ++i )
kaytetty[i] = false;
for( int i = 0; i < sivu; ++i )
{
xSum[i] = ySum[i] = 0;
xNum[i] = yNum[i] = -1;
}
min[sivu-1] = 0;
max[sivu-1] = 0;
for( int i = 1; i < sivu; ++i )
{
min[sivu-i-1] = min[sivu-i] + i;
max[sivu-i-1] = max[sivu-i] + ruutuja + 1 - i;
}
int r = 0;
for( int e = 0; e < sivu; ++e )
jarjestys[r++] = e;
for( int e = 1; e < sivu; ++e )
jarjestys[r++] = e*sivu;
for( int e = 1; e < sivu-1; ++e )
jarjestys[r++] = e*sivu+sivu-e-1;
for( int i = 1; i < sivu; ++i )
{
for( int e = i; e < sivu; ++e )
if( i+e+1 != sivu )
jarjestys[r++] = i*sivu+e;
for( int e = i+1; e < sivu; ++e )
if( i+e+1 != sivu )
jarjestys[r++] = e*sivu+i;
}
}
void EtsiTaikaneliot(int num)
{
int sarake = jarjestys[num] % sivu;
int rivi = jarjestys[num] / sivu;
int xSTmp = xSum[rivi];
int ySTmp = ySum[sarake];
int dSTmp1 = dSum1;
int dSTmp2 = dSum2;
int & xS = xSum[rivi];
int & yS = ySum[sarake];
int dNTmp1 = dNum1;
int dNTmp2 = dNum2;
int & xN = xNum[rivi];
int & yN = yNum[sarake];
++xN;
++yN;
if( rivi == sarake )
++dNum1;
if( rivi == sivu-sarake-1 )
++dNum2;
int xMin = min[xN];
int yMin = min[yN];
int dMin1 = min[dNum1];
int dMin2 = min[dNum2];
int xMax = max[xN];
int yMax = max[yN];
int dMax1 = max[dNum1];
int dMax2 = max[dNum2];
for( int i = 1; i <= ruutuja; ++i )
{
if( !kaytetty[i-1] )
{
nelio[jarjestys[num]] = i;
xS = xSTmp + i;
if( xS+xMin > summa || xS+xMax < summa )
continue;
yS = ySTmp + i;
if( yS+yMin > summa || yS+yMax < summa )
continue;
dSum1 = dSTmp1;
if( rivi == sarake )
{
dSum1 += i;
if( dSum1+dMin1 > summa || dSum1+dMax1 < summa )
continue;
}
dSum2 = dSTmp2;
if( rivi == sivu-sarake-1 )
{
dSum2 += i;
if( dSum2+dMin2 > summa || dSum2+dMax2 < summa )
continue;
}
if( num < ruutuja-1 )
{
kaytetty[i-1] = true;
EtsiTaikaneliot(num+1);
kaytetty[i-1] = false;
}else{
//ratkaisu löytyi -> tässä vaiheessa hoidettaisiin tulostus
++maara;
memcpy(ratkaisu, nelio, ruutuja*sizeof(int));
}
}
if( num == 1 )
std::cout << '.';
if( num == 0 )
std::cout << " Testattu " << i << ", J\x84ljell\x84 " << ruutuja-i << std::endl;
}
xS = xSTmp;
yS = ySTmp;
dSum1 = dSTmp1;
dSum2 = dSTmp2;
--xN;
--yN;
dNum1 = dNTmp1;
dNum2 = dNTmp2;
}
int main()
{
Alusta();
std::cout << "Rivin summa on " << summa << std::endl;
std::cout << "Etsit\x84\x84n ratkaisuja:\n";
int aikaAlussa = clock();
EtsiTaikaneliot(0);
int aikaLopussa = clock();
int aika = aikaLopussa - aikaAlussa;
std::cout << "\n\nValmis. Ratkaisuja l\x94ytyi " << maara << " (" << maara/8
<< " erilaista) kpl.\n\n";
std::cout << "Viimeisin l\x94ydetty ratkaisu oli:\n";
for( int i = 0; i < ruutuja; ++i )
{
std::cout.width(3);
std::cout << ratkaisu[i];
if( i%sivu == sivu-1 )
std::cout << std::endl;
}
std::cout << "\nAikaa kului " << aika/3600000 << "h " << (aika/60000)%60 << "min "
<< (aika/1000)%60 << '.' << (aika/100)%10 << (aika/10)%10 << aika%10 << "s.\n\n";
system("pause");
}Monimutkaista koodia! Täytyy tuohon perehtyä oikein ajan kanssa.
Tästä voisi tehdä esimerkiksi koodivinkin?
Hyvin tuntui toimivan koodi, olisi kiva kuulla vähän tarkemmin sen toimintaperiaatteesta. Seuraava haaste on järkevässä ajassa 5x5-taikaneliöiden etsiminen, joita lienee melko suuri määrä: 3x3-neliöitä on vain yksi, mutta 4x4-neliöitä jo 880 erilaista.
Erilaisia 5x5 taikaneliöitä on 275305224 kappaletta (tässä taikaneliöt ovat erilaisia vaikka toinen saataisiin toisesta permutoimalla sarakkeita tai rivejä) joten siitä vain etsimään!
Aihe on jo aika vanha, joten et voi enää vastata siihen.