Puurakenne

Kyseessä on eräs optimointiongelma, jossa pitäisi etsiä pienin suorakulmio, josta voi lukea annetut luvut. Kaikkien tapausten tutkiminen ei tule kysymykseen, sillä erilaisia suorakulmioita on noin 10^150-10^200 kpl. Minusta asiaa on helpoin ajatella puuna, jossa juuressa on tyhjä suorakulmio, seuraavassa askeleessa suorakulmioon on laitettu yksi luku, sen lapsessa on kyseinen luku toinen luku. Mietin asiaa siten, että kussakin solmussa olisi indeksi, joka kuvaa, mitä solmua lähdetään tutkimaan. Jos päädytään umpikujaan, joudutaan palaamaan taaksepäin ja poistamaan huonot solmut.

tukijamatemaatikko kirjoitti:

Kyseessä on eräs optimointiongelma, jossa pitäisi etsiä pienin suorakulmio, josta voi lukea annetut luvut. Kaikkien tapausten tutkiminen ei tule kysymykseen, sillä erilaisia suorakulmioita on noin 10^150-10^200 kpl. Minusta asiaa on helpoin ajatella puuna, jossa juuressa on tyhjä suorakulmio, seuraavassa askeleessa suorakulmioon on laitettu yksi luku, sen lapsessa on kyseinen luku toinen luku. Mietin asiaa siten, että kussakin solmussa olisi indeksi, joka kuvaa, mitä solmua lähdetään tutkimaan. Jos päädytään umpikujaan, joudutaan palaamaan taaksepäin ja poistamaan huonot solmut.

Lue lisää

Tuosta ei vielä oikein selviä että voisiko homma onnistua kuitenkin rekursiolla. Säilytetäänkö muistissa vain paras "oksa" ja uusia testataan vai kuinka..?

tukijamatemaatikko kirjoitti:

Kyseessä on eräs optimointiongelma, jossa pitäisi etsiä pienin suorakulmio, josta voi lukea annetut luvut. Kaikkien tapausten tutkiminen ei tule kysymykseen, sillä erilaisia suorakulmioita on noin 10^150-10^200 kpl. Minusta asiaa on helpoin ajatella puuna, jossa juuressa on tyhjä suorakulmio, seuraavassa askeleessa suorakulmioon on laitettu yksi luku, sen lapsessa on kyseinen luku toinen luku. Mietin asiaa siten, että kussakin solmussa olisi indeksi, joka kuvaa, mitä solmua lähdetään tutkimaan. Jos päädytään umpikujaan, joudutaan palaamaan taaksepäin ja poistamaan huonot solmut.

Lue lisää

Kuulostaa vähän siltä, että ehkä sitä puuta ei tarvitse oikeasti muodostaa vaan tehdäänkin rekursiolla lennossa se osa puuta mitä tutkitaan. Tai itse asiassa koko puuta ei tarvitse muodostaa kun rekursio jo epäsuorasti muodostaa sen puun. Vaikea sanoa mitään konkreettista tietämättä mikä se ongelma on oikeasti. Oletko varma ettei ongelmalla ole yksinkertaisempaa ratkaisua?

tutkija-x kirjoitti:

Kuulostaa vähän siltä, että ehkä sitä puuta ei tarvitse oikeasti muodostaa vaan tehdäänkin rekursiolla lennossa se osa puuta mitä tutkitaan. Tai itse asiassa koko puuta ei tarvitse muodostaa kun rekursio jo epäsuorasti muodostaa sen puun. Vaikea sanoa mitään konkreettista tietämättä mikä se ongelma on oikeasti. Oletko varma ettei ongelmalla ole yksinkertaisempaa ratkaisua?

Lue lisää

Enpäs ole keksinyt muuta ratkaisua.

tutkijamatemaatikko kirjoitti:

Enpäs ole keksinyt muuta ratkaisua.

