Gesamtes Labyrinth auskundschaften und Rückwege markieren

Die Idee ist, einen Todo-Liste mit Zellen (Positionen) zu haben, die noch nicht «fertig augekundschaftet» sind.

Von dieser Liste nimmt man jeweils eine Zelle weg und bearbeitet diese. Dabei werden unter Umständen neue Zellen zur Todo-Liste hinzugefügt.

Eingabe: Labyrinth mit unmarkierten Zellen, ausser die Startzelle ist markiert mit 'S'
 
Todo-Liste enthält die Startzelle
Solange die Todo-Liste nicht leer ist, wiederhole:
    Entferne eine Zelle aus der Todo-Liste, nenne diese «aktuell»
    Für alle Richtungen $d$ von 0 bis und mit 3:
        Ist der Durchgang zur Nachbarszelle «nachbar» in Richtung $d$ offen?
            Ist «nachbar» unmarkiert?
                markiere «nachbar» mit einem Pfeil, der zu «aktuell» zeigt (z.B. mit >,v,<,^).
                Füge «aktuell» der Todo-Liste hinzu.
                Füge «nachbar» der Todo-Liste hinzu.
                Beende das Überprüfen der Richtungen sofort.
 
Ausgabe: Von Jeder Zelle ist der Weg zur Startzelle markiert.

Je nachdem, wie die Zelle aus der Todo-Liste entfernt werden, wird das Labyrinth in unterschiedlicher Art durchsucht.

Tiefensuche: Die zuletzt eingefügten Zellen werden zuerst entfernt (Last in, first out). Die Todo-Liste wird als Stapel verwendet. Die Suche geht erst so weit wie irgend möglich, bzw. erst in die Tiefe.

Breitensuche: Die Zellen werden in der Reihenfolge entfernt, wie sie hinzugefügt wurden. D.h. Zellen hinten der Liste hinzugefügt und vorne entfernt. Die Suche besucht die Zellen in Reihenfolge ihrer Distanz von Startpunkt, geht «zwiebelschalenförmig» vor. Man könnte die Distanz vom Startpunkt als Markierung verwenden, z.B. 0-9, dann A-Z, dann a-z.

todo = []              # Leere Liste
todo.append(start)     # Element hinten anfügen
prin(len(todo))        # Anzahl Elemente ausgeben
aktuell = todo.pop()   # Element hinten von der Liste entfernen
todo.append(start)
aktuell = todo.pop(0)  # Element vorne (von Position 0) entfernen

Warten, damit in der Ausgabe verfolgt werden kann, was läuft.

import time
 
time.sleep(0.1)   # 0.1s Warten

Markierungen für die Distanz. Folgende

# Liefert die nächste Markierung 0-9,A-Z,a-z
def naechsteMarkierung(markierung):
   if markierung=="9":
       return "A"
   if markierung=="Z":
       return "a"
   return chr(ord(markierung)+1)