Kartenlegen - Anfänger mit knackigem Problem

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Zwonimir
User
Beiträge: 4
Registriert: Samstag 14. April 2018, 01:11

Erstmal möchte ich mich kurz vorstellen, ich bin Mechatroniker aus Wien und lerne seit einigen Wochen zum Spaß Python 3.

Derzeit habe ich ein Real-Life-Problem, welches ich gerne nutzen würde, um meine Python-Kenntnisse zu vertiefen. An richtigen Problemen knobelt es sich einfach lieber, als an Beispielen aus dem Lehrbuch.
Ich habe ein Kartenspiel, welches ich nicht schaffe zu lösen. Langsam beschleicht mich das Gefühl, dass es keine Lösung geben kann. Wieso also nicht alle Permutationen durchrechnen?

Bild

Zur Vereinfachung versuche ich meine Überlegungen nur anhand der vier Karten oben links zu veranschaulichen:
Ich vergebe Front und Heck der Flugzeuge in den verschieden Farben Primzahlen, positiv und negativ:

Front weiß = +2
Heck weiß = -2
Front gelb = +3
Heck gelb = -3
Front grün = +5
Heck grün = -5
Front blau = +7
Heck blau = -7

Karte 1 oben links stelle ich also von oben beginnend im Uhrzeigersinn als Liste dar=

Code: Alles auswählen

card1 = [-7, -2, 5, 3]
Die Idee ist, dass im Layout die Summe der benachbarten Flugzeugteile so 0 ergeben müsste.
Jetzt kann jede Karte an 9 Positionen liegen, und jeweils 4 Lagen einnehmen. Somit gebe es also 9!*9^4 Möglichkeiten soweit ich richtig rechne, wenn wir nicht in Betracht ziehen, dass zwei Hecks und zwei Fronten nicht zusammen passen.

Wenn wir jetzt der Einfachheit halber nur die vier Karten oben links ansehen, habe ich mal sowas hier fabriziert:

Code: Alles auswählen

card1 = [-7, -2, 5, 3]
card2 = [-3, -5, 7, 2]
card3 = [-5, -3, 5, 2]
card4 = [-7, -2, 7, 3]
result = 1
iteration = 0
drehung = 0


while result != 0 and drehung <4:
    result = card1[1] + card2[3] + card3[1] + card4[3] + card1[2] + card3[0] + card2[2] + card4[0]
    iteration = iteration + 1
    
    if result == 0:
        print ("Bingo! Summe ist",result,"bei Durchlauf",iteration,".")
        print ("Lösung:\nKarte 1:", card1, "\nKarte 2:", card2, "\nKarte 3:", card3, "\nKarte 4:", card4)
    else:
        print (iteration)
        card1.append(card1.pop(0))
        drehung = drehung + 1
Ich drehe die erste Karte maximal vier Mal und berechne jedesmal die Summe der Schnittstellen. Zuerst addiere ich horizontal, danach vertikal. Hier im Code-Beispiel liegen die Karten wie oben im Bild richtig.
Jetzt stehe ich aber vor dem Problem, dass ich Karte 2 um 90 Grad weiter drehen will und dann Karte 1 wieder einmal rundum rotieren muss, usw.
Ich könnte jetzt für jede Karte eine neue Schleife anlegen, aber dass muss doch übersichtlicher gehen?

Meine Idee ist, dass ich alle Karten in eine Liste packe, und dann für jede Karte mit einer Drehungsvariablen arbeite:

Code: Alles auswählen

cards = [[-7, -2, 5, 3],[-3, -5, 7, 2],[-5, -3, 5, 2],[-7, -2, 7, 3]]
Aber was dann?
Wenn die Lage aller Karten einmal durch ist, muss ich eine Positionspermutation durchführen. Dafür habe ich mir schon die Itertools Bibliothek angesehen, damit könnte es vielleicht klappen.

Hat jemand einen Tipp oder eine Idee? Ich bin mir nicht sicher ob ich das nicht zu kompliziert angehe, vielleicht bin ich komplett am Holzweg?

Wenn es keine Lösung für das Game geben sollte, möchte ich es hieb und stichfest wissen. Ich hoffe ihr versteht das? :wink:
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Wenn ich mich nicht verrechnet habe, sollten es n! * 4^n Kombinationen sein.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Habe mich wohl tatsächlich verrechnet und komme jetzt auf n!^2 * 4^n Permutationen.

Vielleicht stimmt ja auch das nicht und es gibt sicher zudem mehrere Wege die Lösung anzugehen. Mein Ansatz wäre:

Code: Alles auswählen

import itertools
from enum import Enum


class Plane(Enum):
    blue_front = 1
    green_front = 2
    yellow_front = 3
    white_front = 4
    blue_tail = -1
    green_tail = -2
    yellow_tail = -3
    white_tail = -4
    

# ORDER: top, right, bottom, left
CARDS = [
    [Plane.blue_tail, Plane.white_tail, Plane.green_front, Plane.yellow_front],
    [Plane.yellow_tail, Plane.green_tail, Plane.blue_front, Plane.white_front],
    [Plane.green_tail, Plane.yellow_tail, Plane.green_front, Plane.white_front],
    [Plane.blue_tail, Plane.white_tail, Plane.blue_front, Plane.yellow_front]
]


