Sokkelo

Matemaatikko Leonhard Euler oli ensimmäisiä, jotka ratkaisivat sokkeloita matemaattisesti. Näin hän löysi topologian tieteenä.

Seuraavat algoritmit on suunniteltu käytettäväksi sokkelon sisällä ilman sokkelon matkustajan aiempaa tietämystä sokkelon rakenteesta. On olemassa toisia algoritmeja sokkeloille paperilla, jossa ratkaisijalla on käytössä sokkelon yleiskuva.

 

Seinän seuraaminen (wall follower) on tunnetuin sääntö sokkeloiden läpikäymisessä. Se tunnetaan joko vasemman käden sääntönä tai oikean käden sääntönä. Jos sokkelo on yksinkertaisesti yhdistetty (kaikki seinät ovat kiinni toisissaan tai sokkelon ulkorajaan), pitämällä yhden kätensä kiinni yhdessä seinässä seuraaja ei eksy ulos sokkelosta paitsi uloskäyntipaikassa, jos sellainen on. Muussa tapauksessa hän palaa sisääntulokohtaan. Jos sokkelo ei ole yksinkertaisesti yhdistetty, tällä menetelmällä ei voi läpikäydä sokkeloa.

Seinien seuraaja -menetelmää voidaan soveltaa kolmi- tai useampiulotteisiin sokkeloihin, jos niiden käytävät voidaan projisoida kaksiulotteisiksi deterministisessä mielessä. Esimerkiksi kolmiulotteisessa ylöspäin etenevien käytävien voidaan ajatella johtavan luoteeseen ja alaspäin menevien käytävien kaakkoon. Tällöin voidaan käyttää standardia seinien seuraaja -menetelmää.

Erilliset (eivät yksinkertaisesti yhdistettyjä) sokkelot voidaan ratkaista yhä seinien avulla seuraavalla menetelmällä, jos sekä sisääntulokohta että ulostulokohta ovat sokkelon ulkoseinillä. Jos sokkelon ratkaisu alkaa sokkelon keskeltä (sisältä), alkupisteen tulee olla erillään loppupisteestä, sillä muuten ratkaisun eteneminen kiertää jatkuvaa kehää. Pledge-menetelmä (nimetty Exeterin Jon Pledgen mukaan) voi ratkaista tämän ongelman.

Esteiden kiertämiseen suunniteltu menetelmä tarvitsee mielivaltaisesti valitun suunnan. Kun etsintä törmää esteeseen, yksi käsi (esimerkiksi oikea) asetetaan esteeseen (näyttämään suuntaa) ja asetetut kädet merkitään muistiin. Kun ratkaisun haku edistyessään etenee alkuperäiseen suuntaan uudelleen ja kun tehtyjen käännösten summa on 0, ratkaisija jättää esteen ja jatkaa etenemistä sen alkuperäiseen suuntaan.

Tällä menetelmällä kompassin kanssa löytää ulos sokkelosta mistä sisäpisteestä tahansa missä tahansa säännöllisessä (finite) ja kaksiulotteisessa sokkelossa riippumatta etsinnän alkupisteestä. Kuitenkaan tällä menetelmällä ei voida ratkaista tietä alkupisteestä ulostuloon, jos loppupiste on sokkelon sisällä.

Tämä on triviaali menetelmä, joka voidaan toteuttaa erittäin tyhmällä robotilla tai hiirellä, mutta jolla ei ole takeita toimivuudesta. Menetelmässä edetään suoraan eteenpäin, kunnes saavutetaan este. Sen jälkeen tehdään satunnainen päätös, mihin suuntaan edetään. Tämä menetelmä epäonnistuu tietenkin, jos poistuminen (loppupiste) on seinän keskivaiheilla.

 

Tremauxin tehokkaassa menetelmässä sokkelon lattiaan on piirrettävä etenemisviiva kuljetun polun merkitsemiseksi. Menetelmä on taattu ratkaisemaan kaikki hyvinmääriteltyjen käytävien sokkelot. Saavuttaessa merkitsemättömään risteykseen otetaan jokin suunta. Jos taas etsintä on jo käynyt aiemmin tässä risteyksessä, etsintä voi palata takaisin tuloreittiä. Jos edetään uudelleen käytävää, joka on jo tutkittu, piirretään toinen viiva ja seuraavassa risteyksessä edetään tutkimattomalle käytävälle, mikäli mahdollista. Muussa tapauksessa edetään jo tutkittua käytävää. Etsintä ei koskaan käy yhtä käytävää useammin kuin kaksi kertaa. Jos sokkelossa ei ole poistumiskohtaa, menetelmä tuo etsinnän takaisin alkupisteeseen.

 

On olemassa monia tapoja automatisoida sokkelon luominen.