Mikä se ongelma tarkemmin ottaen on mitä olet ratkaisemassa? Vaikka matemaattisen algoritmin kuvaisikin puurakenteen muodostamisena ja sen käsittelynä, on se joskus mahdollista käytännössä laskea muodostamatta oikeasti sitä puuta. Mutta tietämättä ongelmasta enempää on vähän vaikea sanoa onnistuuko se tässä tapauksessa.

tutkijamatemaatikko kirjoitti:

Enpäs ole keksinyt muuta ratkaisua.

Rekursio kyllä vaikuttaisi passelilta tuohon "pitäisi etsiä pienin suorakulmio, josta voi lukea annetut luvut". Siis samaan tapaan kuin shakkiohjelma tekee rekursiivisesti siirtoja eteenpäin etsiessään parasta siirtoa.

tutkija-x kirjoitti:

Mikä se ongelma tarkemmin ottaen on mitä olet ratkaisemassa? Vaikka matemaattisen algoritmin kuvaisikin puurakenteen muodostamisena ja sen käsittelynä, on se joskus mahdollista käytännössä laskea muodostamatta oikeasti sitä puuta. Mutta tietämättä ongelmasta enempää on vähän vaikea sanoa onnistuuko se tässä tapauksessa.

Lue lisää

Löysin sen osoitteesta http://www.mersenneforum.org/showthread.php?t=13381 . Siis hahmottelin ratkaisuksi sellaisen puun, että sen juuressa on tyhjä taulukko. Sen lapsina on kaikki ne taulukot, joihin on laitettu luku 10000. Näiden lapsina on taulukot, jossa on luvut 10000 ja 9801 jne. Kaverini kysyi tuolle tehtävälle ratkaisua ja en keksinyt muuta tapaa kuin puurakenteen ja best-first-searchin.

tutkijamatemaatikko kirjoitti:

Löysin sen osoitteesta http://www.mersenneforum.org/showthread.php?t=13381 . Siis hahmottelin ratkaisuksi sellaisen puun, että sen juuressa on tyhjä taulukko. Sen lapsina on kaikki ne taulukot, joihin on laitettu luku 10000. Näiden lapsina on taulukot, jossa on luvut 10000 ja 9801 jne. Kaverini kysyi tuolle tehtävälle ratkaisua ja en keksinyt muuta tapaa kuin puurakenteen ja best-first-searchin.

Lue lisää

Piti siis kirjoittaa, että postitin ongelman tuolle palstalle, mutta uulin siitä kaveriltani.

tutkijamatemaatikko kirjoitti:

Löysin sen osoitteesta http://www.mersenneforum.org/showthread.php?t=13381 . Siis hahmottelin ratkaisuksi sellaisen puun, että sen juuressa on tyhjä taulukko. Sen lapsina on kaikki ne taulukot, joihin on laitettu luku 10000. Näiden lapsina on taulukot, jossa on luvut 10000 ja 9801 jne. Kaverini kysyi tuolle tehtävälle ratkaisua ja en keksinyt muuta tapaa kuin puurakenteen ja best-first-searchin.

Lue lisää

Mites tuo siis menee. Eli 11x11 gridi, joka muodostuu numeroista (0-9?) ja jostain ruudusta johonkin valittuun suuntaan lähtien voidaan lukea luvut 1^2,2^2,3^2,...,100^2, niinkö? Mitä tapahtuu kun tullaan gridin reunaan vai saako siis suuntaa vaihtaa joka askeleella? Ja pitääkö sieltä siis löytyä sekvenssi 1491625... vai mitä tuo tarkoittaa?

tutkija-x kirjoitti:

Mites tuo siis menee. Eli 11x11 gridi, joka muodostuu numeroista (0-9?) ja jostain ruudusta johonkin valittuun suuntaan lähtien voidaan lukea luvut 1^2,2^2,3^2,...,100^2, niinkö? Mitä tapahtuu kun tullaan gridin reunaan vai saako siis suuntaa vaihtaa joka askeleella? Ja pitääkö sieltä siis löytyä sekvenssi 1491625... vai mitä tuo tarkoittaa?

Lue lisää

"Eli 11x11 gridi, joka muodostuu numeroista (0-9?)"

