Kuinka täyteen pystyt täyttämään nxn -ruudukon, niin että mitkään neljä täytettyä ruutua eivät ole minkään neliön nurkat. Vain suorassa olevat neliöt otetaan huomioon.
Kokeile täällä pienille ruudukoille: https://jsfiddle.net/kdzxg7s1/4/
(JSFiddleä ei taida enää saada millään kokoruudulle, mutta voi tuolla sitä vetää vähän isommaksi ja muuttaa CSS:än #gridContainerin width ja height isommiksi.)
Ruudukon täyttö niin että ei muodostu neliöitä
Anonyymi
36
902
Vastaukset
- Anonyymi
Keksin kutoselle tämmöisen: https://imgur.com/Oe3VtZs
Eli 23 ruutua 36:sta täytetty. Liekkö paras mahdollinen?- Anonyymi
Kokeilin vanhaa S. Moronin menetelmää ihan vaan lyijykynällä pöydällä olleen A4:n tyhjään tilaan. Menetelmässä poistetaan neliöiden nurkkia suuruusjärjestyksessä. Ensin 6x6, sitten 5x5:t ja siten 4x4:t ja katsotaan miten käy. Laidoilta ei poisteta mitään, jos ei ole ihan pakko.
6XXXXX
X5X45X
XXX44X
X44XXX
X54X2X
XXXXX4
Jäljelle jäi 24 kpl X-merkittyä. Numero kertoo, miksi poistettiin. Meni ihan mekaanisesti. Oli aina yksi vaihtoehto, joten ei tarvinnut kombinoida. ( Ihan lopussa piti rikkoa sääntöä ja poista alanurkasta yksi. Korvasi kaksi sääntöjen mukaista poistoa.)
Aika symmetrinen kuvio. Ei näyttäisi löytyvän yhtään 2x2 tai 3x3 neliötä. Sain myös täytettyä ruudukkosi ilman virheilmoitusta. - Anonyymi
Anonyymi kirjoitti:
Kokeilin vanhaa S. Moronin menetelmää ihan vaan lyijykynällä pöydällä olleen A4:n tyhjään tilaan. Menetelmässä poistetaan neliöiden nurkkia suuruusjärjestyksessä. Ensin 6x6, sitten 5x5:t ja siten 4x4:t ja katsotaan miten käy. Laidoilta ei poisteta mitään, jos ei ole ihan pakko.
6XXXXX
X5X45X
XXX44X
X44XXX
X54X2X
XXXXX4
Jäljelle jäi 24 kpl X-merkittyä. Numero kertoo, miksi poistettiin. Meni ihan mekaanisesti. Oli aina yksi vaihtoehto, joten ei tarvinnut kombinoida. ( Ihan lopussa piti rikkoa sääntöä ja poista alanurkasta yksi. Korvasi kaksi sääntöjen mukaista poistoa.)
Aika symmetrinen kuvio. Ei näyttäisi löytyvän yhtään 2x2 tai 3x3 neliötä. Sain myös täytettyä ruudukkosi ilman virheilmoitusta.Kokeilin 6x6:sta myös pienellä ja tyhmällä Python-ohjelmalla. Löytyi 68 kpl 24:n ruudukkoa. Niistä ehkä n. 8 on peilikuvia.
Yhtään 25 ruudukkoa ei löytynyt. 6x6 ruudukossa on 9 kpl täysin itsenäistä 2x2 ruudukkoa. Jokaisesta pitää poistaa vähintään yksi. Kaikkien 5x5:ien ja 4x4:ien ja 3x3:ien rikkominen ei onnistu millään kahdella lisäpoistolla.
7x7:sta saa alle 5 minuutissa suoraan paperilla S. Moronin menetelmällä 31. Pythonilla voi saada ehkä yhden lisää. Yrittäkää. Helppo optimoida monilla eri tavoilla. Mitään ei tieystikän kannata lisätä, vaan poistaa. - Anonyymi
Anonyymi kirjoitti:
Kokeilin vanhaa S. Moronin menetelmää ihan vaan lyijykynällä pöydällä olleen A4:n tyhjään tilaan. Menetelmässä poistetaan neliöiden nurkkia suuruusjärjestyksessä. Ensin 6x6, sitten 5x5:t ja siten 4x4:t ja katsotaan miten käy. Laidoilta ei poisteta mitään, jos ei ole ihan pakko.
6XXXXX
X5X45X
XXX44X
X44XXX
X54X2X
XXXXX4
Jäljelle jäi 24 kpl X-merkittyä. Numero kertoo, miksi poistettiin. Meni ihan mekaanisesti. Oli aina yksi vaihtoehto, joten ei tarvinnut kombinoida. ( Ihan lopussa piti rikkoa sääntöä ja poista alanurkasta yksi. Korvasi kaksi sääntöjen mukaista poistoa.)
Aika symmetrinen kuvio. Ei näyttäisi löytyvän yhtään 2x2 tai 3x3 neliötä. Sain myös täytettyä ruudukkosi ilman virheilmoitusta.Tuo onkin parempi tapa ajatella, että lähdetään poistamaan neliöitä täydestä ruudukosta kuin että lähdetään täyttämään tyhjää ruudukkoa.
Jos lähtee täyttämään rivi kerrallaan aina mahdolliset, niin taitaa syntyä Sierpinskin kolmio -tyyppinen kuvio. Sen dimensiohan on log_2 (3), joten täytettyjen lukumäärää kasvaa kuten n^1.585. Kuinkakohan tämä neliönpoisto-strategia yleiselle n vertautuu tähän?
Parasta mahdollista täyttöä voi olla yleiselle n liian hankala löytää, mutta mitä pystytään sanomaan niiden kasvuvauhdista? Merkitään nxn:n parasta täyttöä f_n:llä. Saadaanko vähintään tietty positiivinen osuus neliöstä täytettyä vai onko lim f_n/n^2 = 0? Mikä siinä tapauksessa on f_n:n oikea kasvunopeus? - Anonyymi
Anonyymi kirjoitti:
Tuo onkin parempi tapa ajatella, että lähdetään poistamaan neliöitä täydestä ruudukosta kuin että lähdetään täyttämään tyhjää ruudukkoa.
Jos lähtee täyttämään rivi kerrallaan aina mahdolliset, niin taitaa syntyä Sierpinskin kolmio -tyyppinen kuvio. Sen dimensiohan on log_2 (3), joten täytettyjen lukumäärää kasvaa kuten n^1.585. Kuinkakohan tämä neliönpoisto-strategia yleiselle n vertautuu tähän?
Parasta mahdollista täyttöä voi olla yleiselle n liian hankala löytää, mutta mitä pystytään sanomaan niiden kasvuvauhdista? Merkitään nxn:n parasta täyttöä f_n:llä. Saadaanko vähintään tietty positiivinen osuus neliöstä täytettyä vai onko lim f_n/n^2 = 0? Mikä siinä tapauksessa on f_n:n oikea kasvunopeus?Kokeile poistaa täynnä olevasta 8x8 ruudukosta ensin suurimman neliön vasen ylänurkka. Sitten kolmen 7x7 neliön yksi nurkka. Etene vasemmalta ylhäältä oikealle alas. Älä poista laidoilta. Kun olet saanut tuhottua myös 6x6 neliöt, niin eteneminen nopeutuu, sillä suurin osa 5x5 neliöistä on jo tuhottu. Ei tarvitse poistaa montakaan 4x4 neliötä.
Yllättäen jäljelle ei jää juuri lainkaan 3x3 neliöitä. Mikä on tuloksesi? Saatko ihan pienellä oikean alanurkka-alueen säädöllä lisättyä yhden poistetun nurkan takaisin?
En ole tehnyt vielä ohjelmaa tähän. Olisi aivan liian yksinkertainen. Luultavasti jopa 100x100 onnistuisi hetkessä ja saisi lähes oikean tuloksen.
Poistot voi merkitä 8x8:ssa vaikka shakkilaudalle nappuloilla.
Alla pienin (binäärilukuna) 6x6 ruudukko. Poistot on merkittu 1:llä.
1 0 0 0 0 0
0 0 1 0 1 0
0 1 1 1 0 0
0 0 1 1 1 0
0 1 0 1 0 0
0 0 0 0 0 1 - Anonyymi
Anonyymi kirjoitti:
Kokeile poistaa täynnä olevasta 8x8 ruudukosta ensin suurimman neliön vasen ylänurkka. Sitten kolmen 7x7 neliön yksi nurkka. Etene vasemmalta ylhäältä oikealle alas. Älä poista laidoilta. Kun olet saanut tuhottua myös 6x6 neliöt, niin eteneminen nopeutuu, sillä suurin osa 5x5 neliöistä on jo tuhottu. Ei tarvitse poistaa montakaan 4x4 neliötä.
Yllättäen jäljelle ei jää juuri lainkaan 3x3 neliöitä. Mikä on tuloksesi? Saatko ihan pienellä oikean alanurkka-alueen säädöllä lisättyä yhden poistetun nurkan takaisin?
En ole tehnyt vielä ohjelmaa tähän. Olisi aivan liian yksinkertainen. Luultavasti jopa 100x100 onnistuisi hetkessä ja saisi lähes oikean tuloksen.
Poistot voi merkitä 8x8:ssa vaikka shakkilaudalle nappuloilla.
Alla pienin (binäärilukuna) 6x6 ruudukko. Poistot on merkittu 1:llä.
1 0 0 0 0 0
0 0 1 0 1 0
0 1 1 1 0 0
0 0 1 1 1 0
0 1 0 1 0 0
0 0 0 0 0 1Tuollainen tuli kynää ja paperia käyttäen 26:lla poistolla ja pienellä säätämisellä:
1 0 0 1 0 0 0 0
0 1 0 0 1 0 1 0
0 0 1 0 1 1 1 0
0 1 1 0 1 1 1 0
0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 0
0 1 1 1 0 1 0 0
0 0 0 0 0 0 0 1
Joku älykäs matemaatikko (tai googlaaja) selviää helposti 25:llä tai vain 24:llä poistolla. Kuka?
q = [1,0,0,1,0,0,0,0,
0,1,0,0,1,0,1,0,
0,0,1,0,1,1,1,0,
0,1,1,0,1,1,1,0,
0,1,1,1,1,0,0,0,
0,0,1,1,0,0,1,0,
0,1,1,1,0,1,0,0,
0,0,0,0,0,0,0,1] - Anonyymi
Anonyymi kirjoitti:
Tuollainen tuli kynää ja paperia käyttäen 26:lla poistolla ja pienellä säätämisellä:
1 0 0 1 0 0 0 0
0 1 0 0 1 0 1 0
0 0 1 0 1 1 1 0
0 1 1 0 1 1 1 0
0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 0
0 1 1 1 0 1 0 0
0 0 0 0 0 0 0 1
Joku älykäs matemaatikko (tai googlaaja) selviää helposti 25:llä tai vain 24:llä poistolla. Kuka?
q = [1,0,0,1,0,0,0,0,
0,1,0,0,1,0,1,0,
0,0,1,0,1,1,1,0,
0,1,1,0,1,1,1,0,
0,1,1,1,1,0,0,0,
0,0,1,1,0,0,1,0,
0,1,1,1,0,1,0,0,
0,0,0,0,0,0,0,1]Ei vaatinut paljoakaan älyä.
Laitoin yksinkertaisen ruudukon tarkistusohjelman tarkistamaan ikuisesti 8x8-ruudukkoja, josta oli poistettu vain vasen ylänurkka ja virheen havaittuaan poistamaan satunnaisesti yhden nurkan ja jatkamaan hommaa. Löytyi paljon 25:ia ja muutamia 24:ia. Lisää löytyy varmasti, jos antaa ohjelman pyöriä muutamassa ikkunassa usean tunnin ajan.
1 1 0 1 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0
0 1 0 1 1 0 0 0
0 0 1 0 1 0 1 0
0 1 1 0 0 0 0 1
0 1 0 0 1 1 0 0
0 0 0 1 0 0 1 0
24
1 0 1 1 0 0 0 0
1 0 0 0 1 0 1 0
0 0 1 0 1 1 0 0
0 1 0 1 0 0 0 1
0 1 0 0 0 1 0 0
0 1 1 1 0 0 1 0
0 0 1 0 1 0 0 1
1 0 0 0 0 0 1 1
24
7x7:sta löytyy ainakin 17:ia ja 9x9:stä 35:ia ja 10x10:stä 45:ia ja 12x12:sta 71:ia ja 16x16:sta 144:ia muutamassa minuutissa. 20x20 ei meinaa päästä millään alle 240 eikä 100x100 alle 8190 eikä 1000x1000 alle 941300. Toimiiko ohjelma väärin vai oikein? Isoissa ruudukoissa täyttöaste näyttäisi pienevän lähes nollaan. - Anonyymi
Anonyymi kirjoitti:
Ei vaatinut paljoakaan älyä.
Laitoin yksinkertaisen ruudukon tarkistusohjelman tarkistamaan ikuisesti 8x8-ruudukkoja, josta oli poistettu vain vasen ylänurkka ja virheen havaittuaan poistamaan satunnaisesti yhden nurkan ja jatkamaan hommaa. Löytyi paljon 25:ia ja muutamia 24:ia. Lisää löytyy varmasti, jos antaa ohjelman pyöriä muutamassa ikkunassa usean tunnin ajan.
1 1 0 1 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0
0 1 0 1 1 0 0 0
0 0 1 0 1 0 1 0
0 1 1 0 0 0 0 1
0 1 0 0 1 1 0 0
0 0 0 1 0 0 1 0
24
1 0 1 1 0 0 0 0
1 0 0 0 1 0 1 0
0 0 1 0 1 1 0 0
0 1 0 1 0 0 0 1
0 1 0 0 0 1 0 0
0 1 1 1 0 0 1 0
0 0 1 0 1 0 0 1
1 0 0 0 0 0 1 1
24
7x7:sta löytyy ainakin 17:ia ja 9x9:stä 35:ia ja 10x10:stä 45:ia ja 12x12:sta 71:ia ja 16x16:sta 144:ia muutamassa minuutissa. 20x20 ei meinaa päästä millään alle 240 eikä 100x100 alle 8190 eikä 1000x1000 alle 941300. Toimiiko ohjelma väärin vai oikein? Isoissa ruudukoissa täyttöaste näyttäisi pienevän lähes nollaan.Joo, täyttöaste menee nollaan eli f_n = o(n^2). Tämän sanoo 2-ulotteinen Szemerédin lause, joka on "hypergraafin poisto lemman" aplikaatio (ks. linkki alemmasta viestistä).
Tässä videossa (luento vuodelta 2019): https://youtu.be/rBUFitIoE14?t=2988 sanotaan, että parempia ylärajoja ei tunneta kielletyn kuvion ollessa neliö. Nurkalle saadaan Fourierin analyysillä yläraja n^2 / (log log n)^c. - Anonyymi
Anonyymi kirjoitti:
Joo, täyttöaste menee nollaan eli f_n = o(n^2). Tämän sanoo 2-ulotteinen Szemerédin lause, joka on "hypergraafin poisto lemman" aplikaatio (ks. linkki alemmasta viestistä).
Tässä videossa (luento vuodelta 2019): https://youtu.be/rBUFitIoE14?t=2988 sanotaan, että parempia ylärajoja ei tunneta kielletyn kuvion ollessa neliö. Nurkalle saadaan Fourierin analyysillä yläraja n^2 / (log log n)^c.Täyttöaste on alle 50 % jo 15x15 ruudukossa. Kokeilkaa täyttää 14x14 ruudukko. Saattaa onnistua vielä yli 50 % täyttöasteella.
Isoilla ruudukoilla kannattaakin aina lähteä täyttäämään sitä eikä tyhjentämään. Pääsee paljon vähemmällä ja näkee aina heti onnistuuko vai ei. Pitää tietysti keksiä joku älykäs tapa aloittaa täyttäminen. Loppu on sitten pajon helpompaa, kun mahdollisuudet vähenevät. Vai onko sen älykkään täyttämisen aloitustavan keksiminen erittäin vaikeaa? Mikä ruutu täytetään ensin ja mikä sitten?
Ruudukossa olevien erikokoisten neliöiden nurkkien määrä kasvaa rajusti ruudukon koon kasvaessa. Lähes jokainen ruudukon ruutu on kymmenien eri neliöden joku nurkka. Tämän vaikutus pystytään kyllä havainnollistamaan ymmärrettävästi ihan peruskoulumatematikallakin ja kuvilla ja animaatioilla tässä erikoistapauksessa. - Anonyymi
Anonyymi kirjoitti:
Ei vaatinut paljoakaan älyä.
Laitoin yksinkertaisen ruudukon tarkistusohjelman tarkistamaan ikuisesti 8x8-ruudukkoja, josta oli poistettu vain vasen ylänurkka ja virheen havaittuaan poistamaan satunnaisesti yhden nurkan ja jatkamaan hommaa. Löytyi paljon 25:ia ja muutamia 24:ia. Lisää löytyy varmasti, jos antaa ohjelman pyöriä muutamassa ikkunassa usean tunnin ajan.
1 1 0 1 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0
0 1 0 1 1 0 0 0
0 0 1 0 1 0 1 0
0 1 1 0 0 0 0 1
0 1 0 0 1 1 0 0
0 0 0 1 0 0 1 0
24
1 0 1 1 0 0 0 0
1 0 0 0 1 0 1 0
0 0 1 0 1 1 0 0
0 1 0 1 0 0 0 1
0 1 0 0 0 1 0 0
0 1 1 1 0 0 1 0
0 0 1 0 1 0 0 1
1 0 0 0 0 0 1 1
24
7x7:sta löytyy ainakin 17:ia ja 9x9:stä 35:ia ja 10x10:stä 45:ia ja 12x12:sta 71:ia ja 16x16:sta 144:ia muutamassa minuutissa. 20x20 ei meinaa päästä millään alle 240 eikä 100x100 alle 8190 eikä 1000x1000 alle 941300. Toimiiko ohjelma väärin vai oikein? Isoissa ruudukoissa täyttöaste näyttäisi pienevän lähes nollaan.Löytyi 8x8 ruudukko, jossa 41 ruutua on täytetty( eli 23 poistettu).
1 0 0 0 0 0 0 0
0 1 1 0 1 0 1 0
0 1 1 0 1 1 0 0
0 0 0 0 1 1 1 0
0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 0
0 1 0 1 0 1 0 0
0 0 0 0 0 0 0 1
23
Muodostuu kaunis kuvio. Hakekaa sellainen Googlen kuvahaulla. Varmasti löytyy, jos osaa hakea.
Joku älykäs matemaatikko pystyy varmasti käymään läpi kaikki mahdolliset kombinaatiot. Ei niitä ole rajattomasti, jos keksii algoritmin, joka rajoittaa jokaisen poiston (tai lisäyksen) jälkeen hakua maksimaalisesti. Kolmesta 7-neliöstä voidaan poistaa yksi nurkka 4^3=64 tavalla. Eli tehtävä supistuu 64:ään huomattavasti helpompaan osatehtävään. Niistä voidaan poistaa 6-neliöt jne... Ei tietysti ihan näin suoraviivaisesti, vaan jotenkin paljon älykkäämmin. - Anonyymi
Anonyymi kirjoitti:
Täyttöaste on alle 50 % jo 15x15 ruudukossa. Kokeilkaa täyttää 14x14 ruudukko. Saattaa onnistua vielä yli 50 % täyttöasteella.
Isoilla ruudukoilla kannattaakin aina lähteä täyttäämään sitä eikä tyhjentämään. Pääsee paljon vähemmällä ja näkee aina heti onnistuuko vai ei. Pitää tietysti keksiä joku älykäs tapa aloittaa täyttäminen. Loppu on sitten pajon helpompaa, kun mahdollisuudet vähenevät. Vai onko sen älykkään täyttämisen aloitustavan keksiminen erittäin vaikeaa? Mikä ruutu täytetään ensin ja mikä sitten?
Ruudukossa olevien erikokoisten neliöiden nurkkien määrä kasvaa rajusti ruudukon koon kasvaessa. Lähes jokainen ruudukon ruutu on kymmenien eri neliöden joku nurkka. Tämän vaikutus pystytään kyllä havainnollistamaan ymmärrettävästi ihan peruskoulumatematikallakin ja kuvilla ja animaatioilla tässä erikoistapauksessa.Tuossa on 20x20 ruudukko, josta on poistettu 200. Täyttöaste 50 %.
1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0
0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1
0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0
1 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1
0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0
0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1
0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0
0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1
1 0 1 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0
1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 0 1
0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1
0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 0
0 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1
1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0
1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0
0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1
0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0
1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1
0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0
20 200
Ja 15x15 ruudukko, josta on poistettu 102. Täyttöaste 54,7 %.
1 0 1 1 0 0 0 1 0 0 0 1 1 0 0
1 0 0 1 0 1 0 0 0 1 0 0 0 1 1
1 0 1 0 1 0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 1 1 0 1 0 0 0 1 1 0
1 1 0 1 1 0 0 0 0 1 1 1 0 0 1
0 0 0 1 0 0 1 1 1 1 1 0 0 1 0
0 1 0 0 1 0 0 1 1 1 0 1 1 0 0
0 0 1 0 1 0 1 1 1 0 0 1 0 0 1
1 1 0 0 0 1 1 1 0 1 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0 1 0 0 1 1
1 0 1 0 0 0 0 1 0 1 1 0 1 0 1
0 0 1 1 0 1 0 0 0 1 0 1 0 1 0
0 1 0 0 0 1 1 0 1 1 0 1 0 0 1
0 1 0 1 0 0 1 0 1 0 0 0 1 0 0
0 0 1 0 1 1 0 0 0 0 1 0 0 0 1
15 102
Ja 10x10 ruudukko. Poistettu 40.
1 0 0 0 1 0 0 1 0 1
1 0 1 0 0 0 1 0 0 0
1 0 0 1 0 1 0 0 1 0
0 1 0 0 0 1 1 0 0 1
0 0 1 0 1 1 0 1 0 0
0 1 1 1 1 0 0 0 0 1
1 1 0 0 1 0 1 0 1 0
0 1 0 1 1 0 1 1 0 0
0 0 0 0 0 1 0 1 1 0
0 1 1 1 0 0 0 0 0 0
10 40
Tyhmääkin tyhmepi ohjelma tekee listan kaikkien neliöiden nurkista ja poistaa aina sen ruudun, jossa on eniten nurkkia. Jokaisen poiston jälkeen listaa päiviteään eli siitä poistetaan (maskataan) kaikki ne neliöt, joiden yksikin nurkka on poistetussa ruudussa. Sitten lasketaan uudet nurkkien määrät jäljellä olevista neliöistä. Jos useassa ruudussa on sama maksimimäärä nurkkia, valitaan joku niistä satunnaisesti. Yllättävän nopea ja tehokas pienillä ruudukoila ilman mitää optimointeja tai jälkikäsittelyjä.
Toimii hitaasti 100x100 ruudukossa. Ehkä n. minuutti jokaista kierrosta kohti. Paras tulos tähän asti on 6819 poistoa eli n. 32 % täyttöaste. - Anonyymi
Anonyymi kirjoitti:
Tuossa on 20x20 ruudukko, josta on poistettu 200. Täyttöaste 50 %.
1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0
0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1
0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0
1 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1
0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0
0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1
0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0
0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1
1 0 1 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0
1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 0 1
0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1
0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 0
0 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1
1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0
1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0
0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1
0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0
1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1
0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0
20 200
Ja 15x15 ruudukko, josta on poistettu 102. Täyttöaste 54,7 %.
1 0 1 1 0 0 0 1 0 0 0 1 1 0 0
1 0 0 1 0 1 0 0 0 1 0 0 0 1 1
1 0 1 0 1 0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 1 1 0 1 0 0 0 1 1 0
1 1 0 1 1 0 0 0 0 1 1 1 0 0 1
0 0 0 1 0 0 1 1 1 1 1 0 0 1 0
0 1 0 0 1 0 0 1 1 1 0 1 1 0 0
0 0 1 0 1 0 1 1 1 0 0 1 0 0 1
1 1 0 0 0 1 1 1 0 1 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0 1 0 0 1 1
1 0 1 0 0 0 0 1 0 1 1 0 1 0 1
0 0 1 1 0 1 0 0 0 1 0 1 0 1 0
0 1 0 0 0 1 1 0 1 1 0 1 0 0 1
0 1 0 1 0 0 1 0 1 0 0 0 1 0 0
0 0 1 0 1 1 0 0 0 0 1 0 0 0 1
15 102
Ja 10x10 ruudukko. Poistettu 40.
1 0 0 0 1 0 0 1 0 1
1 0 1 0 0 0 1 0 0 0
1 0 0 1 0 1 0 0 1 0
0 1 0 0 0 1 1 0 0 1
0 0 1 0 1 1 0 1 0 0
0 1 1 1 1 0 0 0 0 1
1 1 0 0 1 0 1 0 1 0
0 1 0 1 1 0 1 1 0 0
0 0 0 0 0 1 0 1 1 0
0 1 1 1 0 0 0 0 0 0
10 40
Tyhmääkin tyhmepi ohjelma tekee listan kaikkien neliöiden nurkista ja poistaa aina sen ruudun, jossa on eniten nurkkia. Jokaisen poiston jälkeen listaa päiviteään eli siitä poistetaan (maskataan) kaikki ne neliöt, joiden yksikin nurkka on poistetussa ruudussa. Sitten lasketaan uudet nurkkien määrät jäljellä olevista neliöistä. Jos useassa ruudussa on sama maksimimäärä nurkkia, valitaan joku niistä satunnaisesti. Yllättävän nopea ja tehokas pienillä ruudukoila ilman mitää optimointeja tai jälkikäsittelyjä.
Toimii hitaasti 100x100 ruudukossa. Ehkä n. minuutti jokaista kierrosta kohti. Paras tulos tähän asti on 6819 poistoa eli n. 32 % täyttöaste.Kokeilin simuloitua jäähdytystä (Simulated Annealing). Koodit ja tulokset tuolla: https://pastebin.com/zkiZgCDQ
Hieman sain parannusta noihin löytämiisi. Minulla ratkaisuruudukossa 1=täytetty ja 0=tyhjä. Tässä lukumäärät kuinka moni ruutu löydetyssä ratkaisussa täytetty:
n=10: 60 [tämä oli sama arvo]
n=20: 203
n=100: 3243
Vähän jopa yllätyin kun ajon ihan lopussa alkoi tulemaan noinkin hyviä tuloksia vaikka aluksi junnataan pitkään ihan huonoissa. Mutta niin se SA-algoritmi toimii, että se "hitaasti jäähtyy" kohti parempia ratkaisuja. Tiedä sitten tosin kuinka lähellä nuo todellista optimia vielä ovat, varsinkaan tuo n=100. Voisihan sitä kokeilla vielä suuremmalla iteraatiomäärällä jos viitsii. Tuossa minulla oli 10^8 ja se vei 4,5 tuntia. - Anonyymi
Anonyymi kirjoitti:
Kokeilin simuloitua jäähdytystä (Simulated Annealing). Koodit ja tulokset tuolla: https://pastebin.com/zkiZgCDQ
Hieman sain parannusta noihin löytämiisi. Minulla ratkaisuruudukossa 1=täytetty ja 0=tyhjä. Tässä lukumäärät kuinka moni ruutu löydetyssä ratkaisussa täytetty:
n=10: 60 [tämä oli sama arvo]
n=20: 203
n=100: 3243
Vähän jopa yllätyin kun ajon ihan lopussa alkoi tulemaan noinkin hyviä tuloksia vaikka aluksi junnataan pitkään ihan huonoissa. Mutta niin se SA-algoritmi toimii, että se "hitaasti jäähtyy" kohti parempia ratkaisuja. Tiedä sitten tosin kuinka lähellä nuo todellista optimia vielä ovat, varsinkaan tuo n=100. Voisihan sitä kokeilla vielä suuremmalla iteraatiomäärällä jos viitsii. Tuossa minulla oli 10^8 ja se vei 4,5 tuntia.Pastebin ei näyttäisi toimivan ainakaan ilman kirjautumista.
10x10 ruudukko ratkesi 39 poistolla eli 61 lisäystä. Tulee aina sama ruudukko tai se käännettynä 180 astetta. Merkki siitä, ettei ole parempaa. Sama juttu on 8x8:n kanssa. Aina tulee kaksi peilikuvaa. (23 poistoa tai 41 lisäystä.) Poistot merkitty 0:lla.
0 1 0 1 0 1 1 1 1 0
1 1 1 1 0 1 0 1 0 1
1 0 1 0 1 0 0 1 1 1
0 1 1 0 1 1 1 0 0 1
1 1 0 0 1 0 1 0 1 1
1 0 1 0 0 1 1 1 0 0
1 1 1 1 0 0 0 0 1 1
1 0 0 1 1 0 1 1 1 0
1 0 0 1 0 1 1 0 1 1
0 1 1 1 1 1 0 1 1 0
10x10 39 61
[0,1,0,1,0,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,0]
Laitoin tyhmän ohjelmani tarkistamaan aina lopussa, montako alussa tehtyä poistoa osoittautuu turhiksi myöhemmin tehtyjen poistojen vuoksi. Usein saa lisätty muutaman alussa tehdyn poiston takaisin. Helppoa! Pääsee aina todella nopeasti lähelle optimia.
20x20 ruudukkoja tuli erilaisia 203 lisäyksellä. Ei vielä yhtään parempaa. 100x100 ruudukossa en päässyt kuin 3238 lisäykseen (6762 poistoa). Liian hidasta. Hidastuu neliöllisesti poistojen kasvaessa. Kokeilin vain muutama tuhat kertaa. Pitää joskus muuttaa ohjelma tekemään lisäyksiä isoilla ruudukoilla. - Anonyymi
Anonyymi kirjoitti:
Pastebin ei näyttäisi toimivan ainakaan ilman kirjautumista.
10x10 ruudukko ratkesi 39 poistolla eli 61 lisäystä. Tulee aina sama ruudukko tai se käännettynä 180 astetta. Merkki siitä, ettei ole parempaa. Sama juttu on 8x8:n kanssa. Aina tulee kaksi peilikuvaa. (23 poistoa tai 41 lisäystä.) Poistot merkitty 0:lla.
0 1 0 1 0 1 1 1 1 0
1 1 1 1 0 1 0 1 0 1
1 0 1 0 1 0 0 1 1 1
0 1 1 0 1 1 1 0 0 1
1 1 0 0 1 0 1 0 1 1
1 0 1 0 0 1 1 1 0 0
1 1 1 1 0 0 0 0 1 1
1 0 0 1 1 0 1 1 1 0
1 0 0 1 0 1 1 0 1 1
0 1 1 1 1 1 0 1 1 0
10x10 39 61
[0,1,0,1,0,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,0]
Laitoin tyhmän ohjelmani tarkistamaan aina lopussa, montako alussa tehtyä poistoa osoittautuu turhiksi myöhemmin tehtyjen poistojen vuoksi. Usein saa lisätty muutaman alussa tehdyn poiston takaisin. Helppoa! Pääsee aina todella nopeasti lähelle optimia.
20x20 ruudukkoja tuli erilaisia 203 lisäyksellä. Ei vielä yhtään parempaa. 100x100 ruudukossa en päässyt kuin 3238 lisäykseen (6762 poistoa). Liian hidasta. Hidastuu neliöllisesti poistojen kasvaessa. Kokeilin vain muutama tuhat kertaa. Pitää joskus muuttaa ohjelma tekemään lisäyksiä isoilla ruudukoilla.Sain hiukan parannettua 14x14 ja 15x15 ruudukkoja. Joitakin ruudukkoja olen laskenut vain alle tunnin.
2x2: 3 (1)
3x3: 7 (2)
4x4: 12 (4)
5x5: 17 (8)
6x6: 24 (12)
7x7: 32 (17)
8x8: 41 (23)
9x9: 51 (30)
10x10: 61 (39)
11x11: 72 (49)
12x12: 84 (60)
13x13: 96 (73)
14x14: 110 (86)
15x15: 124 (101)
16x16: 138 (118)
Joku on nuo varmasti aiemminkin laskenut (ja päässyt parempiinkin lukemiin), mutta Google ei taaskaan suostu näyttäämään yhtikäs mitään. Ei edes 8x8 ruudukon pikseli-kuvalla hakien. Suuremmat kuin 6x6 ovat ehkä olleet liian vaikeita ennen tehokkaita tietokoneita. - Anonyymi
Anonyymi kirjoitti:
Sain hiukan parannettua 14x14 ja 15x15 ruudukkoja. Joitakin ruudukkoja olen laskenut vain alle tunnin.
2x2: 3 (1)
3x3: 7 (2)
4x4: 12 (4)
5x5: 17 (8)
6x6: 24 (12)
7x7: 32 (17)
8x8: 41 (23)
9x9: 51 (30)
10x10: 61 (39)
11x11: 72 (49)
12x12: 84 (60)
13x13: 96 (73)
14x14: 110 (86)
15x15: 124 (101)
16x16: 138 (118)
Joku on nuo varmasti aiemminkin laskenut (ja päässyt parempiinkin lukemiin), mutta Google ei taaskaan suostu näyttäämään yhtikäs mitään. Ei edes 8x8 ruudukon pikseli-kuvalla hakien. Suuremmat kuin 6x6 ovat ehkä olleet liian vaikeita ennen tehokkaita tietokoneita.Ai, ei mulla pastebin kirjautumisia vaadi ja toimii toisellakin koneella. Chromea käytän selaimena.
No, laitoin kMax=1e9 menemään ja löytyi
n=100: 3334
Tässä, jos saat näkymään: https://pastebin.com/MtKbvX7W on samat koodit kuin edellisessä ja tämä uusi tulos. - Anonyymi
Anonyymi kirjoitti:
Ai, ei mulla pastebin kirjautumisia vaadi ja toimii toisellakin koneella. Chromea käytän selaimena.
No, laitoin kMax=1e9 menemään ja löytyi
n=100: 3334
Tässä, jos saat näkymään: https://pastebin.com/MtKbvX7W on samat koodit kuin edellisessä ja tämä uusi tulos.Jotain vilahti 0,1 sekunnin ajaksi. Eli uBlock Origin hoiti homman aika nopeasti. Sen kun disabloi, alkoi näkyä.
Jokaiseen ruutuun liittyvien neliöiden kolme muuta nurkkaa ovat aina vakiopaikoissa. Niistä voi tehdä ohjelman alussa listan jokaista ruutua varten. [[a,b,c],...]. Turha pyöriä työläissä pikkusilmukoissa miljardeja kertoja. Kerta riittää! Muisti tietysti loppuu paljon yli 100x100 ruudukoissa.
Kuinka paljon parempi ohjelmasi on tyhmään poisto-ohelmaan verrattuna 50x50 ruudukossa? Sain parhaksi tulokseksi 974 lisäystä (1526 poistoa) Yhteensä n. 14000 yritystä. Aikaa vajaa tunti neljällä ytimellä. Toiseksi paras oli 972. - Anonyymi
Anonyymi kirjoitti:
Ai, ei mulla pastebin kirjautumisia vaadi ja toimii toisellakin koneella. Chromea käytän selaimena.
No, laitoin kMax=1e9 menemään ja löytyi
n=100: 3334
Tässä, jos saat näkymään: https://pastebin.com/MtKbvX7W on samat koodit kuin edellisessä ja tämä uusi tulos.Saatko 25x25:lle paremman kuin 297 lisättyä? (Poistot merkitty 1:llä.)
1,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,
1,0,1,1,1,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,1,0,0,1,0,
0,0,0,1,0,1,0,1,1,1,1,0,0,1,0,1,1,1,0,1,0,0,1,1,0,
0,1,0,0,1,0,0,0,1,1,1,1,0,0,1,0,1,1,0,0,0,1,1,1,0,
1,0,0,1,1,1,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,1,0,0,0,
1,1,0,0,0,1,0,0,1,1,1,0,0,0,1,1,1,0,1,0,0,1,0,1,1,
0,0,1,1,1,0,1,0,0,0,0,1,1,1,0,1,1,0,1,0,1,0,0,1,1,
1,0,0,0,1,0,1,1,1,0,1,0,0,1,1,1,1,0,1,1,1,1,0,0,1,
0,1,0,1,0,1,1,1,1,0,0,1,0,0,1,0,1,0,1,1,1,0,0,1,0,
0,0,0,1,0,0,1,0,1,0,1,1,0,1,1,1,1,0,1,1,0,0,1,0,0,
0,1,1,0,1,1,0,1,0,0,0,1,1,1,1,1,0,0,1,1,0,1,1,1,0,
1,1,1,0,0,1,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,0,
0,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,1,0,0,0,1,0,1,0,
1,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,1,1,0,1,0,0,0,0,1,
0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,1,0,0,
0,1,0,1,1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,0,0,1,1,1,
1,0,1,1,1,1,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,
1,1,1,0,0,0,1,0,1,1,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,
0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,0,1,0,0,0,
0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,
1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,0,0,1,0,1,1,1,1,0,1,
0,1,0,1,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,0,1,1,0,0,0,
0,1,0,0,1,1,1,0,0,0,1,0,0,1,0,1,1,1,0,1,1,0,0,1,0,
1,0,1,0,0,0,0,1,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,0,0,
0,1,1,1,0,1,1,1,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,1]
25 297 (328) - Anonyymi
Anonyymi kirjoitti:
Jotain vilahti 0,1 sekunnin ajaksi. Eli uBlock Origin hoiti homman aika nopeasti. Sen kun disabloi, alkoi näkyä.
Jokaiseen ruutuun liittyvien neliöiden kolme muuta nurkkaa ovat aina vakiopaikoissa. Niistä voi tehdä ohjelman alussa listan jokaista ruutua varten. [[a,b,c],...]. Turha pyöriä työläissä pikkusilmukoissa miljardeja kertoja. Kerta riittää! Muisti tietysti loppuu paljon yli 100x100 ruudukoissa.
Kuinka paljon parempi ohjelmasi on tyhmään poisto-ohelmaan verrattuna 50x50 ruudukossa? Sain parhaksi tulokseksi 974 lisäystä (1526 poistoa) Yhteensä n. 14000 yritystä. Aikaa vajaa tunti neljällä ytimellä. Toiseksi paras oli 972.Sain nopeutettua tyhmää poisto-ohjelmaa 100x100 ruudukolla 45 kertaa nopeammaksi tekemällä ruutukohtaisen listan tähän ruutuun liittyvien neliöiden indekseistä isossa neliötaulukossa. Neliöitä on noin 330000 ja yksittäiseen ruutuun liittyy vain muutamia kymmenniä ruutuja. 50x50 ruudukon laskenta nopeutui n. 30 kertaiseksi. Ihan pienemmissä ruudukoissakin nopeus tuplaantui. Ja ohjelma yksinkertaistui.
Ohjelma onnistui saamaan 50x50 ruudukkoon 980 lisäystä (1520 poistoa). Vaikea parantaa älykkäällä ohjelmilla! Myös neljä pienempää ruudukkoa parantui yhdellä ihan vaan jo ohjelman toiminnan varmistamisen yhteydessä.
11x11: 72 (48) ( 1)
12x12: 84 (60)
13x13: 96 (72) ( 1)
14x14: 110 (86)
15x15: 124 (100) ( 1)
16x16: 138 (117) ( 1)
25x25 ruudukko (297 lisäystä) ei parantunut (vielä) yhtään. Miksei? - Anonyymi
Anonyymi kirjoitti:
Sain nopeutettua tyhmää poisto-ohjelmaa 100x100 ruudukolla 45 kertaa nopeammaksi tekemällä ruutukohtaisen listan tähän ruutuun liittyvien neliöiden indekseistä isossa neliötaulukossa. Neliöitä on noin 330000 ja yksittäiseen ruutuun liittyy vain muutamia kymmenniä ruutuja. 50x50 ruudukon laskenta nopeutui n. 30 kertaiseksi. Ihan pienemmissä ruudukoissakin nopeus tuplaantui. Ja ohjelma yksinkertaistui.
Ohjelma onnistui saamaan 50x50 ruudukkoon 980 lisäystä (1520 poistoa). Vaikea parantaa älykkäällä ohjelmilla! Myös neljä pienempää ruudukkoa parantui yhdellä ihan vaan jo ohjelman toiminnan varmistamisen yhteydessä.
11x11: 72 (48) ( 1)
12x12: 84 (60)
13x13: 96 (72) ( 1)
14x14: 110 (86)
15x15: 124 (100) ( 1)
16x16: 138 (117) ( 1)
25x25 ruudukko (297 lisäystä) ei parantunut (vielä) yhtään. Miksei?Lisäysten määrät unohtui päivittää.
11x11: 73 (48)
12x12: 84 (60)
13x13: 97 (72)
14x14: 110 (86)
15x15: 125 (100)
16x16: 139 (117)
1,1,0,0,0,0,1,0,0,0,0,0,1,1,0,
1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,
0,0,1,0,1,1,1,0,0,1,1,0,0,0,0,
1,0,0,1,1,1,0,1,0,0,0,1,0,1,0,
1,1,0,0,1,0,0,1,0,1,0,0,0,1,1,
0,0,1,1,0,1,1,0,0,1,1,1,0,0,1,
0,1,0,0,0,1,1,1,1,1,1,0,0,1,0,
1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,
0,0,1,1,1,0,1,1,0,0,0,0,1,0,1,
1,0,1,0,0,0,1,0,1,1,1,0,0,0,1,
0,0,0,0,1,0,0,0,1,1,0,1,1,0,0,
0,1,1,1,0,1,1,0,0,0,0,1,0,1,0,
0,1,1,1,0,0,0,1,0,1,0,0,0,0,0,
0,0,0,1,0,1,0,1,1,0,0,1,1,1,0,
0,1,0,1,1,0,1,0,0,0,1,1,1,0,0]
15x15 125 (100) - Anonyymi
Itse löysin nopeutuneella ohjelmalla 20x20:lle vain 304 ja 100x100:lle vain 3265, joten ohjelmasi on selvästi parempi yli 16x16 ruudukoissa.
Muutamissa pienissä ruudukoissakin on varmasti hiukan parantamista. Vaihtoehtoja on niissäkin lähes ääretön määrä. Tyhmä lähes mekaanisesti tomiva ohjelmani ei ehkä käy joitakin vaihtoehtoja läpi koskaan, vaikka ohjemaa ajaisi ikuisesti. Pitänee lisätä alkuun hiukan kaikki isoimpien neliöiden (huonotkin) vaihtoehdot läpikäyvää kombinointia. - Anonyymi
Anonyymi kirjoitti:
Itse löysin nopeutuneella ohjelmalla 20x20:lle vain 304 ja 100x100:lle vain 3265, joten ohjelmasi on selvästi parempi yli 16x16 ruudukoissa.
Muutamissa pienissä ruudukoissakin on varmasti hiukan parantamista. Vaihtoehtoja on niissäkin lähes ääretön määrä. Tyhmä lähes mekaanisesti tomiva ohjelmani ei ehkä käy joitakin vaihtoehtoja läpi koskaan, vaikka ohjemaa ajaisi ikuisesti. Pitänee lisätä alkuun hiukan kaikki isoimpien neliöiden (huonotkin) vaihtoehdot läpikäyvää kombinointia.Viiskymppiselle tuli 1014.
- Anonyymi
Anonyymi kirjoitti:
Viiskymppiselle tuli 1014.
Iso parannus.
Sain 16x16 ruudukolle 140 lisäystä. Saatko 5 enemän? Lisäykset merkitty 1:llä.
0,1,1,1,1,1,0,0,1,0,0,0,1,1,0,1,
1,1,0,1,0,1,1,1,1,0,0,1,0,1,0,1,
0,1,1,0,0,0,1,0,1,0,1,1,1,0,1,1,
0,0,1,1,1,0,0,1,1,1,1,0,0,1,1,0,
1,1,1,0,1,0,1,1,0,1,0,0,1,1,0,1,
1,0,0,1,1,1,1,0,0,0,1,0,0,1,0,1,
0,1,1,1,0,1,0,1,0,0,0,1,1,1,1,0,
1,0,0,1,1,0,0,0,0,1,0,1,0,0,1,1,
1,0,1,0,0,1,0,0,0,1,1,1,1,0,0,1,
1,1,1,1,0,0,0,0,0,0,1,0,0,1,1,1,
0,1,0,1,1,0,0,0,1,0,0,1,1,0,0,1,
1,0,0,1,0,1,0,0,1,1,1,1,0,0,1,0,
1,1,1,0,1,1,1,0,1,0,1,0,0,0,1,1,
1,0,1,1,1,0,1,1,0,0,1,1,1,0,0,0,
1,1,0,0,1,1,0,1,0,1,1,0,1,0,1,0,
1,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1]
16x16 140 (116)
- Anonyymi
Tässä hieman tietoja tuosta asymptoottisesta kasvusta, joita sain eri lähteistä kerättyä. Merkitään f_n = #ruutuja parhaassa neliöttömässä nxn täytössä.
f_n = o(n^2)
Lähde: https://en.wikipedia.org/wiki/Hypergraph_removal_lemma#Applications
Lisätään joukkoon S alkio (1, 1), jolloin kyseeseen tulee neliöt.
f_n >= C e^(-c*sqrt(log n)) * n^2, joillekin vakioille C>0 ja c>0.
Perustelu: Linkin https://planetmath.org/behrendsconstruction mukaan löydetään vähintään kokoa e^(-c*sqrt(n)) * n oleva joukon {1,2,...,n} (merk. [n]) osajoukko, jossa ei ole 3 termistä aritmeettista jonoa. Olkoon A tällainen [2n]:n joukko. Muodostetaan nyt ruudukon [2n]^2 osajoukko B = {(x,y) | x-y ϵ A}. Tämä on jopa "neliön nurkaton" eli se ei sisällä mitään kolmikkoa (x, y d), (x, y), (x d, y). Tämä johtuu siitä, että tuollainen kolmikko B:ssä tarkoittaisi, että A:ssa piti olla kolmiterminen aritmeettinen jono x-y-d, x-y, x-y d. Nyt joukko B on halutunisoinen, koska jokaisen A:n alkion päälle tulee diagonaalinen suora, joten se täyttää pystysuunnassa positiivisen osan ruudukosta (vakio C) ja lopputermi tulee siitä miten paljon A täyttää vaakasuunnassa. Tässä oli B:lle 2n ja A:lle n, mutta aiheutuva termi voidaan vetää vakioon c.
Näin siis nähdään että f_n on asymptoottiselta kasvultaan pienempää kuin n^2 mutta suurempaa kuin n^t millekään t<2. - Anonyymi
Tästähän tulikin mielenkiintoinen aihe, vähän kuin oma salakirjoitusmetodi sotkea tuolla tavoin kirjaimia ja numjeroita :D:D
- Anonyymi
Tiedättekö muuten miten lasketaan Piin desimaaleja oikein pitkälle, se on yksinkertainen kaava mutta vaatii enemmän ruutupaperia.
1=NNNORX? olisi= 1=nand,nand,nand-or-xor eli vastaus nolla :D - Anonyymi
Jos sotket jotain digitaalitekniikan loogisia operaattoreita vaikka X merkkinä XOR eli NAND operaattori eli se ottaisi sen arvonsa sitten X-suuntaisesti viereisistä numeroista silloin... tulisi jo aika monimutkainen salakirjoitusmetodi.
- Anonyymi
Tee kolmiulotteinen ruudukko, silloin syntyisi vain kuutioita, ei neliöitä.
Sitten joissain 3d-laskuissa voisit käyttää jotain grafiikkakiihdyttimen ominaisuuksia, valmiiksi laskettuja monimutkaisia vektori-väännöksiä, joita ei viitsisi kirjoittaa ruutupaperille lyijykynän kanssa.- Anonyymi
Szemèredin lause puree myös kuutioihin. Itse asiassa otettiinpa mikä tahansa äärellinen kuvio S, niin d-ulotteisen [n]^d-ruudukon osajoukko, josta tätä kuviota ei löydy, on kooltaan o(n^d) eli sen täyttöaste menee nollaan, kun n menee äärettömään.
- Anonyymi
Yritän todistaa, että 8x8 ruudukolle löytyy vain yksi paras ratkaisu 41-lisäyksellä (23-poistolla). Kokeilen ensin ohjelman optimointia 7x7 ruudukolla.
Tein silmukkaohjelman, joka käy läpi kaikki 7x7 ruudukon mahdollisuudet. Aikaa kuluu yhdellä ytimellä alle 5 minuutia. Löytyy 17:llä poistolla 28 erilaista, joista 12 on 180 astetta käännettyjä. Ei löydy yhtään 16:lla poistolla.
Ruudukon vasen ylänurkka on aina poistettuna. Ohjelma hakee ensin 10 neliötä, joilla ei ole yhtään yhteistä nurkkaa. (Löytyy 29 erilaista mahdollisuutta. Voi valita ensimmäisen löydetyn.) Jokaisesta neliöstä valitaan yksi nurkka. Kombinaatioita siis 4^10 kpl. Ratkaisussa on pakko olla mukana jotkut näistä kombinaatioista.
Sitten ohjelma tekee listan kaikista jäljellä olevista ehjistä neliöistä ja valitsee seuravaaksi kombinoitavaksi niistä aina ensimmäisen ehjän. Tätä jatketaan kuudella silmukka tasolla. (1 10 6 = 17). Kaikki ratkaisut löytyvät täysin varmasti. Ja löytyvät moneenkin kertaan. On keksi parempaa järkevää kombinointitapaa, jolla tämän voisi välttää.
Koko ruudukkoa voidaan kuvata yhdellä (49-bittisellä) luvulla (x). Jokainen ehjä neliö on luku (y), jossa on 4 kpl 1-bittiä ja muut 0-bittejä. Tarkistukseen riittää aina vain yksi and-opetaatio. (If x&y==y:). Jokaisen valinnan yhteydessä x:ää päivitetään valitussa kohdaas olevalla 1-bitillä xor-operaatiolla (nollaus) ja sitten takaisin 1:ksi vastaavalla or-operaatiolla. Yksinkertaista ja super-nopeaa.
Ratkaisuja ovat esim. 269651365523190, 140381976712950 ja 351625697646586. Vasen ylänurkka on vähiten merkitsevä bitti. Nopeuttaa laskentaa.
Tuossa yksi tapa valita 10 erinurkkaista neliötä 7x7 ruudukosta. Vasenta ylänurkkaa ei saa käyttää. Kokeilkaa valita 11 neliötä.
x 0 1 _ 0 _ 1
2 3 2 4 _ 4 3
5 _ 6 7 5 6 7
2 0 2 4 0 4 _
8 8 1 9 _ 9 1
8 8 6 7 _ 6 7
5 3 _ 9 5 9 3
8x8 ruudukossa saa valittua vastaavasti 15 erinurkkaista neliötä. Niiden nurkat saa kombinoitua 4^15 tavalla (n. miljardi). Sitten vaan pitää kombinoida 7 ehjää neliötä lisää eli yhteensä 4^22. Ei mahdotonta ajan kanssa. Helppo jakaa useille ytimille. Jos ratkaisuja on, niin ne löytyvät aina useaan kertaan.- Anonyymi
Kyllä 41 on kasille maksimi. Siitä voi tehdä lineaarisen kokonaislukuoptimointi ongelman. Tässä Sage-koodi: https://pastebin.com/3uw6i3Nf
Kasi meni vielä aika nopeaan. Ei tainnut mennä minuuttiakaan. Laitoin ysin pyörimään mutta se ei taida ihan hetkessä mennä. - Anonyymi
Anonyymi kirjoitti:
Kyllä 41 on kasille maksimi. Siitä voi tehdä lineaarisen kokonaislukuoptimointi ongelman. Tässä Sage-koodi: https://pastebin.com/3uw6i3Nf
Kasi meni vielä aika nopeaan. Ei tainnut mennä minuuttiakaan. Laitoin ysin pyörimään mutta se ei taida ihan hetkessä mennä.En lukenutkaan tarpeeksi tarkkaan.. Siis että vain yksi ratkaisu. Tarkoitatko kiertoja heijastuksia vaille? Saman (kierretyn) ratkaisun löytää Sagekin MIP:n ratkaisuna. En tiedä saisiko sitä laitettua löytämään kaikki mahdolliset optimiratkaisut.
- Anonyymi
Anonyymi kirjoitti:
En lukenutkaan tarpeeksi tarkkaan.. Siis että vain yksi ratkaisu. Tarkoitatko kiertoja heijastuksia vaille? Saman (kierretyn) ratkaisun löytää Sagekin MIP:n ratkaisuna. En tiedä saisiko sitä laitettua löytämään kaikki mahdolliset optimiratkaisut.
Eli tämän: https://imgur.com/rQecJNU
Heijastuksethan tuossa eivät taida vaikuttaa kun on peilisymmetrinen vinodiagonaalin suhteen. Eli olisi vain neljä eri ratkaisua...? - Anonyymi
Anonyymi kirjoitti:
Kyllä 41 on kasille maksimi. Siitä voi tehdä lineaarisen kokonaislukuoptimointi ongelman. Tässä Sage-koodi: https://pastebin.com/3uw6i3Nf
Kasi meni vielä aika nopeaan. Ei tainnut mennä minuuttiakaan. Laitoin ysin pyörimään mutta se ei taida ihan hetkessä mennä.No nyt oli ysikin pyörinyt loppuun. Maksimi on 51:
[[0, 1, 1, 1, 1, 0, 1, 1, 0], [1, 1, 0, 0, 1, 0, 0, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 0], [1, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 0, 1, 1, 1, 1, 0, 1], [1, 1, 0, 1, 0, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 0, 1, 1], [1, 1, 1, 0, 1, 0, 1, 0, 1], [0, 1, 0, 1, 1, 1, 1, 1, 0]] - Anonyymi
Anonyymi kirjoitti:
Eli tämän: https://imgur.com/rQecJNU
Heijastuksethan tuossa eivät taida vaikuttaa kun on peilisymmetrinen vinodiagonaalin suhteen. Eli olisi vain neljä eri ratkaisua...?Ei kuvan käännöt ole mitään erillisiä ratkaisuja. Ei ainakaan matemaattisesti. Kannattaa valita vasen ylänurkka aina poistetuksi. Vähentää samoja käännettyjä tai väännettyjä ratkaisuja.
- Anonyymi
Anonyymi kirjoitti:
Ei kuvan käännöt ole mitään erillisiä ratkaisuja. Ei ainakaan matemaattisesti. Kannattaa valita vasen ylänurkka aina poistetuksi. Vähentää samoja käännettyjä tai väännettyjä ratkaisuja.
9x9 ruudukon maksimin todistaminen kombinoimalla lienee käytännössä mahdotonta tai ainakin liian kallista. Ehkä 10...20 vuoden päästä voisi yrittää.
Miksei 8x8 ruudukon ratkaisuja tai edes koko tehtävää löydy Googlella? On ollut varmasti ihan yleinen ongelmakulmatehtävä vuosisatoja. Pitäisi tietää joku avainsana tai nimi.
Kokeile täyttää 20x20 (tai 19x19 tai edes 18x18) ruudukko ihan täyteen punaisilla ja sinisillä ruuduilla siten, ettei minkään neliön kaikki 4 nurkkaa ole samaa väriä. Yli 20x20 ruudukot ovat varmasti mahdottomia ja pienet liian helppoja. - Anonyymi
Anonyymi kirjoitti:
9x9 ruudukon maksimin todistaminen kombinoimalla lienee käytännössä mahdotonta tai ainakin liian kallista. Ehkä 10...20 vuoden päästä voisi yrittää.
Miksei 8x8 ruudukon ratkaisuja tai edes koko tehtävää löydy Googlella? On ollut varmasti ihan yleinen ongelmakulmatehtävä vuosisatoja. Pitäisi tietää joku avainsana tai nimi.
Kokeile täyttää 20x20 (tai 19x19 tai edes 18x18) ruudukko ihan täyteen punaisilla ja sinisillä ruuduilla siten, ettei minkään neliön kaikki 4 nurkkaa ole samaa väriä. Yli 20x20 ruudukot ovat varmasti mahdottomia ja pienet liian helppoja.Kävin läpi kaikki 8x8:n mahdollisuudet. Löytyi vain yksi ratakaisu ja se käännettynä 180 astetta.
Isojen ruudukoiden täyttö kahdella eri värillä siten, ettei minkään neliön kaikki nurkat ole samaa väriä on aika hankalaa. Pitää kehittää siihen joku täysin erilainen algoritmi. Ongelma on varmasti tuttu kaikille pinnan laatoitusongelmia ratkoneille matemaatikoille. Mahdollinen maksimikokokin varmasti tiedetään.
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Aivosyöpää sairastava Olga Temonen TV:ssä - Viimeinen Perjantai-keskusteluohjelma ulos
Näyttelijä-yrittäjä Olga Temonen sairastaa neljännen asteen glioomaa eli aivosyöpää, jota ei ole mahdollista leikata. Hä802799Pelotelkaa niin paljon kuin sielu sietää.
Mutta ei mene perille asti. Miksi Venäjä hyökkäisi Suomeen? No, tottahan se tietenkin on jos Suomi joka ei ole edes soda2931610Mikä saa ihmisen tekemään tällaista?
Onko se huomatuksi tulemisen tarve tosiaan niin iso tarve, että nuoruuttaan ja tietämättömyyttään pilataan loppuelämä?2461517- 871361
IL - VARUSMIEHIÄ lähetetään jatkossa NATO-tehtäviin ulkomaille!
Suomen puolustuksen uudet linjaukset: Varusmiehiä suunnitellaan Nato-tehtäviin Puolustusministeri Antti Häkkänen esittel4011339Nyt kun Pride on ohi 3.0
Edelliset kaksi ketjua tuli täyteen. Pidetään siis edelleen tämä asia esillä. Raamattu opettaa johdonmukaisesti, että3961273Esko Eerikäinen tatuoi kasvoihinsa rakkaan nimen - Kärkäs kommentti "Ritvasta" lävähti somessa
Ohhoh! Esko Eerikäinen on ottanut uuden tatuoinnin. Kyseessä ei ole mikä tahansa kuva minne tahansa, vaan Eerikäisen tat381017Kiitos nainen
Kuitenkin. Olet sitten ajanmerkkinä. Tuskin enää sinua näen ja huomasitko, että olit siinä viimeisen kerran samassa paik2979Hyväksytkö sinä sen että päättäjämme ei rakenna rauhaa Venäjän kanssa?
Vielä kun sota ehkäpä voitaisiin välttää rauhanponnisteluilla niin millä verukkeella voidaan sanoa että on hyvä asia kun329854Miksi Purra-graffiti ei nyt olekkaan naisvihaa?
"Pohtikaapa reaktiota, jos vastaava graffiti olisi tehty Sanna Marinista", kysyy Tere Sammallahti. Helsingin Suvilahden254832