Keskustelu: Ohjelmointiputka: Putkaposti 19: Älykäs robotti

Uusi putkaposti on ilmestynyt:

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=arob

Kuinka lyhyitä komentosarjoja onnistutte löytämään?

Normaalia helpompi. Voisin jopa osallistua :)

Aika jännä tehtävä, ei ole moni uskaltanut koskeakaan ilmeisesti.

Olisi ihan kiinnostava kuulla, millaisia lähestymistapoja tuohon on jo keksitty. Itse tein apuohjelman, jolle voin syöttää siirtoja ja joka näyttää merkkigrafiikalla erilaiset mahdolliset tilanteet, joissa nyt erilaisissa labyrinteissa oltaisiin. Nykyinen ratkaisuni on siis päättelemällä ja kokeilemalla saatu.

Edit. Ja näinpä se lyheni tuonne 30:een asti. Ehkä tähän on hyvä lopettaa tältä erää.

Kuinka lyhyen sarjan Antti itse on onnistunut löytämään?

Metabolix kirjoitti:

Aika jännä tehtävä, ei ole moni uskaltanut koskeakaan ilmeisesti.

Olisi ihan kiinnostava kuulla, millaisia lähestymistapoja tuohon on jo keksitty. Itse tein apuohjelman, jolle voin syöttää siirtoja ja joka näyttää merkkigrafiikalla erilaiset mahdolliset tilanteet, joissa nyt erilaisissa labyrinteissa oltaisiin. Nykyinen ratkaisuni on siis päättelemällä ja kokeilemalla saatu.

Edit. Ja näinpä se lyheni tuonne 30:een asti. Ehkä tähän on hyvä lopettaa tältä erää.

Itse lähdin toisesta suunnasta, kohti ideaaliratkaisua...

Antaa koneen jauhaa, myöhemmin lisää asiasta, jos ratkaisu(ja) löytyy...

Dataa on kertynyt jo muutama kymmentä megaa...

PS. Se on kaukana puhtaasta brute-forcesta...

Itse aloitin vain kirjoittelemaan tekstieditoriin siirtosarjaa, jota mielessäni kokeilin erilaisiin tilanteisiin ja lisäksi käytin apuna tehtävän lähetyssivua, joka näyttää tilanteen, jossa Osku epäonnistuu. Aina kun sarjan pituus alkoi mennä yli 50, niin aloitin alusta tai yritin lyhentää sitä jotenkin. Ensimmäinen kelvollinen sarjan pituus oli 51, josta se sitten pienellä muokkauksella putosi nykyiseen pituuteensa, joka on 46. Vielä näköjään olisi aika paljon varaa optimoida, mikäli vaan viitsin.

Minäkin olen tähän mennessä lähinnä tyytynyt etsimään ratkaisuja kokeilemalla enkä ole alittanut lukujenVihaajan tulosta (29). Toisin sanoen minulla ei ole tehtävään "malliratkaisua". Mutta muutama algoritmi-idea on mielessä, joista kerron lisää, jos ne osoittautuvat riittävän nopeiksi. Näistä algoritmeista on päältä päin vaikea sanoa, ovatko ne tarpeeksi tehokkaita, ja en ole vielä saanut ohjelmoitua niitä. Kuitenkin olen melko toiveikas, että vielä tämän 4 x 4 -ruudukon lyhin komentosarja olisi mahdollista varmistaa tavalla tai toisella.

Antti Laaksonen kirjoitti:

Minäkin olen tähän mennessä lähinnä tyytynyt etsimään ratkaisuja kokeilemalla enkä ole alittanut lukujenVihaajan tulosta (29). Toisin sanoen minulla ei ole tehtävään "malliratkaisua". Mutta muutama algoritmi-idea on mielessä, joista kerron lisää, jos ne osoittautuvat riittävän nopeiksi. Näistä algoritmeista on päältä päin vaikea sanoa, ovatko ne tarpeeksi tehokkaita, ja en ole vielä saanut ohjelmoitua niitä. Kuitenkin olen melko toiveikas, että vielä tämän 4 x 4 -ruudukon lyhin komentosarja olisi mahdollista varmistaa tavalla tai toisella.

Se voi olla vaikeaa, 6-20 merkin komentosarjoja on kuitenkin "vaatimattomat" 90 biljoonaa, 6-28 merkin sarjoja 40 000 triljoonaa.