Kyllä.

Lukeminen tapahtuu siten, että kullekin luvulle etsitään luvun alkukohta ja kiinnitetään suunta, johon mennään. Jos näin löydetään luku n^2, voidaan valita uusi alkukohta, kiinnittää suunta ja etsiä luku (n 1)^2. Suuntaa ei saa vaihtaa välillä ja reunoja ei voi ylittää. Esimerkiksi 2x4- ruudukosta

1004
6414

voidaan lukea neliöt 1^2=1,10^2=100,20^2=400 ja 8^2=64.

tutkijamatemaatikko kirjoitti:

"Eli 11x11 gridi, joka muodostuu numeroista (0-9?)"

Kyllä.

Lukeminen tapahtuu siten, että kullekin luvulle etsitään luvun alkukohta ja kiinnitetään suunta, johon mennään. Jos näin löydetään luku n^2, voidaan valita uusi alkukohta, kiinnittää suunta ja etsiä luku (n 1)^2. Suuntaa ei saa vaihtaa välillä ja reunoja ei voi ylittää. Esimerkiksi 2x4- ruudukosta

1004
6414

voidaan lukea neliöt 1^2=1,10^2=100,20^2=400 ja 8^2=64.

Lue lisää

1004
6414

voidaan lukea neliöt 1^2=1,4^2=16,10^2=100,20^2=400 ja 8^2=64.

tutkijamatemaatikko kirjoitti:

"Eli 11x11 gridi, joka muodostuu numeroista (0-9?)"

Kyllä.

Lukeminen tapahtuu siten, että kullekin luvulle etsitään luvun alkukohta ja kiinnitetään suunta, johon mennään. Jos näin löydetään luku n^2, voidaan valita uusi alkukohta, kiinnittää suunta ja etsiä luku (n 1)^2. Suuntaa ei saa vaihtaa välillä ja reunoja ei voi ylittää. Esimerkiksi 2x4- ruudukosta

1004
6414

voidaan lukea neliöt 1^2=1,10^2=100,20^2=400 ja 8^2=64.

Lue lisää

Tuossahan (11*11)^10 = 121^10 eri mahdollisuutta ja jos kone käy läpi vaikka miljardi tapausta sekunnissa (jota tuskin tekee), niin aikaa menee reippaasti alakanttiin arvioiden 121^10 > (10^2)^10 => 10^20/10^9 = 10^11 sekuntia eli yli 3000 vuotta. Brute-force ei nyt oikein käy.

Joten pitäisi keksiä jotain nokkelaa, ehkäpä jotenkin rajoittaa tapauksia tai vanhalla kunnon kynä-paperi jutskalla. Tehtävässähän ei vaadittu varsinaisen ratkaisun esittämistä, vaan todistus että sellainen on olemassa.

Brutalix kirjoitti:

Tuossahan (11*11)^10 = 121^10 eri mahdollisuutta ja jos kone käy läpi vaikka miljardi tapausta sekunnissa (jota tuskin tekee), niin aikaa menee reippaasti alakanttiin arvioiden 121^10 > (10^2)^10 => 10^20/10^9 = 10^11 sekuntia eli yli 3000 vuotta. Brute-force ei nyt oikein käy.

Joten pitäisi keksiä jotain nokkelaa, ehkäpä jotenkin rajoittaa tapauksia tai vanhalla kunnon kynä-paperi jutskalla. Tehtävässähän ei vaadittu varsinaisen ratkaisun esittämistä, vaan todistus että sellainen on olemassa.

Lue lisää

No joo, ei taas tullut luettua koko ketjua, olihan tuo jo ymmärretty.

Jotenkin niitä neliölukuja voisi tosiaan tunkea siihen taulukkoon ja ainakin kannattaa aloittaa suurimmista. Hmm... ei muuta neuvoa tule tähän hätään.

tutkijamatemaatikko kirjoitti:

"Eli 11x11 gridi, joka muodostuu numeroista (0-9?)"

Kyllä.