Tämä on yksinkertaisin tapa luoda sokkelo tietokonetta käyttäen. Kuvittele sokkeloon käytettävissä oleva tila laajaksi ruudukoksi (kuten laaja shakkilauta), jonka kussakin ruudussa on alkutilanteessa 4 seinää. Satunnaisesta ruudusta alkaen tietokone valitsee satunnaisen naapurisolun, jossa ei ole vielä vierailtu. Tietokone poistaa seinän näiden kahden ruudun väliltä ja lisää uuden ruudun pinoon (tämä on analogista viivan piirtämiselle lattiaan). Tietokone jatkaa tätä prosessia. Ruutu, jolla ei ole läpikäymättömiä naapurisoluja, on umpikuja. Siihen saavuttuaan luonti palaa takaisin niin kauan, kunnes pinosta löytyy ruutu, jolla on läpikäymättömiä naapuriruutuja (luoden uuden risteyksen). Tämä prosessi jatkuu, kunnes kaikki solut on käyty läpi. Tämä menetelmä johtaa läpikäynnin päättymään lopulta alkusoluun. Tämä merkitsee sitä, että koko sokkelon tila on käyty läpi.

Tällaisenaan menetelmä on erittäin yksinkertainen eikä tuota kovin monimutkaisia sokkeloita. Määritellymmät menetelmän säännöt voivat auttaa vaikeammin ratkaistavia sokkeloita.

• Hoo Hill Maze, Shefford, Bedfordshire, Englanti
• Hampton Court Palace, Englanti (pensasaitasokkelo)
• Chatsworth House, Englanti (pensasaitasokkelo)
• Nooan arkki -eläintarha, Bristol, Englanti (pisin pensasaitasokkelo maailmassa, istutettu 2003)
• Samsø, Tanska (maailman suurin sokkelo)
• Schönbrunn Palace, Itävalta (pieni sisäänpääsymaksu, keskellä sokkeloa torni, josta näkee koko pensasaitasokkelon)
• Longleat, Englanti (pensasaita-sokkelo)
• Kristallipalatsi, Englanti. Pieni sokkelo puistossa.
• Hedge maze Leeds Castlessa, Maidstone, Kent, Englanti. Suunnittelija on Adrian Fisher
• Beauty Hill Farm, Chichester, Yhdysvallat (kenttäsokkelo)
• Sokkelo Keski-saarella Torontossa. Tanskalais-kanadalainen yhteisö lahjoitti sen vuonna 1967. Tämä sokkelo on avoinna yleisölle ympäri vuoden.
• Davis' Mega Maze, Sterling Mass, Yhdysvallat (pensasaita-sokkelo). Adrian Fisherin suunnittelema.
• Labyrinthe du Hangar 16, Montreal, Kanada
• Serendipity Maze, Mouille Point, Kapkaupunki, Etelä-Afrikka
• Soekershof Walkabout Mazes ja Botanical Gardens Robertsonissa, Western Capessa, Etelä-Afrikassa. 13 870 m² alue.
• Magnolia Plantation, Charleston, Etelä-Carolina, Yhdysvallat
• Lasten sokkelo (tehty heinäpaaleista), Ashland Berryn maatila, Ashland, Virginia, Yhdysvallat

Sokkeloita käytetään usein tieteellisessä tutkimuksessa tilallista navigointia ja oppimista tutkittaessa. Tyypillisiä koe-eläimiä ovat rotat tai hiiret. Esimerkkejä tutkimuskohteista ovat Barnesin sokkelo, Morrisin vesisokkelo ja kulmasokkelo.

• Aluesokkelot tai A-sokkelot, joissa läpikäyty alue tulee kasvaa tai vähetä jokaisella askeleella.
• Arpakuutiosokkelot, joissa edetään arpakuutioiden mukaan perustuen erilaisiin sääntöihin.
• Numerosokkelot, joissa edetään ruudussa olevan numeron osoittamaan suuntaan.
• Monitilaiset sokkelot, joissa etsintäsäännöt muuttuvat riippuen siitä, miten sokkelossa on edetty.

Sokkelo, jonka läpikäynti muodostaa kuvion.

Sokkelopeli, jossa läpikäynti muodostaa umpikujia.

• Stanley Kubrick: Hohto
• Guillermo del Toro: Pan's Labyrinth

Pääartikkeli: Sokkelopeli

• Atarin Gotcha

• Fisher, Adrian & Gerster, Georg: The Art of the Maze. Weidenfeld & Nicolson, 1990. ISBN 0-297-83027-9
• Saward, Jeff: Magical Paths. Mitchell Beazley, 2002. ISBN 1-84000-573-4
• Matthews, W.H.: Mazes and Labyrinths: Their History and Development (1927). Dover Publications, 1970. ISBN 0-486-22614-X

 

Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheesta Sokkelo.

• Picturemaze game (Arkistoitu – Internet Archive)
• Hoo Hill Maze: Shefford, Bedfordshire, UK. (Arkistoitu – Internet Archive)
• Mazes: Construction and Solution with Java illustration
• Maze Algorithms: This site explains the different types of mazes and how to generate and solve them
• Make a Maze: This site has a maze generating program
• Printable Maze Games - from 20x20 to 100x100
• Some thoughts on the uses of “Infinite Mazes”
• Topology and navigation (Arkistoitu – Internet Archive)
• Corn mazes in Illinois from the Chicagoland Vibary Network
• Emptystare: exploring the depths of the maze metaphor (Arkistoitu – Internet Archive)
• W.H. Matthews, Mazes and Labyrinths (1922) online-versio W.H. Matthewin klassisesta kirjasta
• Labyrintit (Arkistoitu – Internet Archive) Jeff Sawardin www-sivu
• Labyrinttiyhdistys
• Sokkeloiden luokitus
• Suomalainen sokkelo-labyrintti blogi