Laskennan 1. vaihe suoritettu, nyt minulla on 109 uniikkia lyhyttä komentosarjaa, jotka tulee yhdistää vastaukseksi.

SPOILER:
<spoiler>
Vain ~1/6 ruudukoista (16384) on mahdollisia. 3828
Niistä reiluun kolmannekseen on vain yksi kuuden merkin ratkaisu. 1454
Kuuden merkin ratkaisuja on 20 erilaista.
5*5 tai suurempiin ei suurella todenäköisyydellä ole "Oskulle kelpaavaa ratkaisua" vaikka ratkaisun pituusraja poistettaisiin.

.....
####.
.....
.####
.....

.#...
.#.#.
.#.#.
.#.#.
...#.
ja muut tämäntyyppiset poisulkevat 4*4 ruudukossa olevan "säännön",
jos ruudukko on ratkaistavissa, niin siihen on olemassa ratkaisu,
jonka pituus on täsmälleen 6 (8 @ 5*5)

</spoiler>

L2-K2 kirjoitti:

Vain ~1/6 ruudukoista (16384) on mahdollisia. 3828

No spoiler sinullekin (tai muille, jotka eivät ole tätä ehkä huomanneet): olennaisesti erilaisia labyrintteja on vain 2083. Esimerkiksi seuraavassa tapauksessa saavuttamattomilla kysymysmerkkiruuduilla ei ole merkitystä:

O.#?
#..#
?#..
??#X

BTW, 3828 / 16384 = 0.234 eli noin 1/4, hieman enemmän siis kuin väitit. Sen sijaan 2083 / 16384 = 0.127 eli noin 1/8.

Mä en millää keksi miten saa käytyä läpi kaikki mahdolliset "kentät".

L2-K2 kirjoitti:

Se voi olla vaikeaa, 6-20 merkin komentosarjoja on kuitenkin "vaatimattomat" 90 biljoonaa, 6-28 merkin sarjoja 40 000 triljoonaa.

Jep, ja vaikeus onkin siinä, että suurin osa noista sarjoista täytyy jonkin oveluuden avulla hylätä niin, että niitä ei tarvitse edes tutkia.

L2-K2 kirjoitti:

Laskennan 1. vaihe suoritettu, nyt minulla on 109 uniikkia lyhyttä komentosarjaa, jotka tulee yhdistää vastaukseksi.

Kertoisitko tarkemmin, millä menetelmällä olet etsimässä vastausta?

Dude kirjoitti:

Mä en millää keksi miten saa käytyä läpi kaikki mahdolliset "kentät".

Rekursiivinen aliohjelma on yksi näppärä konsti.

Pseudokoodina aliohjelma näyttää tältä:

haku(x, y):
    if x == 0 and y == 4:
        valmis()
        return
    if x == 4:
        haku(0, y + 1)
        return
    kentta[x][y] = 0
    haku(x + 1, y)
    kentta[x][y] = 1
    haku(x + 1, y)

Aliohjelmaa kutsutaan haku(0, 0) ja ideana on, että taulukkoon kentta tulee vuorollaan jokainen mahdollinen kenttä, jotka käsitellään aliohjelman valmis avulla. Taulukossa 0 tarkoittaa tyhjää ruutua ja 1 tarkoittaa estettyä ruutua. Aliohjelma haku on rekursiivinen eli se kutsuu itseään, ja jokainen kutsutaso huolehtii yhdestä taulukon alkiosta. Jokaisella tasolla haaraudutaan kahteen tapaukseen: taulukkoon tulee siihen kohtaan tyhjä ruutu tai estetty ruutu. Aliohjelman alussa olevat ehtolauseet tarvitaan seuraavalle riville siirtymiseen ja valmiin kentän käsittelyyn.

Jos ohjelmoit QBasicilla, koodi näyttää käytännössä tältä:

DIM SHARED kentta%(4, 4)

Haku 0, 0

SUB Haku (x%, y%)
   IF x% = 0 AND y% = 4 THEN
      Valmis
      EXIT SUB
   END IF
   IF x% = 4 THEN
      Haku 0, y% + 1
      EXIT SUB
   END IF
   kentta%(x%, y%) = 0
   Haku x% + 1, y%
   kentta%(x%, y%) = 1
   Haku x% + 1, y%
