Zeltlager

Dieses Rätsel schaut harmlos aus, hat es aber in sich. Die Aufgabe: in einem rechteckigen oder quadratischen Feld sind Bäume eingezeichnet.

• Zu jedem Baum ist genau ein Zelt daneben (das heißt links, rechts, oberhalb oder unterhalb des Baumes) aufzustellen.
• Zwei Zelte dürfen nicht waagrecht oder senkrecht nebeneinanderstehen. Diagonal ist erlaubt.
• In jeder Zeile und jeder Spalte ist angegeben, wie viele Zelte dort zu stehen haben.

Hier wieder ein Beispiel aus der schönen Sammlung von Angela und Otto Janko (https://www.janko.at/Raetsel/Zeltlager):

Datenstruktur

In den bisherigen Programmen wurde bisher der nächste level mit dem Eintragen einer gültigen Zahl (oder einer Königin) in ein Feld erreicht. Hier ist es sinnvoller. jedem Baum eine Nummer zuzuordnen, die gleich dem level ist, und den level nach der erfolgreichen Zuordnung eines Zelts zu erhöhen. Alle Felder werden wieder Spalte für Spalte und Zeile für Zeile nummeriert. Jeder Baum erhält eine Platznummer, aus der seine Koordinaten Zeile (r) und Spalte (c) errechnet werden. Mit moves werden jene Plätze bestimmt, auf die ein Zelt gestellt werden kann. valid prüft, ob dabei die Bedingungen eingehalten werden. Die Hilfsfunktion neighbors bestimmt zu einer Feldnummer die Nummern der Nachbarn, also aller horizontal und vertikal (aber nicht diagonal) umgebenden Felder.

Das Beispiel oben enthält 25 Felder (von 0 bis 24 nummeriert). Die Bäume stehen auf den Feldern 0, 10, 14, 17 und 23. Diese Nummern werden als Liste trees gespeichert. Nachbarn von 10 wären beispielsweise 5, 11 und 15. Die geforderte Anzahl der Zelte wäre in den Zeilen (rows) 1, 1, 1, 1, 1 und in den Spalten (cols) 1, 1, 2, 0, 1. Somit wird dieses Rätsel durch die drei Listen

trees = [0, 10, 14, 17, 23]
rows =  [1, 1, 1, 1, 1]
cols =  [1, 1, 2, 0, 1]

beschrieben.

zeltlager.py

# File zeltlager.py

from backtrack import Backtrack

 

class Zeltlager(Backtrack):

 

    trees = [0, 10, 14, 17, 23]

    rows =  [1, 1, 1, 1, 1]

    cols =  [1, 1, 2, 0, 1]

   

    # Auch rechteckige Plätze sind möglich, daher zwei Größenangaben

    rsize = len(rows)

    csize = len(cols)

   

    tents = []  # Zu Beginn sind keine Zelte aufgebaut

    solutionNr = 0      # Nummer der Lösung

    rowscount = [0 for i in range(rsize)]  # Aktuelle Anzahl der Zelte pro Zeile

    colscount = [0 for i in range(csize)]  # Aktuelle Anzahl der Zelte pro Spalte

 

    def __init__(self, test:bool= False, showAttempts:bool = False):

        super().__init__(test, showAttempts)

 

    def rowAndCol(self, where:int) -> tuple:

        s = self.rsize

        return (where // s, where % s)

 

    def neighbors(self, place:int) -> list[int]:

       

        r, c = self.rowAndCol(place)        

        s = self.rsize

        n = [ ]    

       

        if c+1<s:

            n.append(place+1)            

        if r>0:

            n.append(place-s)        

        if c>0:

            n.append(place-1)

        if r+1<s:

            n.append(place+s)

        return n

   

    def moves(self, level: int) -> list[int]:        

        return self.neighbors(self.trees[level])

 

    def valid(self, level: int, move:int) -> bool:

        if move in self.trees:  # da steht ein anderer Baum

            return False

       

        if move in self.tents:  # da steht schon ein zelt

            return False

 

        for n in self.neighbors(move):

            if n in self.tents: # da steht schon ein Zelt daneben

                return False

 

        r, c = self.rowAndCol(move)

        if self.rowscount[r] >= self.rows[r]:   # kein weiteres Zelt möglich

            return False

        if self.colscount[c] >= self.cols[c]:   # kein weiteres Zelt möglich

            return False

        return True

 

    def record(self, level: int, move:int):

        self.tents.append(move)

        r, c = self.rowAndCol(move)

        self.rowscount[r] += 1

        self.colscount[c] += 1

 

    def undo(self, level: int, move:int):

        self.tents.pop()

        r, c = self.rowAndCol(move)

        self.rowscount[r] -= 1

        self.colscount[c] -= 1

 

    def done(self, level: int)-> bool:

        if len(self.trees) == len(self.tents):

            self.solutionNr += 1            

            self.show()

            return True

        return False

 

    def show(self):

 

        # Einfache Ausgabe:

        # print(f”\nSolution {self.solutionNr:4} level={level} {self.tents}”)

 

        # Schönere Ausgabe:

        tree = "B"  #  B steht für Baum

        tent = "Z"  #  Z steht für Zelt

        print(f"\nLösung {self.solutionNr:4}")

        print(" "*6, end="")

        for c in range(self.csize):

            print(f"{self.cols[c]:3}", end="")

        print()

        for r in range(self.rsize):

            print(f"{self.rows[r]:2d} -> ", end="")

            for c in range(self.csize):

                f = r*self.rsize + c # Feldnummer

                if f in self.trees:

                    print(f"  {tree}", end="")

                elif f in self.tents:

                    print(f"  {tent}", end="")

                else:

                    print("  .", end="")

            print()

 

if __name__ == "__main__":

    Zeltlager(test=False, showAttempts=True)

Ergebnisse

Das Programm (zeltlager.py) findet zwei Lösungen, hier mit den Randbeschriftungen:

Lösung    1
        1  1  2  0  1
 1 ->   B  Z  .  .  .
 1 ->   Z  .  .  .  .
 1 ->   B  .  Z  .  B
 1 ->   .  .  B  .  Z
 1 ->   .  .  Z  B  .

Lösung    2
        1  1  2  0  1
 1 ->   B  Z  .  .  .
 1 ->   .  .  .  .  Z
 1 ->   B  .  Z  .  B
 1 ->   Z  .  B  .  .
 1 ->   .  .  Z  B  .
44 attempts in     0.50 seconds

B steht Baum und Z für Zelt. Nette Symbole aus dem Unicode-Zeichensatz wären besser, erfordern aber mehr Aufwand, da sie keine einheitliche Zeichenbreite aufweisen.

zeltlager_2.py zeigt ein anderes Beispiel, wieder mit der Übergabe der Problembeschreibung als Argumente an Zeltlager.

zeltlager_3.py enthält eine neue Angabe für eine schwierige Aufgabe. Die Lösungen 2 und 3 sehen gleich aus. Allerdings werden Bäume und Zelte unterschiedlich zugeordnet. Um das anzuzeigen, wird hier anstelle von “Z” die Nummer des Baums angezeigt, der zu dem Zelt gehört. Das zeigt, dass in den Lösungen 2 und 3 die Baumnummern 11 und 14 vertauscht sind.

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)