Lukeminen tapahtuu siten, että kullekin luvulle etsitään luvun alkukohta ja kiinnitetään suunta, johon mennään. Jos näin löydetään luku n^2, voidaan valita uusi alkukohta, kiinnittää suunta ja etsiä luku (n 1)^2. Suuntaa ei saa vaihtaa välillä ja reunoja ei voi ylittää. Esimerkiksi 2x4- ruudukosta

1004
6414

voidaan lukea neliöt 1^2=1,10^2=100,20^2=400 ja 8^2=64.

Lue lisää

Oletko kokeilut kynällä ja ruutupaperilla, tuntuisi että voisi onnistua koska lukuja on 100 kpl ja ruutuja 121, niin tuntuisi mahtuvan melko helposti. Vikan eli 10000 voisi sijoittaa reunaan ja isot sitten perään.

Tossa luvut:
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289
324 361 400 441 484 529 576 625 676 729 784 841 900 961
1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764
1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809
2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096
4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625
5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396
7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409
9604 9801 10000

Ihan hauska tehtävä jos onnistuu käsin.

Auttaisikohan etsiä ensin 'pareja' esim. 4245 2401 jotka menevät osin päällekkäin.

Brutalix kirjoitti:

Oletko kokeilut kynällä ja ruutupaperilla, tuntuisi että voisi onnistua koska lukuja on 100 kpl ja ruutuja 121, niin tuntuisi mahtuvan melko helposti. Vikan eli 10000 voisi sijoittaa reunaan ja isot sitten perään.

Tossa luvut:
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289
324 361 400 441 484 529 576 625 676 729 784 841 900 961
1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764
1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809
2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096
4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625
5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396
7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409
9604 9801 10000

Ihan hauska tehtävä jos onnistuu käsin.

Auttaisikohan etsiä ensin 'pareja' esim. 4245 2401 jotka menevät osin päällekkäin.

Lue lisää

Tuossahan voisi rekursiivinen haku toimia. Jo joku fiksu algoritmi joka estää symmetriset toisinnot; siis jos aloitetaan sijoittamalla "10000" nurkkaan eri asentoihin, niin edetään laitaa pitkin, mutta laidan puolenvälin yli ei tarvitse mennä, koska se on symmetrisesti samanlainen kuin aloituspuoli. Mennäänkin seuraavalle riville, mutta ei ensimmäiseen ruuruun, koska se on jo symmetrisesti tutkittu jne.

Brutalix kirjoitti:

Oletko kokeilut kynällä ja ruutupaperilla, tuntuisi että voisi onnistua koska lukuja on 100 kpl ja ruutuja 121, niin tuntuisi mahtuvan melko helposti. Vikan eli 10000 voisi sijoittaa reunaan ja isot sitten perään.

Tossa luvut:
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289
324 361 400 441 484 529 576 625 676 729 784 841 900 961
1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764
1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809
2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096
4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625
5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396
7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409
9604 9801 10000

Ihan hauska tehtävä jos onnistuu käsin.

Auttaisikohan etsiä ensin 'pareja' esim. 4245 2401 jotka menevät osin päällekkäin.

Lue lisää

Selitinpä väärin. Kuhunkin ruutuun tulee yksi numero, ei luku. Siten vaikkapa jos 3 peräkkäisessä ruudussa on numerot 4, 0 ja 0, niin siitä voidaan lukea luku 400=20^2. Mutta lukujen 1,4,9,...,10000 tarvitaan paljon enemmän numeroita, joten aika tiiviisti sijoittelun saa tehdä.

tutkijamatemaatikko kirjoitti:

Selitinpä väärin. Kuhunkin ruutuun tulee yksi numero, ei luku. Siten vaikkapa jos 3 peräkkäisessä ruudussa on numerot 4, 0 ja 0, niin siitä voidaan lukea luku 400=20^2. Mutta lukujen 1,4,9,...,10000 tarvitaan paljon enemmän numeroita, joten aika tiiviisti sijoittelun saa tehdä.

Lue lisää