END SUB

Kaikki kentät voi kokeeksi vaikkapa tulostaa:

SUB Valmis
   FOR y% = 0 TO 3
      FOR x% = 0 TO 3
         IF kentta%(x%, y%) = 0 THEN
            PRINT "_";
         ELSE
            PRINT "#";
         END IF
      NEXT
      PRINT
   NEXT
   PRINT
END SUB

Voi olla hyvä idea säilöä kaikki kentät taulukkoon (tai jopa tiedostoon), josta ne ovat helposti saatavilla tarvittaessa eikä niitä jouduta joka kerta muodostamaan alusta alkaen.

Antti Laaksonen kirjoitti:

Voi olla hyvä idea säilöä kaikki kentät taulukkoon (tai jopa tiedostoon), josta ne ovat helposti saatavilla tarvittaessa eikä niitä jouduta joka kerta muodostamaan alusta alkaen.

Tällä tuskin on todellista merkitystä. Raskaahko C++-toteutus funktiosta, joka luo kaikki kentät ja karsii mahdottomat ja epäolennaiset pois, tekee tehtävänsä noin 0,02 sekunnissa g++:lla -O2-lipulla käännettynä.

Antti Laaksonen kirjoitti:

L2-K2 kirjoitti:

Laskennan 1. vaihe suoritettu, nyt minulla on 109 uniikkia lyhyttä komentosarjaa, jotka tulee yhdistää vastaukseksi.

Kertoisitko tarkemmin, millä menetelmällä olet etsimässä vastausta?

Etsin ns. "vaikeista kentistä" (valitsin algoritmillä ne, joiden lyhimpänä ratkaisuna vain ruudukon keskeltä meneviä reittijä, niissä paljon jumittavia paikkoja) kaikki reitit, jotka vievät läpi siten, että siirtoja, joilla ei ole vaikutusta merkataan pienillä kirjaimilla yoav. Sitten yhdistän nämä sarjat yhdeksi. Sarjasta tuli yllättävän lyhyt, 20 merkkiä...

Tosin nyt kun olen saanut sarjan valmiiksi, havaitsin että se ei toimi joillekkin sellaisille kentille, joita pidin "helppoina".

Mietintämyssy palaa takaisin päähän...

Antti Laaksonen kirjoitti:

L2-K2 kirjoitti:

Se voi olla vaikeaa, 6-20 merkin komentosarjoja on kuitenkin "vaatimattomat" 90 biljoonaa, 6-28 merkin sarjoja 40 000 triljoonaa.

Jep, ja vaikeus onkin siinä, että suurin osa noista sarjoista täytyy jonkin oveluuden avulla hylätä niin, että niitä ei tarvitse edes tutkia.

Sarjoja voi karsia muutamalla tavalla,
- ensimmäinen merkki on A, (O pois symmetrian vuoksi; Y tai V eivät tee mitään alussa)
- toinen merkki on joko A tai O
- sarjassa on oltava vähintään kolme O ja kolme A
(- O ei voi seurata V:tä eikä V O:ta) Tai sitten voi...
(- A ei voi seurata Y:tä eikä Y A:ta) ...jos tarkemmin ajattelee.
- sarja päättyy joko A tai O
- yli kolmea samaa kirjainta ei voi olla peräkkäin

Nyt sarjoja on huomattavasti vähemmän, mutta silti aivan liikaa.

* sarja ei toimi jos se ei toteuta jotain ruudukkoa, joten aloitetaan testaus sellaisista ruudukoista, joissa useimmat sarjat epäonnistuvat

Pitäisiköhän laittaa brute-force kehiin?

L2-K2 kirjoitti:

5*5 tai suurempiin ei suurella todenäköisyydellä ole "Oskulle kelpaavaa ratkaisua" vaikka ratkaisun pituusraja poistettaisiin.

Minusta on selvää, että kaikkiin kokoihin on ratkaisu, jos pituutta ei rajoiteta.

L2-K2 kirjoitti:

(- O ei voi seurata V:tä eikä V O:ta) Tai sitten voi...
(- A ei voi seurata Y:tä eikä Y A:ta) ...jos tarkemmin ajattelee.

