Labyrinthe lösen und erzeugen

+---+---+---+---+---+---+
|   |           |       |
+   +   +   +   +---+   +
|   |   |   |           |
+   +   +---+---+---+   +
|   |       |       |   |
+   +   +---+   +   +   +
|               |   |   |
+   +---+   +---+---+   +
|   |               |   |
+---+   +   +---+---+   +
|       |           |   |
+---+---+---+---+---+---+

In einem Raster sollen Labyrinthe gelöst und erzeugt werden.

Zur Verfügung steht eine Klasse, die eine zeilenweise ASCII-Art Darstellung des Labyrinths enthält und manipulieren kann.

• l = Laby(5,8): Erzeugt ein leeres Raster der Grösse 5×8 (alle Verbindungen geschlossen).
• l.w und l.h sind die Breite und Höhe des Rasters (Anzahl Zellen).
• Zellinhalte können gesetzt und abgefragt werden: l.setMark(x,y,c) und l.getMark(x,y). Default-Inhalt ist ein Leerschlag.
• Die vier Richtungen sind definiert: l.dirs, von 0 bis 3, trigonometrisch von 0˚ bis 270˚.
• Verbindungen können gesetzt und abgefragt werden: l.canGo(x,y,d) und l.setGo(x,y,d,True/False)
• Hilfsfunktion a,b = l.move(x,y,d) liefert die verschobenen Koordinaten von (x,y) in Richtung d.
• Hilfsfunktion l.on(x,y) liefert True, wenn (x,y) im Raster.
• l.neu() generiert ein leeres Raster mit allen Verbindungen geschlossen.
• l.load(datei), l.save(datei), tut was man vermutet.

Python-Code

Weitere Labyrinthe

• Es soll der (einzig existierende) Weg von der linken oberen Zelle (0,0) zur Zelle unten rechts (l.w-1, l.h-1) gefunden werden.
  • Überlegen Sie sich dazu erste einen Algorithmus auf Papier. Nutzen Sie dazu die Möglichkeit, Zellen markieren zu können.
  • Programmieren Sie Ihren Algorithmus. Markieren Sie den Weg
    • Markierung entweder mit 'X', oder optional die Richtung angeben, in der die Zelle verlassen werden muss, mit '>', 'v', '<', '^'.
• Überlegen Sie sich, wie ein Labyrinth generiert werden könnte und programmieren Sie einen solchen Generator.
• Wie zufällig ist ihr generiertes Labyrinth? Könnten alle möglichen Labyrinthe von Ihrem Algorithmus erzeugt werden? Sind die einzelnen Labyrinthe gleich wahrscheinlich?