Tietokoneen kannalta asetelma on vähän kuin GO pelissä; siinä on niin paljon eri vaihtoehtoja joka "siirrolla" (verrattuna esim shakkiin) että vie aikaa tutkia. Pitäisi olla jokin menetelmä että numeroita ei lätkitä täysin satunnaisesti koko ruudukon alueelle, vaan esim. aloitetaan tutkiminen aloituspaikan ympäriltä lähtien.

tutkijamatemaatikko kirjoitti:

Selitinpä väärin. Kuhunkin ruutuun tulee yksi numero, ei luku. Siten vaikkapa jos 3 peräkkäisessä ruudussa on numerot 4, 0 ja 0, niin siitä voidaan lukea luku 400=20^2. Mutta lukujen 1,4,9,...,10000 tarvitaan paljon enemmän numeroita, joten aika tiiviisti sijoittelun saa tehdä.

Lue lisää

Joo, ymmärsin kyllä ja arvioni taisi olla väärä, sillä jos neliöluvut pistetään peräkkäin "1491625..." niin tulee 358 merkkiä. 'Pakkaussuhde' on siis 358/121 = 2,96, joten tiivis se on.

Etkö ole kokeillut paperilla? Vaikka ei onnistuisi, niin siitä saa ideoita kuinka homma tulisi koodata.

Vanha viidakon sananlasku koodareille onkin: Hankalaan ongelmaan kynä ja paperi on paras työkalusi.

tutkijamatemaatikko kirjoitti:

"Eli 11x11 gridi, joka muodostuu numeroista (0-9?)"

Kyllä.

Lukeminen tapahtuu siten, että kullekin luvulle etsitään luvun alkukohta ja kiinnitetään suunta, johon mennään. Jos näin löydetään luku n^2, voidaan valita uusi alkukohta, kiinnittää suunta ja etsiä luku (n 1)^2. Suuntaa ei saa vaihtaa välillä ja reunoja ei voi ylittää. Esimerkiksi 2x4- ruudukosta

1004
6414

voidaan lukea neliöt 1^2=1,10^2=100,20^2=400 ja 8^2=64.

Lue lisää

Pitää vielä miettiä miten tuota itse lähtisi ratkaisemaan, mutta se puuideasi tuntuu kyllä hieman brite force:lta, mikä tässä ei kyllä voi toimia. Itse asiassa vaikuttaa siltä, että kynä ja paperi ovat kovaa valuuttaa tässä tehtävässä. Ainakin voi laskea jotain pienempiä vastaavia ongelmia läpi (vaikka 1^2,...,5^2) ja yrittää keksiä jotain ratkaisualgoritmia. Tosin tällaisen konstruktiivisen todistuksen sijaan voi myös miettiä saisiko sen olemassaolon todistettua jotenkin muuten.

tutkija-x kirjoitti:

Pitää vielä miettiä miten tuota itse lähtisi ratkaisemaan, mutta se puuideasi tuntuu kyllä hieman brite force:lta, mikä tässä ei kyllä voi toimia. Itse asiassa vaikuttaa siltä, että kynä ja paperi ovat kovaa valuuttaa tässä tehtävässä. Ainakin voi laskea jotain pienempiä vastaavia ongelmia läpi (vaikka 1^2,...,5^2) ja yrittää keksiä jotain ratkaisualgoritmia. Tosin tällaisen konstruktiivisen todistuksen sijaan voi myös miettiä saisiko sen olemassaolon todistettua jotenkin muuten.

Lue lisää

Mielestäni taas puuidea voisi toimia, kun kerran siihen käytetään best-first-etsintää, jolloin ensiksi tutkitaan lupaavimmat vaihtoehdot. Onhan se tietyllä tapaa brute forcea, mutta sen ei pitäisi kestää tolkuttoman kauan. Jos osaisin koodata, niin voisin kokeilla tuota.

tutkijamatemaatikko kirjoitti:

Mielestäni taas puuidea voisi toimia, kun kerran siihen käytetään best-first-etsintää, jolloin ensiksi tutkitaan lupaavimmat vaihtoehdot. Onhan se tietyllä tapaa brute forcea, mutta sen ei pitäisi kestää tolkuttoman kauan. Jos osaisin koodata, niin voisin kokeilla tuota.