Minusta niin päin pätee, että O ei voi seurata V:tä ja A ei voi seurata Y:tä, tai minulle ei ainakaan tule mieleen, missä tilanteessa olisi hyödyllistä mennä ensin väärään suuntaan ja sitten palata heti takaisin. Sen sijaan toiseen suuntaan tuossa voi olla järkeä esim. silloin, kun oikealle meneminen johti jossain labyrintissa ratkaisuun, mutta muissa pitää vielä tutkia uusia reittejä.

funktio kirjoitti:

L2-K2 kirjoitti:

5*5 tai suurempiin ei suurella todenäköisyydellä ole "Oskulle kelpaavaa ratkaisua" vaikka ratkaisun pituusraja poistettaisiin.

Minusta on selvää, että kaikkiin kokoihin on ratkaisu, jos pituutta ei rajoiteta.

Näin on, koska jokin ratkaisu löytyy varmasti katsomalla riittävän monta kertaa, mistä labyrintista kehitteillä oleva komentosarja ei selviä, ja täydentämällä komentosarjaa niin, että se ratkaisee lopuksi tämän labyrintin. Näin komentosarjan pituudelle saa todella karkean ylärajan, n² * 2ⁿ², jossa tulon ensimmäinen osa on pisin polku labyrintin sisällä ja toinen osa on erilaisten labyrinttien määrä. 4 x 4 -tapauksessa näin saatu yläraja on 1048576, joten eipä ole kovin tarkka arvio. Tuota ylärajaa voi toki hieman miettimällä pienentää molempien tulon tekijöiden osalta.

Antti Laaksonen:Mä en oo opetellu tekemään rekursiivisiä ohjelmia. Mä tein tuosta sellaasen että se tallentaa ne tiedostoon.

Tämä on mukava ja vaikeustasoltaan sopiva tehtävä; pääsin alustavasti 60:een. Laadin komentosarjan ihan manuaalisesti päättelemällä ja yritys-erehdys-menetelmällä.

Tein Pythonilla pienen apuohjelman, joka laatii kaikki läpäistävissä olevat ruudukot ja testaa annettua komentosarjaa niillä. Epäonnistuneen ruudukon kohdalla tulostuu sekä kyseinen ruudukko että robotin sijainti siinä.

Tallensin läpäistävissä olevat ruudukot tiedostoon, jottei niitä tarvitse laskea joka kerta. Pythonin pickle-moduuli on muuten kätevä moiseen (solvables on 2-ulotteinen lista):

try:
    solvables = pickle.load(open('solvables.dat'))
except:
    solvables = calc_solvables()
    pickle.dump(solvables, open('solvables.dat','w'))

Mihinköhän asti tämä putkaposti on voimassa? Itse olen laskenut, että saisin, jos oikein muistan, alle 30 menevän ratkaisun ja tuo ratkaisu on vasta puhtaasti paperilehtiön ja kynän avulla saatu. Pitäisi kai kehitellä vielä jonkinlaista ohjelmaa kai tuosta, kun kerta Ohjelmointiputkasta on kyse. Tosin alussa mietin hetken, että tarvitseekö tässä ongelman luonteen vuoksi kirjoittaa riviäkään koodia. Pelkän kynän ja paperin kanssa tuo ratkeaa jo melko pitkälle (tai no kokonaan jopa), ainakin sellainen tuntuma itsellä on. Jonkinlaista alarajaa tuon ratkaisun pituudelle olen saannu ja ne arviot eivät paljoa alle 30 ole olleet. Voi olla tietty, että arvioni ovat täysin vääriä.

Pari ongelmaa kun ratkaisee, niin voisi kokeilla tehdä ohjelman, joka generoi tuon ratkaisun. Saa nähdä mitä tästä tulee, jos viikonloppuna ehtisi loppuun ratkomaan tuon.

Kaiketi näihin pystyy vastailemaan myös sen jälkeen kun ne ovat sivupalkista poistuneet, että aikataulun kanssa ei ole niin kiirettä.

Seuraava putkapostitehtävä ilmestyy näillä näkymin tammikuun lopussa, joten ratkaisun lähetykseen on vielä hyvin aikaa. Ja tosiaan myös vanhoihin tehtäviin voi lähettää ratkaisuja, vaikka ne eivät enää näykään sivupalkissa.

Päärynämies kirjoitti:

Pitäisi kai kehitellä vielä jonkinlaista ohjelmaa kai tuosta, kun kerta Ohjelmointiputkasta on kyse.

