Backtracking: Skyline
Ich bin auf das Skyline-Rätsel über die Sonntagausgabe der Presse aufmerksam geworden. Auf der Seite puzzlephil https://puzzlephil.com/puzzles/skyline/de/ finden sich ebenfalls derartige Rätsel, manchmal auch “Stadtteil” oder “Stadtviertel” genannt. Ich stelle hier ein leichtes und ein besonders schwieriges Rätsel vor.
Das Bild zeigt mehrere Hochhäuser von oben. Die Regeln lauten:
- Die Hochhäuser sind jeweils 10, 20, 30 … Stockwerke hoch. Jede Gebäudehöhe kommt in jeder Zeile und jeder Spalte genau einmal vor.
- Die Zahlen am Rand geben an, wie viele Gebäude man von links (von Westen), von rechts (von Osten) usw. sieht. Höhere Gebäude verbergen niedrigere Gebäude. Die Zahl 0 oder eine fehlende Zahl bedeutet, dass die Anzahl der sichtbaren Hochhäuser nicht bekannt ist.
Die mit dem Programm skyline.py
bestimmte Lösung für die einfache Aufgabe lautet:
[40, 20, 10, 30]
[10, 30, 40, 20]
[20, 10, 30, 40]
[30, 40, 20, 10]
Vom Westen aus sehe ich
- 1 Hochhaus (40 Stockwerke), dann
- 3 Hochhäuser (10, 30, 40 Stockwerke), dann wieder
- 3 Hochhäuser (20, 30, 40 Stockwerke) und
- 2 Hochhäuser (30, 40 Stockwerke).
Schaut nach einer interessanten Programmieraufgabe aus!
Beginnen wir mit der Codierung der Aufgabenstellung. Das ist einfach, die vier Randbeschriftungen reichen zur Beschreibung. Sie werden als Listen angelegt:
west = [1, 3, 3, 2]
east = [2, 2, 1, 3]
north = [1, 3, 2, 2]
south = [2, 1, 3, 2]
Mit der Länge der Listen ist auch die Größe des Stadtteils (size
) bestimmt: in diesem Fall ist sie gleich 4. Der Stadtteil wird als eindimensionaler vector
gespeichert, aus dem bei Bedarf einzelne Zeilen und Spalten errechnet werden.
Nun zu den Regeln:
- Regel 1 wird wie bei vorhergehenden Rätseln umgesetzt.
- Für die Regel 2 müssen die sichtbaren Hochhäuser gezählt werden. Da das Zählen und Prüfen für alle vier Richtungen auszuführen sind, ist eine eigene Funktion (
check
) dafür sinnvoll. Aber wie werden Zeilen von links nach rechts und von rechts nach links, Spalten von oben nach unten und von unten nach oben abgearbeitet?
Beispiel
v = [0, 1, 2, 3, 4, 5, 6, 7]
v[0:4]
oder v[0:4:1]
ist der Teilbereich [0, 10, 20, 30]
In dem Beispiel ist 0
der Startindex, 4
der Stoppindex und 1
die Schrittweite. Zum Stoppindex (4)
gehört das Element v[4]
, ist gleich 40
. Es gehört nicht mehr zu dem Teilbereich.
Geht es auch in der umgekehrten Richtung?v[4:0:-1]
ergibt [40, 30, 20, 10]
, also noch nicht den gewünschten Teilbereich. Nun ist v[-8]
gleich 0
. Ferner ist bei einem Teilbereich der Wert an der Obergrenze nicht enthalten. Daher liefert erstv[-5:-9:-1]
oder v[3:-9:-1]
wie gewünscht [30, 20, 10, 0]
.
Wie kann man das ganze v
umdrehen?v[8:-1:-1]
ergibt überraschend [ ]
, aber v[8:-9:-1]
dreht v
um: [70, 60, 50, 40, 30, 20, 10, 0]
Damit können wir Zeilen oder Teile von Zeilen von links nach rechts oder von rechts nach links abarbeiten. Wie kommen wir zu den Spalten?
Nehmen wir an, dass v
einer Matrix mit 2 Zeilen und 4 Spalten darstellt. Die Spalte 0
wird mit v[0:5:4]
aufgerufen (Resultat [0, 40])
, die Spalte 1
mit v[1:6:4]
(ergibt [10, 50]
) usw.
Und in der umgekehrten Richtung?v[4:-9:-4]
ergibt [4, 0]
, v[5:-9:-4]
ergibt [50, 10]
, v[6:-9:-4]
ergibt [60, 20]
und v[7:-9:-4]
liefert [70, 30]
Die Indexausdrücke von v
(wie etwa [4:-9:-4]
) können jedoch nicht als Argumente an die Funktion check übergeben werden. Stattdessen ist ein slice
-Objekt zu verwenden, zum Beispiel slice(4, -9, -4)
.v[slice(4, -9, -4)]
ergibt wieder [40, 0]
.
Hinweis: Auch die Zuweisung des Slice-Objekts an eine Variable ist möglich:sl = slice(4, -9, -4)
v[slice]
Damit kann die Methode valid
recht übersichtlich geschrieben werden. Nur die Argumente von slice
sind nicht wirklich selbsterklärend.
skyline.py
# File skyline.py
from backtrack import Backtrack
import sys
class Skyline(Backtrack):
vector = []
solutionNr = 0
high = 10
# Siehe https://puzzlephil.com/puzzles/skyline/de/
# leicht
west = [1,3,3,2]
east = [2,2,1,3]
north = [1,3,2,2]
south = [2,1,3,2]
def __init__(self, test:bool = False, showAttempts:bool = False):
if not(len(self.west) == len(self.east) == len(self.north) == len(self.south)):
print("Ungleiche Randspalten – Programm beendet")
sys.exit()
self.size = len(self.west)
self.vector = [0 for i in range(self.size*self.size)]
self.showAttempts = showAttempts
self.test = test
self.rset = [set() for i in range(self.size)]
self.cset = [set() for i in range(self.size)]
self.values = set(range(self.high, (self.size+1)*self.high, self.high))
super().__init__(test, showAttempts)
def rowAndCol(self, where:int):
s = self.size
r = where // s
c = where % s
return (r, c)
def moves(self, level:int):
r, c = self.rowAndCol(level)
return list(self.values – self.rset[r] – self.cset[c])
def valid(self, level:int, move:int) -> bool:
r, c = self.rowAndCol(level)
s = self.size
# Jede der vier Richtungen muss einzeln geprüft werden
# Daher ist der Einsatz einer eigenen Funktion check sinnvoll
# Argumente:
# visible: wieveiel Hochhäuser sind sichtbar?
# sl: Argumente für slice
def check(visible:int, sl:list) -> bool:
if visible==0:
# Unbekannte Anzahl, daher ist die Annahme nicht falsch
return True
max = 0
count = 0
# Wenn sl[2] gleich 1 oder -1 ist, wird eine Zeile untersucht
rowtest = abs(sl[2])==1
rc = c if rowtest else r
# Letzte Spalte oder letzte Zeile erreicht?
if rc+1 == s:
# Zählen der sichtbaren Häuser
for v in self.vector[slice(*sl)]:
if v > max:
# Ist das Haus höher als die vorhergehenden?
# Dann count um 1 erhöhen
max = v
count += 1
# Sollten Zwischenergebnisse zum Testen ausgegeben werden?
if self.test:
self.show(f"level={level} r={r} c={c} move={move} attempt={self.attempts}"
f"\nrowtest={rowtest} max={max} count={count} visible={visible} \n"
f"slice={sl} ==> {self.vector[slice(*sl)]}")
# Wurden exakt die Häuser laut Angabe gefunden?
if count != visible:
return False
return True
self.vector[r*s + c] = move # move probeweise eintragen
res = all([
check(self.west[r], [r*s, (r+1)*s, 1]),
check(self.east[r], [-(s-r-1)*s-1, -(s-r)*s-1, –1]),
check(self.north[c], [c, c+s*s, s]),
check(self.south[c], [-(s-c), -((s+1)*s-c), -s])
])
if self.test and (r+1==self.size or c+1==self.size) and res:
self.show(f"valid={res}, level={level}, r={r}, c={c}, move={move}, attempt={self.attempts}")
self.vector[r*s + c] = 0 # move wieder entfernen
return res
def record(self, level:int, move:int):
self.vector[level]=move
r, c = self.rowAndCol(level)
self.rset[r].add(move) # Wert zur Menge der Zeilenwerte hinzufügen
self.cset[c].add(move) # Wert zur Menge der Spaltenwerte hinzufügen
def undo(self, level:int, move:int):
self.vector[level]=0
r, c = self.rowAndCol(level)
self.rset[r].remove(move) # Wert aus der Menge der Zeilenwerte entfernen
self.cset[c].remove(move) # Wert aus der Menge der Spaltenwerte entfernen
def done(self, level: int)->bool:
if level==self.size*self.size-1:
self.solutionNr += 1
self.show(f"Resultat {self.solutionNr:4d}, {self.attempts:18_d}. Versuch")
return True
return False
def show(self, text):
print(f"\n{text}")
for r in range(self.size):
for c in range(self.size):
print(f"{self.vector[r*self.size + c]:4d}", end="")
print()
if __name__ == "__main__":
Skyline(False, True)
Die Datei skyline_2.py
zeigt eine weitere Version mit der Aufgabenstellung als Argument beim Start von Skyline.
Manche Skyline-Rätsel sind schon sehr aufwändig. Das “teuflische Rätsel” und seine Lösung ist in der Datei skyline_3.py
zu finden. Die vielen Varianten, die zu prüfen sind, werden mit je einem Punkt pro 100.000 Versuche angezeigt.
Mit
west = [4,2,3,3,2,0]
east = [0,0,0,0,2,4]
north = [5,0,5,3,0,1]
south = [0,4,0,0,3,0]
sind 1.316.961 Versuche notwendig, um diese Lösung zu finden:
[20, 40, 10, 30, 50, 60]
[30, 60, 20, 10, 40, 50]
[40, 20, 30, 50, 60, 10]
[10, 50, 40, 60, 30, 20]
[50, 30, 60, 20, 10, 40]
[60, 10, 50, 40, 20, 30]
Gibt es noch weitere Lösungsvektoren? Es kann nur einen geben! ((C) Highlander)
Das Programm prüft trotzdem weiter, findet (wie erwartet) keine weitere Lösung und benötigt dazu insgesamt 56.388.851 Überprüfungen in 618 Sekunden.
Vorgegebene Felder
In einer Variante von Skyline sind einzelne Felder mit Häusern bekannter Höhe besetzt. Zur Lösung hilft dieselbe Überlegung wie beim Sudoku. Die vorgegebenen Felder werden in einem Dictionary known
mit den Feldnummern als Schlüssel und den Höhen als Werte.
Beispiel: das Rätsel “Stadtviertel” aus der Kurier-Beilage “Freizeit” vom 20. August 2022:
Hier sind die Häuser nur 1, 2, 3, 4 oder 5 Stockwerke hoch. Mit dem Argument high=1 wird das beim Aufruf berücksichtigt. Der Lösungsweg ist in skyline_4.py
zu finden.
Links
- Alle Dateien
- Was ist eigentlich ‘Backtracking’? (clubcomputer.at)
- Backtracking: Königinnenproblem (clubcomputer.at)
- Backtracking: Sudoku (clubcomputer.at)
- Backtracking: Kendoku (clubcomputer.at)
- Backtracking: Skyline (clubcomputer.at)
- Backtracking: Zeltlager (clubcomputer.at)
Martin Weissenböck hat die HTL 3 Rennweg 23 Jahre lang geleitet, schreibt Skripten, Lehrbücher und Artikel für die PCNEWS, leitet die Arbeitsgemeinschaft für Didaktik, Informatik und Mikroelektronik (ADIM) und den Verein SCHUL.InfoSMS. Er hält Vorträge und ist Lehrbeauftragter an der Technischen Universität Wien.
Neueste Kommentare