class Tile:
    
    def __init__(self, top, right, bottom, left):
        self.__dict__.update(
            {k:v for k, v in locals().items() if k != 'self'})
        
    def rotate(self):
        self.top, self.right, self.bottom, self.left = (
            self.left, self.top, self.right, self.bottom)
        
    def __str__(self):
        return '{}, {}, {}, {}'.format(
            self.top.name, self.right.name, self.bottom.name, self.left.name)
        

class Board:
    
    def __init__(self, tileset):
        self.tileset = tileset
    
    @property
    def is_solution(self):
        # to implement
        return False
    
    
def tileset_variations(tileset):
    # TODO: for every tileset do the proper rotations
    yield Board(tileset)

    
def boards(tiles):
    for tileset in itertools.permutations(tiles):
        yield from tileset_variations(tileset)

        
def find_solution(tiles):
    for board in boards(tiles):
        if board.is_solution:
            print(board)
            break
    else:
        print("no solution found")
        
        
def main():
    tiles = [Tile(*card) for card in CARDS]
    find_solution(tiles)
    
    
if __name__ == '__main__':
    main()
Vielleicht kannst Du diesen Ansatz nutzen oder findest etwas geeigneteres.
Zwonimir
User
Beiträge: 4
Registriert: Samstag 14. April 2018, 01:11

Ich muss gestehen, ich bin mit deinem Code erstmal überfordert. Trotzdem danke für die Hilfe, ich schaue mir das sofort an.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@kbr: Du willst den Preis für das kryptischste Programm gewinnen?

Code: Alles auswählen

class Tile:
    def __init__(self, top, right, bottom, left):
        self.top = top
        self.right = right
        self.bottom = bottom
        self.left = left
Da Du sowieso left, top, usw. nicht verwendest, kannst Du Tile einfach durch »collections.deque« ersetzen. Das hat schon eine »rotate«-Methode.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

@Sirius3: sicher, etwas kryptisch. Aber nützlich bei sehr vielen Parametern. Etwas abgewandelt in eine externe Funktion ausgelagert, genügt dann oft ein Einzeiler zur Initialisierung. Ob ein solches Programmdesign (das 'explicit is better than implicit' nicht einhält) gewünscht wird ist eine andere Frage, wie es dokumentiert wird die nächste, und ob es Dir gefällt wieder eine andere.

Da die Tiles später auf korrekte Orientierung geprüft werden müssen, sind deques dafür nicht gut geeignet.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@kbr: wenn ein Initialisierer viele Parameter hat, dann hat man schon ein Problem. Wenn man etwas anderes macht, außer Parameter zu kopieren, dann hat man einen schwer zu findenden Fehler. Wenn in Deiner Implementierung deques Probleme macht (ich finde gar keine) dann wären Namedtuple eine Alternative.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

@Sirius3:
wenn ein Initialisierer viele Parameter hat, dann hat man schon ein Problem. Wenn man etwas anderes macht, außer Parameter zu kopieren, dann hat man einen schwer zu findenden Fehler.
Schön und gut, nichts anderes wird gemacht.
Wenn in Deiner Implementierung deques Probleme macht (ich finde gar keine) dann wären Namedtuple eine Alternative.
Natürlich kannst Du keine Probleme finden, schließlich ist die Prüfung der Tiles noch nicht implementiert. Ich weiß auch nicht, ob ich das tun werde. Du kannst es aber gerne mit deques vormachen, wenn Du willst.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@kbr: ich habe es mit einfachen Strings gelöst. Wobei es, wie der OP schon richtig vermutet, gar keine Lösung gibt.


@Zwonimir: am einfachsten implementiert man das mit einer rekursiven Funktion. Man legt an die erste Position alle Karten in allen Rotationen und ruft die Funktion mit der zweiten Position auf und probiert dort alle restlichen Karten in allen Rotationen und ruft wieder die Funktion mit der dritten Position auf, usw.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

Sirius3 hat geschrieben:@kbr: ich habe es mit einfachen Strings gelöst. Wobei es, wie der OP schon richtig vermutet, gar keine Lösung gibt.
Oh, wie schade. Insbesondere, da ich mehrere ganz ähnliche Puzzles kenne (mit Schildkröten statt Flugzeugen z.B.), die Lösungen haben. Verdammt schwer zu finden.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Habe mir das Puzzle noch einmal angesehen. Statt der theoretisch möglichen n!^2 * 4^n Möglichkeiten kommen nur 4 n! in Betracht, da alle Lösungen mit nicht einheitlichen Kartenausrichtungen ausscheiden. Verbleiben also n! Möglichkeiten multipliziert mit vier, da alle Karten gemeinsam rotiert werden müssen, bevor die nächsten Permutationen durchgerechnet werden. Aber auch dies ist überflüssig, da sich alle diese Rotationen ineinander überführen lassen. Zudem braucht aufgrund der definierten Ausrichtung der Karten nicht unterschieden werden, ob bei gleichfarbigen Kanten Front- oder Heckteile vorliegen. Das vereinfacht die Umsetzung weiter.