Ohjelmaa ei toki tarvitse kirjoittaa, jos vastauksen onnistuu selvittämään muutenkin. Toisinaan Putkapostissa on tehtäviä, jotka voi ratkaista ilman ohjelmointia, ja tämä tehtävä on ilman muuta sellainen. Lähinnä voi tuntea ylpeyttä, jos tehtävän selvittää perinteisin keinoin ilman tietokoneen apua.

Päärynämies kirjoitti:

Jonkinlaista alarajaa tuon ratkaisun pituudelle olen saannu ja ne arviot eivät paljoa alle 30 ole olleet.

Olisin kiinnostunut kuulemaan käyttämistäsi menetelmistä ja saamistasi tuloksista.

Voisin koittaa kyllä tuosta ratkaisusta jonkinlaista koodia vääntää, jos sellaisesta täällä putkassa joku olisi kiinnostunut. Onhan kyse ohjelmointisivustosta. Olen tässä muutaman päivän Haskelia koitellut opetella, joten siitä voisi saada kivan harjotustyön samalla. Ehkä tosin tyydyn pythonilla kokeilemaan, jos en tarpeeksi kerkeä oppia.

Ratkaisuidea kyllä on jo päässä, mutta vielä pitäisi koittaa se muuttaa ajatuksista koodiksi. Voisi sitten myös testata kuinka hyvin se toimii, mutta tosiaan alle kolmenkymmenen veikkaan sen saavani ja brute forcellahan tuota on turha koittaa ratkoa. Tuolloinkin karkeasti arvioiden mahdollisia sarjoja on 4^30 (Tiedän, että tuo heittää kovin paljonkin johtuen liikuttavista suunnista).

Voin sepustaa jotain ratkaisun ja tuon arvion saamisesta tänne, jos se oikeaksi osoittautuu ja kukaan ei ole samaa jo tänne kirjoitellut. Tietysti lähestymistapa voi siltikin olla kovin erilainen.

Päärynämies kirjoitti:

... brute forcellahan tuota on turha koittaa ratkoa. Tuolloinkin karkeasti arvioiden mahdollisia sarjoja on 4^30 (Tiedän, että tuo heittää kovin paljonkin johtuen liikuttavista suunnista).

Miten tuon nyt ottaa. Itse en saanut mitään hienoa algoritmia keksityksi, joten pistin koneen laskemaan. Hakuavaruudesta jo 12% tutkittu ja kun tuon koneen antaa raksuttaa niin jo noin 10 päivässä tuo on kokonaan käyty läpi. Hakuavaruus on mun virityksillä noin luokkaa 4^19, missä ei ole vielä tehty mitään oletuksia, jotka saattaisivat jättää ratkaisuja pois. Olisi varmaan sittenkin pitänyt ostaa se quadcore prossu :)

Tällä hetkellä löytynyt 17(x2) eri 29 siirtoa sisältävää ratkaisua.

FooBat kirjoitti:

Päärynämies kirjoitti:

... brute forcellahan tuota on turha koittaa ratkoa. Tuolloinkin karkeasti arvioiden mahdollisia sarjoja on 4^30 (Tiedän, että tuo heittää kovin paljonkin johtuen liikuttavista suunnista).

Miten tuon nyt ottaa. Itse en saanut mitään hienoa algoritmia keksityksi, joten pistin koneen laskemaan. Hakuavaruudesta jo 12% tutkittu ja kun tuon koneen antaa raksuttaa niin jo noin 10 päivässä tuo on kokonaan käyty läpi. Hakuavaruus on mun virityksillä noin luokkaa 4^19, missä ei ole vielä tehty mitään oletuksia, jotka saattaisivat jättää ratkaisuja pois. Olisi varmaan sittenkin pitänyt ostaa se quadcore prossu :)

Tällä hetkellä löytynyt 17(x2) eri 29 siirtoa sisältävää ratkaisua.

Onko järkeä etsiä 29-ratkaisuja, eikö kannattaisi etsiä <29-ratkaisuja.

L2-K2 kirjoitti:

Onko järkeä etsiä 29-ratkaisuja, eikö kannattaisi etsiä <29-ratkaisuja.

