Hitta Ut Ur Labyrint

Labyrinten utgörs av ett rutnät där vissa rutor är blanka och andra är fyllda. Blanka rutor kan man passera medan fyllda rutor motsvarar väggar och inte kan beträdas. Förflyttning i labyrinten sker längs rutorna och man kan röra sig vänster (V), höger (H), upp (U) och ner (N) så länge man inte slår i en vägg.

I labyrinten är en Startruta och en Slutruta markerade och vi förutsätter att det är möjligt att ta sig mellan dessa rutor.

Du ska nu försöka programmera en robot med en sekvens av V, H, U och N så att oavsett vilken labyrint roboten utgår från (startar i labyrintens Startruta) så kommer den så småningom att nå till Slutrutan (då den meddelar dig att den är framme). Om roboten i något läge slår i en vägg när den utför en instruktion, hoppar den över denna instruktion. Du får ingen återkoppling alls från roboten förrän den nått Slutrutan.

En sekvens skulle t.ex. kunna vara VVUHNUNHV där roboten först försöker gå vänster, sen vänster igen, sen uppåt etc. (Denna sekvens kommer såklart inte att funka i alla labyrinter.)

Vi förutsätter att vi vet att alla labyrinter som kan förekomma är av begränsad storlek, säg max 1000 rutor åt respektive håll.

Är det möjligt att skriva ett sådant program? Om nej, varför inte. Om ja, hur ser det ut.

Observera alltså att ett och samma program ska fungera oavsett vilken labyrint det är frågan om.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License