Ruudukon täyttö niin että ei muodostu neliöitä

Anonyymi

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.)

29

227

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Anonyymi
      • 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 1

        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]


      • 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
        Anonyymi kirjoitti:

        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)

        Löytyi

        n=20: 208
        01101111100111011000
        00011010101101101111
        01110001111010110010
        11010111001001010011
        10111100011000111010
        01100100100110000111
        10001111110000110100
        11101010010010001110
        10110011000110101001
        11010000010010011101
        01110001000001100101
        10000010111111010001
        10101101000000110110
        01100110011001001101
        11010100000111100011
        10111010100101001001
        10100011101010001010
        11001000101010101111
        01111001011101110101
        01010111110111011100

        n=25: 304
        1100101101111010011100000
        1010011001010101110001111
        0100110110110011010010101
        1101011010100010101100010
        0100010001111100011001010
        1011100000100111001011111
        0010001111100101011101001
        0101101010001110000001100
        1010100110000100101110101
        0011000000010010110101110
        0010010110101110000111001
        1110100001000000110010111
        0011101101001000100001101
        1001000101011111110110000
        1111011100000000001101110
        0101010110010001100101010
        1100001101110000101010100
        1010001011011000001010011
        1100101100110011000001101
        0111100010101000110010110
        0010110111100101011000010
        1001101000100011110100111
        0101010001010110011101101
        1100110001111010010011011
        0110011010101111100010110

        Laitoin nyt vielä n=50 pyörimään.


      • Anonyymi
        Anonyymi kirjoitti:

        Löytyi

        n=20: 208
        01101111100111011000
        00011010101101101111
        01110001111010110010
        11010111001001010011
        10111100011000111010
        01100100100110000111
        10001111110000110100
        11101010010010001110
        10110011000110101001
        11010000010010011101
        01110001000001100101
        10000010111111010001
        10101101000000110110
        01100110011001001101
        11010100000111100011
        10111010100101001001
        10100011101010001010
        11001000101010101111
        01111001011101110101
        01010111110111011100

        n=25: 304
        1100101101111010011100000
        1010011001010101110001111
        0100110110110011010010101
        1101011010100010101100010
        0100010001111100011001010
        1011100000100111001011111
        0010001111100101011101001
        0101101010001110000001100
        1010100110000100101110101
        0011000000010010110101110
        0010010110101110000111001
        1110100001000000110010111
        0011101101001000100001101
        1001000101011111110110000
        1111011100000000001101110
        0101010110010001100101010
        1100001101110000101010100
        1010001011011000001010011
        1100101100110011000001101
        0111100010101000110010110
        0010110111100101011000010
        1001101000100011110100111
        0101010001010110011101101
        1100110001111010010011011
        0110011010101111100010110

        Laitoin nyt vielä n=50 pyörimään.

        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.


    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Tokmanin johtaja avauti työntekijäpulasta

      Huuskosen mukaan Tokmannilla on ollut vaikeuksia löytää työvoimaa myymälöihin ja varastoihin, jonka seurauksena tavaratoimituksia on jouduttu jättämää
      Maailman menoa
      342
      8901
    2. Upeaa Martina ja Stefu!

      Onpa upeaa huomata, että ex-pariskunta pystyy juhlimaan yhdessä yhteisen tyttärensä synttäreitä! Ovat ilmeisesti aikuisia ihmisiä, jotka pystyvät haut
      Kotimaiset julkkisjuorut
      275
      2519
    3. 117
      1396
    4. Oho! Iina Kuustonen ja Mikko Leppilampi "häähumussa", Mikko-isä kuittaa viiltävästi: "Totaalinen..."

      Iina Kuustonen on heittänyt hulvattoman idean Instagramissa. Tällä porukalla on kyllä sarkasmi hallussa! https://www.suomi24.fi/viihde/oho-iina-kuusto
      Kotimaiset julkkisjuorut
      2
      1235
    5. Hyvä olkoon sitten niin!

      Minä lopetan sussa roikkumisen ja kiellän ikuisesti kaikki tunteeni sua kohtaan. En tiedä kuka edes olet enää ja jos tulet juttelemaan niin käännän se
      Ikävä
      64
      847
    6. Poliisioperaatio kansanedustajan kotona

      Riikka Slunga-Poutsalon poika säilytti kovia huumeita ja myyntivälineitä äitinsä asunnossa. https://www.iltalehti.fi/politiikka/a/a23dec18-05ef-4ab2-b
      Maailman menoa
      261
      823
    7. Etäisyys kaivattuusi ?

      Oma ihastukseni ( mies ) asuu 250 km päässä, menee autolla 3,5 tuntia ajaessa. Ikävä on koko ajan, nähdään yleensä viikonloppuisin. Miten lähellä/kauk
      Ikävä
      57
      821
    8. Syy miksi en kysele perääsi

      Johtuu siitä että olen ns. Kaikkiruokainen. Voin kyllä ottaa toisenkin naisen jos sinua ei kiinnosta olla mun kanssa. Odotan vain. Se on meinaan niin
      Tunteet
      80
      819
    Aihe