No joo. Halusin ensin löytää edes yhden 29 merkkisen ratkaisun, kun epäilen että se on se minini ja nyt kun se on alkanut jauhamaan niin antaa mennä loppuun asti. Saapahan ainakin selville monta eri ratkaisua tuohon on. Eikä tuo kone valita vaikka sitä vähän rääkkää. Kun pistää prosessille pienemmän prioriteetin niin ei edes käytössä huomaa, että se laskee taustalla.

Brute forcella ratkaisemisesta tuosta katoaa myös osakseen ratkaisun hienous. Onhan se hienompi ratkaista käyttämällä vain kynää ja paperia, kuin vain laittaa kone kokeilemaan eri vaihtoehtoja. Tietysti kun suuri määrä vaihtoehtoja käydään kokeilemalla läpi, niin koodin optimoinnin merkitys nousee huomattavasti.

Päärynämies kirjoitti:

Onhan se hienompi ratkaista käyttämällä vain kynää ja paperia — —

Ja eihän näissä tehtävissä ole edellytetty ohjelman laatimista. Pari aiempaakin on ratkennut paperilla, ainakin yksi jopa päässä. Kerro toki jossain vaiheessa, mitä oikein olet tehnyt. :)

Minusta raaka voima on ihan hyvä juttu, jos sen avulla paljastuu luotettava alaraja.

Miltähän näyttäisi säännöllinen lauseke, joka tuottaa kaikki kelvolliset komentosarjat?

Antti Laaksonen kirjoitti:

Minusta raaka voima on ihan hyvä juttu, jos sen avulla paljastuu luotettava alaraja.

Miltähän näyttäisi säännöllinen lauseke, joka tuottaa kaikki kelvolliset komentosarjat?

Pitkältä :P.

Rajausta:
Alle 17 mittaisia ratkaisuja ei taida olla (täysin optimoimaton brute-force ei löytänyt).
50% 17:sta käyty läpi, mutta ei tällä tavalla (ainakaan tällä raudalla, nyt kulunut jo useita minuutteja, aikaarvio 29 saavuttamiseen ~200 vuotta), ei tule koskaan valmista... lopetan tähän.

On muuten olemassa ainakin yksi (+peilikuva) 28 merkin pituinen komentosarja, joka ratkaisee kaikki paitsi yhden (1) ruudukon.

Varoitus! Saatan spoilata jotakin.

Väitämpä nopeiden paperilla tehtyjen pohdintojen jälkeen, ettei ei ole alle 29 siirron mittaista sarjaa, joka ratkaisisi kaikki mahdolliset sokkelot. Voitte koittaa todistaa vääräksi, vaikka sitten brute forcella.

Jos tälläiset väitteet tai "spoilaukset" ovat kiellettyjä, niin poistakaa tai muokatkaa vain rankalla kädellä. Ei ole tarkoitus ratkaisun iloa viedä muilta, vaan vain käydä aktiivista keskustelua.

Voisi vielä itsekin brute forcella omaa ratkasua testata. Eikun koodia vääntämään.

FooBat kirjoitti:

Tällä hetkellä löytynyt 17(x2) eri 29 siirtoa sisältävää ratkaisua.

SPOILER:
Kun löydät kaikki 29-ratkaisut näet samalla mikä on alaraja ratkaisun pituudelle.

Sain nyt jonkinlaisen python -skriptin aikaiseksi testatakseni ratkaisuani, mutta nyt ongelmaksi muodostuikin se, etten tiedä moniko noista mahdollisista sokkeloista on ratkaistavissa. Saako sen joku paljastaa vai pitääkö minun laskea ne itse tai kehittää algoritmi ratkaistavuuden testaamiseen? Tietysti algoritminkin voin kehittää, mutta jotenkin mielestäni epäoleellista tehtävän kannalta, kun ei ole tarkoitus kerta tutkia eri sokkeloideen ratkaistavuutta.

Tosin heräsi pieni epäilys, että olisiko tuota omaa 29:n merkin mittaista sarjaani vielä sittenkin mahdollista lyhentää. Voisi koittaa kirjoittaa ohjelman sen testaamiseen.

Kuten aiemmin jo kerroin, ratkaistavissa on 3828 eli noin 1/4. Näistä oleellisesti erilaisia on vain 2083 eli noin 1/8. Jälkimmäisestä luvusta on karsittu pois ruudukot, joissa on eroa vain sellaisella alueella, johon ei pääse tai johon pääsee vain kulkemalla maalin kautta.