Lue lisää

Tarkoitatko best-first-haulla jotain A*-algoritmin variaatiota?

http://en.wikipedia.org/wiki/A*_search_algorithm

Minkälaista heuristiikkaa ajattelit? Eli mikä on "lupaava" vaihtoehto? Ei sitä puuta tarvitse tuossa haussa muodostaa, pelkkä rekursio riittää. Tuo voi toimiakin, jos mahdollisia ratkaisuja on huomattavasti enemmän kuin yksi. Jos niitä on vain vähän, redusoituu tuo käytännössä brute-forceksi.

tutkija-x kirjoitti:

Tarkoitatko best-first-haulla jotain A*-algoritmin variaatiota?

http://en.wikipedia.org/wiki/A*_search_algorithm

Minkälaista heuristiikkaa ajattelit? Eli mikä on "lupaava" vaihtoehto? Ei sitä puuta tarvitse tuossa haussa muodostaa, pelkkä rekursio riittää. Tuo voi toimiakin, jos mahdollisia ratkaisuja on huomattavasti enemmän kuin yksi. Jos niitä on vain vähän, redusoituu tuo käytännössä brute-forceksi.

Lue lisää

Näyttäisi tuo A* olevan jotain sellaista, jota haen. Sanotaan taulukon ruutua vapaaksi, jos siihen ei ole laitettu numeroa. Tällöin vapaiden ruutujen määrä löydettyjen neliölukujen määrä voisi olla toimiva heuristiikka.

tutkijamatemaatikko kirjoitti:

Näyttäisi tuo A* olevan jotain sellaista, jota haen. Sanotaan taulukon ruutua vapaaksi, jos siihen ei ole laitettu numeroa. Tällöin vapaiden ruutujen määrä löydettyjen neliölukujen määrä voisi olla toimiva heuristiikka.

Lue lisää

Veikkaan, että tuollaisella heuristiikalla menetelmä on käytännössä brute-force eikä anna käytännössä vastausta koskaan. Lieneekö tuo heuristiikka edes validi?

Jos paikkoja on vaan 121 ja mahdutettavia merkkejä on 358, niin se on se päällekkäisyys mikä tässä dominoi. Itse asiassa poistamalla ne neliöt jotka ovat etu- tai takaperin sisällytettynä suurempiin neliöihin, saadaan merkkien määrä vähennettyä 312:een. Tämänkin jälkeen päällekkäisyyksiä pitää olla 191, eli huomattava osa luvuista on osana jopa kolmea neliötä.

Päällekkäisyyksiä voisi ehkä käyttää etsinnässä jotenkin näin:

- Muodostetaan (tai kuvitellaan) graafi, jossa kunkin neliön numeroista on kaaret samoihin numeroihin muissa neliöissä. Nämä kuvaavat siis mahdollisia päällekkäisyyksiä numeroissa.
- Kaaria poistamalla voidaan päästä sellaiseen tilanteeseen, että päällekkäisyydet voidaan toteuttaa kahdessa dimensiossa (jolloin graafi on "validi"). Koska päällekkäisyyksiä pitää joka tapauksessa olla paljon, ei annetulla graafilla liene mahdollisia asetteluja kovin paljoa. Onhan kaaria oltava ainakin 191.
- Näistä valideista graafeista pitää valita sellanen, jonka realisaatio mahtuu 11x11-ruudukkoon.

Tämän ongelman ratkaiseminen A*-haulla voisi olla ehkä realistisempi kuin suoraviivainen lukujen peräkkäinen asettelu gridiin. Haasteena tässä on ainakin keksiä nopea algoritmi graafin määräävän 2d-asettelun muodostamiseen ja/tai validiuden tarkistamiseen.

tutkijamatemaatikko kirjoitti:

Näyttäisi tuo A* olevan jotain sellaista, jota haen. Sanotaan taulukon ruutua vapaaksi, jos siihen ei ole laitettu numeroa. Tällöin vapaiden ruutujen määrä löydettyjen neliölukujen määrä voisi olla toimiva heuristiikka.

Lue lisää

Kokeilin nopeasti ihan simppelia rekursiivistä bruteforce menetelmää joka lätkii lukuja järjestyksessä alkaen 10000 sitten 9801 jne. Nopeasti löytyy 39.. 40.. lukua ja hetken ruksuteltuaan 41 lukua on saanut sopimaan, eli lukuun 3600 asti, mutta sitten näyttäisi hidastuvan kuin seinään.

aapeli. kirjoitti:

Kokeilin nopeasti ihan simppelia rekursiivistä bruteforce menetelmää joka lätkii lukuja järjestyksessä alkaen 10000 sitten 9801 jne. Nopeasti löytyy 39.. 40.. lukua ja hetken ruksuteltuaan 41 lukua on saanut sopimaan, eli lukuun 3600 asti, mutta sitten näyttäisi hidastuvan kuin seinään.

Lue lisää

Tai siis 41. eli 3600 oli luku jota ei enää saatu sopimaan (melko lyhyessä ajassa). silloin näytti tältä:

1 0 0 0 0 9 8 0 1 9 8
8 6 4 9 6 4 2 7 6 0 8
1 7 5 0 6 0 8 1 7 2 3
0 9 4 4 7 9 1 7 6 5 6
0 2 7 5 3 2 4 7 8 6 5
6 1 6 9 9 4 2 0 8 4 6
2 9 0 2 6 5 4 5 9 0 1
4 4 8 9 7 6 2 6 6 0 2
1 8 4 7 9 2 3 5 2 9 7
x 1 6 7 4 5 3 8 4 4 3
x 5 0 4 1 4 0 9 6 9 3

aapeli. kirjoitti:

Tai siis 41. eli 3600 oli luku jota ei enää saatu sopimaan (melko lyhyessä ajassa). silloin näytti tältä:

1 0 0 0 0 9 8 0 1 9 8
8 6 4 9 6 4 2 7 6 0 8
1 7 5 0 6 0 8 1 7 2 3
0 9 4 4 7 9 1 7 6 5 6
0 2 7 5 3 2 4 7 8 6 5
6 1 6 9 9 4 2 0 8 4 6
2 9 0 2 6 5 4 5 9 0 1
4 4 8 9 7 6 2 6 6 0 2
1 8 4 7 9 2 3 5 2 9 7
x 1 6 7 4 5 3 8 4 4 3
x 5 0 4 1 4 0 9 6 9 3

Lue lisää

Tuollainen rekursio voi kestää aika kauan. Olisikohan olemassa mitään tapaa, jolla rekursiota voisi ohjata etsimään ratkaisua? Esimerkiksi jos ruudukkoon on täytetty n numeroa ja on löydetty neliöt m^2, (m 1)^2,...,100^2 ja n sekä m toteuttavat jotain ehtoja, niin ratkaisua ei voi löytyä. Tuo pakkaussuhde 358/121 voisi ehkä jotenkin auttaa tähän, mutta en keksi miten.

ongelmanmiettijä kirjoitti:

Tuollainen rekursio voi kestää aika kauan. Olisikohan olemassa mitään tapaa, jolla rekursiota voisi ohjata etsimään ratkaisua? Esimerkiksi jos ruudukkoon on täytetty n numeroa ja on löydetty neliöt m^2, (m 1)^2,...,100^2 ja n sekä m toteuttavat jotain ehtoja, niin ratkaisua ei voi löytyä. Tuo pakkaussuhde 358/121 voisi ehkä jotenkin auttaa tähän, mutta en keksi miten.

Lue lisää

Pakkaussuhde on muuten 312/121 ~ 2.6, kun poistetaan ne luvut jotka sisältyvät suoraan tai kääntäen muihin (kuten jo aikaisemmin mainittiin). Lukuja jää 81 kpl eli nämä:

121 196 256 289 361 484 529 576 676 729 784 841 961 1024 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625 5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396 7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409 9604 9801 10000

Poistetut:
1 4 9 16 25 36 49 64 81 100 144 169 225 324 400 441 625 900 1089

ongelmanmiettijä kirjoitti:

Tuollainen rekursio voi kestää aika kauan. Olisikohan olemassa mitään tapaa, jolla rekursiota voisi ohjata etsimään ratkaisua? Esimerkiksi jos ruudukkoon on täytetty n numeroa ja on löydetty neliöt m^2, (m 1)^2,...,100^2 ja n sekä m toteuttavat jotain ehtoja, niin ratkaisua ei voi löytyä. Tuo pakkaussuhde 358/121 voisi ehkä jotenkin auttaa tähän, mutta en keksi miten.

Lue lisää

Niin siis se pakkaussuhde 312/121 kertoo, että jokaisen ruudun läpi kulkee keskimäärin 2.6 eri lukua. Siispä ehkäpä kannattaisi koittaa keskittyä näihin päällekkäisyysrelaatioihin lukujen paikkojen suoran etsimisen sijaan (kuten ylempänä ehdotetussa algoritmissa).

Vaikea kuvitella, että olisi jotain ehtoja n:lle ja m:lle tuossa mainitsemassasi mielessä, koska samoilla n,m voi olla aina ratkaisuja tai ei. Vaikka ruudukko olisi täynnä, niin koska pakkaussuhde on 2.6, se ei takaa etteivät kaikki loput neliöt silti menisi ruudukkkoon.

tutkija-x kirjoitti:

Niin siis se pakkaussuhde 312/121 kertoo, että jokaisen ruudun läpi kulkee keskimäärin 2.6 eri lukua. Siispä ehkäpä kannattaisi koittaa keskittyä näihin päällekkäisyysrelaatioihin lukujen paikkojen suoran etsimisen sijaan (kuten ylempänä ehdotetussa algoritmissa).

Vaikea kuvitella, että olisi jotain ehtoja n:lle ja m:lle tuossa mainitsemassasi mielessä, koska samoilla n,m voi olla aina ratkaisuja tai ei. Vaikka ruudukko olisi täynnä, niin koska pakkaussuhde on 2.6, se ei takaa etteivät kaikki loput neliöt silti menisi ruudukkkoon.

Lue lisää

Pitäisi varmaan lätkiä noita numeroita jotenkin fiksummassa järjestyksessä kuin tuossa mun kokeilussa rivi riviltä ja sarake sarakkeelta, alkaen numerosta 10000, 9801 jne. Tuon 2.6 suhteen saavuttaminen ylipäätään näyttäisi olevan heti alkuunsa hankalaa. Vaikka siis laittaisi suhteen rekursion jatkumisen ehdoksi. Ehkä jotenkin järjestämällä lätkittävät numerot sen mukaan kuinka niissä on yhteisiä numeroita eli mahdollisimman hyvät mahdollisuudet risteymiin.

aapeli. kirjoitti:

Pitäisi varmaan lätkiä noita numeroita jotenkin fiksummassa järjestyksessä kuin tuossa mun kokeilussa rivi riviltä ja sarake sarakkeelta, alkaen numerosta 10000, 9801 jne. Tuon 2.6 suhteen saavuttaminen ylipäätään näyttäisi olevan heti alkuunsa hankalaa. Vaikka siis laittaisi suhteen rekursion jatkumisen ehdoksi. Ehkä jotenkin järjestämällä lätkittävät numerot sen mukaan kuinka niissä on yhteisiä numeroita eli mahdollisimman hyvät mahdollisuudet risteymiin.

Lue lisää

Jonkilainen ideanpoikanen että jos ei olisikaan kiinteäsi rajoitettu (11x11) ruudukko, vaan ensimmäinen neliö lätkäistäisiin nollakoordinaattiin ja seuraavat neliöt jollakin menetelmällä spiraalisti laajeten. 11x11 raja muodostuisi dynaamisesti senmukaan kuinka kauas neliöitä on jo aseteltu.