Beim bekannten Königsberger Brückenproblem soll man in einer Rundreise jede der 7 Brücken genau einmal überqueren und wieder am Ausgangspunkt ankommen.
Insgesamt 96 Spielversionen dieser Aufgabe in 6 Spielstufen hat die App “7 bridges”:
Es beginnt zunächst in den ersten beiden Leveln (“Bridges” und “Bridg-o-rama”) mit relativ trivialen Spielchen, die einfach Beispiele des klassischen graphentheoretischen Problems sind – allerdings ist zu beachten, dass hier nicht nach Eulerkreisen, sondern nach Eulerwegen gesucht wird: man soll alle Brücken überqueren, muss aber nicht unbedingt am Ausgangspunkt wieder ankommen.
Euler selbst hatte ja seinerzeit bemerkt, dass es eine Rundreise (einen Eulerkreis) genau dann gibt, wenn jede Insel eine gerade Anzahl von Brücken hat. Falls man nur nach einem Eulerweg (also einer Reise, deren Endpunkt nicht unbedingt der Startpunkt ist) sucht, hat man eine ähnliche Bedingung: es muss entweder 0 oder 2 Inseln mit einer ungeraden Anzahl von Brücken geben.
Einen Algorithmus für die Rundreise entwickelte erst Hierholzer in seiner postum 1873 veröffentlichten Arbeit Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Der Hierholzer-Algorithmus funktioniert in linearer Laufzeit und ist eigentlich recht naheliegend: man findet einen Kreis, nimmt diesen aus dem Graphen heraus und findet einen weiteren Kreis im übriggebliebenen Graphen usw., am Ende setzt man die Kreise zusammen.
Man kann Hierholzers Algorithmus natürlich auch auf die Suche nach Eulerwegen anwenden: man verbindet einfach die beiden Inseln mit ungerader Brückenzahl durch eine zusätzliche (gedachte) Brücke und sucht dann mit dem Algorithmus nach einem Eulerkreis in diesem neuen Graphen.
Für die hier auftretenden Brückenzahlen (maximal 66) sollte auch schon der in quadratischer Zeit arbeitende Fleury-Algorithmus ausreichen.
Diese klassischen Probleme stellen die jeweils 16 Spiele in den ersten beiden Leveln. Im dritten Level “Houses and Colors” kommen dann Farben dazu: beim Überqueren einer farbigen Brücke nimmt der Spieler die Farbe der überquerten Brücke an. Wichtig ist das weil man die Häuser nur in der jeweils passenden Farbe besuchen darf.
Beim 4. Level “Tolls” kommt als weitere Schwierigkeit hinzu, dass man manche Brücken nur überqueren darf, wenn man vorher Punkte gesammelt hat. Die Punkte bekommt man bei den Häusern.
Und schließlich gibt es den 5. Level “Subways” und den 6. Level “Teleporters”, bei denen man, wenn vorher genug Punkte gesammelt wurden, U-Bahnen und Teleportation benuten darf, um Brücken zu überwinden.
Die App für 0,99 Euro gibt es hier.
Kommentare (1)