Also habe ich meinen Ansatz einmal laufen lassen und wenn man die Ausgangsposition des Puzzles mit

123
456
789

bezeichnet, dann ergibt sich ohne Rotation die Lösung

623
981
547
Zwonimir
User
Beiträge: 4
Registriert: Samstag 14. April 2018, 01:11

@kbr
Stimmt, an das gemeinsame rotieren habe ich gar nicht gedacht! Und ja, damit entfällt natürlich auch die Unterscheidung zwischen Front- und Heck... irre, ich sah den Wald vor lauter Bäumen nicht.
Kannst du mir trotzdem beim code ein wenig unter die Arme greifen, ich verstehe im obigen Beispiel nur Bahnhof... Bei der Anwendung der Permutationen habe ich noch leichte Verständnis-Probleme. Außerdem habe ich noch ein weiteres Puzzle, von welchem ich die Lösung zwar kenne, aber es wäre auch interessant ob es mehrere Lösungen gibt. :D
Vielen lieben Dank, ich bin an dem Ding schon verzweifelt. Python ist für die Lösung solcher Alltagsprobleme echt klasse, da macht es gleich viel mehr Spaß, gefällt mir immer besser.

Bild
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

@Zwonimir: Das neue Puzzle scheint aufwendiger zu lösen, da hier einzelne Karten wohl doch rotiert werden können und dadurch nicht nur auf Farbe, sondern auch auf Besen oder Kopf getestet werden muss. Insbesondere aber erhöht sich die Zahl der Permutationen u.U. beträchtlich. Wenn Du zudem wissen möchtest, ob es mehrere Lösungen gibt, musst Du diese alle durchrechnen. Das kann ein Problem werden: Nehmen wir an, die Zahl der möglichen Permutationen beträgt n!^2 * 4^n, dann ergibt dies für n=9 ca. 3,45 * 10^16 Varianten. Das sind zu viele. Du musst also Regeln finden, welche die Zahl der zu betrachtenden Varianten einschränken. Im Falle des Flugzeug-Puzzles war es möglich die Zahl der sinnvollen Kombinationen auf n! einzugrenzen. Bei n = 9 sind dies immer noch 362.880 Varianten.

Meinen Code für die Lösung des Flugzeug-Puzzles füge ich unten an. Diesen kannst Du gerne als Vorlage nutzen.

Code: Alles auswählen

import itertools


# ORDER: top, right, bottom, left
CARDS = [
    ['blue', 'white', 'green', 'yellow'],
    ['yellow', 'green', 'blue', 'white'],
    ['white', 'yellow', 'blue', 'green'],
    ['green', 'yellow', 'green', 'white'],
    ['blue', 'white', 'blue', 'yellow'],
    ['yellow', 'white', 'green', 'blue'],
    ['green', 'white', 'blue', 'yellow'],
    ['blue', 'yellow', 'green', 'white'],
    ['green', 'white', 'blue', 'yellow']
]

# assume square board:
SHAPE = int(len(CARDS) ** 0.5)


class Tile:
    
    def __init__(self, top, right, bottom, left):
        self.top = top
        self.right = right
        self.bottom = bottom
        self.left = left
        
    @property
    def colors(self):
        return ', '.join([self.top, self.right, self.bottom, self.left])
    

class Board:
    
    def __init__(self, tileset):
        self.tileset = tileset
                
    def get_neighbours(self, index):
        right = index + 1
        try:
            right_tile = self.tileset[right] if right % SHAPE else None
        except IndexError:
            right_tile = None
        bottom = index + SHAPE
        try:
            bottom_tile = self.tileset[bottom]
        except IndexError:
            bottom_tile = None
        return right_tile, bottom_tile
            
    @property
    def is_solution(self):
        
        def match_right(tile, right_tile):
            return True if not right_tile else tile.right == right_tile.left
            
        def match_bottom(tile, bottom_tile):
            return True if not bottom_tile else tile.bottom == bottom_tile.top
            
        for index, tile in enumerate(self.tileset):
            right_tile, bottom_tile = self.get_neighbours(index)
            if not (match_right(tile, right_tile) and match_bottom(tile, bottom_tile)):
                return False
        return True

    def __str__(self):
        return '\n'.join([tile.colors for tile in self.tileset])

    
def boards(tiles):
    for tileset in itertools.permutations(tiles):
        yield Board(tileset)

        
def find_solution(tiles):
    for board in boards(tiles):
        if board.is_solution:
            return board
    return "no solution found"
        
        
def main():
    tiles = [Tile(*card) for card in CARDS]
    result = find_solution(tiles)
    print(result)
    
    
if __name__ == '__main__':
    main()
Zwonimir
User
Beiträge: 4
Registriert: Samstag 14. April 2018, 01:11

@kbr

Vielen Dank, das hilft mir definitiv weiter. Aufbauend auf dieser Problemstellung fallen mir jede Menge anderer Dinge ein, die ich später, sobald ich mit Python besser vertraut bin, angehen kann. Danke nochmals! 8)
Antworten