Backtracking: Skyline

von | Aug 29, 2022 | Python | 0 Kommentare

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:

  1. Die Hochhäuser sind jeweils 10, 20, 30 … Stockwerke hoch. Jede Gebäudehöhe kommt in jeder Zeile und jeder Spalte genau einmal vor.
  2. 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 erst
v[-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.

Kommentar absenden

Zur Werkzeugleiste springen