mawe's Pythoban knacken

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
Gast

Freitag 29. April 2005, 19:48

Hallo Leute

Um zu schwere Felder von mawe's Pythoban zu knacken dieser Code:

Code: Alles auswählen

#!/usr/bin/env python

import levelset1, sys, copy, time 


###>>> diese Variablen anpassen:
ZeigAlleLoesungen = 0       # 1=sucht nach allen Moeglichkeiten: viel Zeit/RAM
                            # 0=erster Loesungsweg wird gezeigt und dann Exit
MaxVersuche       = 5000000 # 
MaxVerlauf        = 300     # max Schritte bis Loesung: 
                            # zu klein=evtl keine Loesung, zu gross=viel Zeit/RAM
###<<<


Mauer        =  "#"  
Ziel         =  "."  
Mann         =  "@"  
Diamant      =  "$"  
DiamantZiel  =  "*"  
leer         =  " "  
MannZiel     =  "+"  
ausserhalb   =  " "
VersuchNr    =  0
FeldHoehe    =  0
FeldBreite   =  0
Feld1        =  {}
Feld1bew     =  {}
StartZeit    =  time.time()

VersuchtListe = [] # bereits probierte Felder - kein Ergebnis
ProbierListe =  [] # Felder(inkl. Verlauf) die noch probiert werden muessen
BingoListe   =  [] # gefundene Ergebnisse(ganzer Verlauf)


def Fehler(s):
    print s
    sys.exit(1)

# setzt die Variablen FeldBreite/FeldHoehe/Feld1/Feld1bew
def setFeld1(F): 
    f = F.split("\n")
    global FeldBreite
    global FeldHoehe
    global Feld1
    global Feld1bew
    FeldBreite = 0
    FeldHoehe = len(f)
    for i in range(len(f)): # maximale Breite rausbekommen
        while (len(f[i])>0) and (f[i][len(f[i])-1]==" "): 
            f[i] = f[i][0:len(f[i])-1]
        if len(f[i]) > FeldBreite :
            FeldBreite = len(f[i])
    for y in range(FeldHoehe):
        for x in range(FeldBreite):
            try:
                if f[y][x] in [" ",".","*","@","+","#","$","?"]:
                    Feld1[(y,x)] = f[y][x]
                if f[y][x] in [".","*","@","+","$"]:
                    Feld1bew[(y,x)] = f[y][x]
            except: 
                Feld1[(y,x)] = ausserhalb
    global VersuchtListe
    VersuchtListe = FeldHoehe * [[0]]
    for y in range(FeldHoehe):
        VersuchtListe[y] = FeldBreite * [[0]]

def Bingo(F):  # true = Yeah, Weg gefunden
    for i in F.keys():
        if F[i] in ["+",".","$"]:
            return 0
    return 1

def MannPos(F): # wo ist der Mann ?
    for i in F.keys():
        if F[i] in ["@","+"]:
            return i

def IstNeuesFeld(y,x,F): # noch nie benutzte Feld-Konstellation
    return VersuchtListe[y][x].count(F) == 0

def DPos(s):
    komma = s.find(",")
    y = s[1:komma]
    x = s[komma+1:len(s)-1]
    return[int(y),int(x)]

def DiamantInEcke(Feld): # noch weiterprobieren > Quatsch
    for i in Feld.keys():
        if Feld[i] == "$":
            yx = DPos(str(i))
            y = yx[0]
            x = yx[1]
            if (y-1>=0) and (x-1>=0):                 # links oben
                if Feld1[(y,x-1)] == Mauer:            #links
                    if Feld1[(y-1,x)] == Mauer:        #oben
                        return 1
            if (y-1>=0) and (x+1<FeldBreite):         # rechts oben
                if Feld1[(y,x+1)] == Mauer:            #rechts
                    if Feld1[(y-1,x)] == Mauer:        #oben
                        return 1
            if (y+1<FeldHoehe) and (x+1<FeldBreite):  # rechts unten
                if Feld1[(y,x+1)] == Mauer:
                    if Feld1[(y+1,x)] == Mauer:
                        return 1
            if (y+1<FeldHoehe) and (x-1>=0):          # links unten
                if Feld1[(y,x-1)] == Mauer:
                    if Feld1[(y+1,x)] == Mauer:
                        return 1        
    return 0

def ErgebnisZeigen(s):
    print s
    if len(BingoListe) < 1:
        print "Kein Ergebnis gefunden..."
        sys.exit(0)
    print "Suchzeit : ",time.time() - StartZeit," Sek."
    F1 = Feld1.copy()
    for i in F1.keys():
        if F1[i] in ["@",".","*","+","$"]:
            F1[i] = leer
    yxalt = [0,0]
    yxneu = [0,0]
    for x in range(len(BingoListe)):
        print
        print "Ergebnis ",x + 1
        for i in range(len(BingoListe[x])): 
            print
            print "Schritt", i,"  ",
            F = F1.copy()
            d = BingoListe[x][i]
            d = d.keys()
            for dd in d:
                F[dd] = BingoListe[x][i][dd]
            yxalt = yxneu
            yxneu = MannPos(BingoListe[x][i])
            if i > 0:
                if yxneu[0] < yxalt[0]:     # nach oben
                    print "hoch"
                elif yxneu[0] > yxalt[0]:  # nach unten
                    print "runter"
                elif yxneu[1] < yxalt[1]:  # links
                    print "links"
                elif yxneu[1] > yxalt[1]:  # rechts
                    print "rechts"
            else: 
                print
            for y2 in range(FeldHoehe):
                s = ""
                for x2 in range(FeldBreite):
                    s = s + F[(y2,x2)]
                print s                 
    sys.exit(0)

# hier findet die eigentliche/meiste Suche statt
def GehZuFeld(vonX,vonY,nachX,nachY,nachX2,nachY2,Verlauf,neu):
    # erstmal checken ob ueberhaupt gesprungen werden kann...
    if (nachX < 0) or (nachX > FeldBreite-1): return 0
    if (nachY < 0) or (nachY > FeldHoehe-1): return 0
    if (Feld1[(nachY,nachX)] in [Mauer]): return 0
    neu = copy.copy(neu)
    # Diamant verschieben geht nicht ?
    if neu.has_key((nachY,nachX)):
        if (neu[(nachY,nachX)] in [Diamant,DiamantZiel]):
            if (nachX2 < 0) or (nachY2 < 0): return 0
            if (nachX2 > FeldBreite-1) or (nachY2 > FeldHoehe-1): return 0
            if (Feld1[(nachY2,nachX2)] in [Mauer]): return 0
            if neu.has_key((nachY2,nachX2)):
                if (neu[(nachY2,nachX2)] in [Mauer,Diamant,DiamantZiel]): return 0
            else:
                neu[(nachY2,nachX2)] = leer
    else:
        neu[(nachY,nachX)] = leer
    # Es kann gesprungen werden
    if neu[(vonY,vonX)] == Mann:  # Altes Feld wieder herstellen
        del neu[(vonY,vonX)]
    elif neu[(vonY,vonX)] == MannZiel:
        neu[(vonY,vonX)] = Ziel
    if neu[(nachY,nachX)] == Diamant:
        neu[(nachY,nachX)] = Mann
        if neu[(nachY2,nachX2)] == leer: neu[(nachY2,nachX2)] = Diamant
        elif neu[(nachY2,nachX2)] == Ziel: neu[(nachY2,nachX2)] = DiamantZiel
    elif neu[(nachY,nachX)] == DiamantZiel:
        neu[(nachY,nachX)] = MannZiel
        if neu[(nachY2,nachX2)] == leer: neu[(nachY2,nachX2)] = Diamant
        elif neu[(nachY2,nachX2)] == Ziel: neu[(nachY2,nachX2)] = DiamantZiel
    if neu[(nachY,nachX)] == Ziel: neu[(nachY,nachX)] = MannZiel 
    elif neu[(nachY,nachX)] == leer: neu[(nachY,nachX)] = Mann 
    if Bingo(neu): # alle Diamanten im Ziel?
        Verlauf = copy.copy(Verlauf)
        Verlauf.append(neu)
        global BingoListe
        BingoListe.append(Verlauf)
        if not ZeigAlleLoesungen:
            ErgebnisZeigen('Bei der 1. Loesung Suche abgebrochen...')
        return 0 
    else:    
        if DiamantInEcke(neu) or (not IstNeuesFeld(vonY,vonX,neu)):
        #if (not IstNeuesFeld(neu,vonY,vonX)):
            pass
        else: 
            # diese Konstellation gabs noch nicht, in Versuchsliste uebernehmen
            global VersuchtListe
            VersuchtListe[vonY][vonX].append(neu)
            Verlauf = copy.copy(Verlauf)
            neu = copy.copy(neu)
            Verlauf.append(neu)
            global ProbierListe
            ProbierListe.append(Verlauf)
            return 1

def Knacken(Verlauf): # Vorarbeit
    global VersuchNr
    if (len(VersuchtListe) > MaxVersuche):
        ErgebnisZeigen('Nach '+str(MaxVersuche)+' Versuchen sollte abgebrochen werden...')        
    if (VersuchNr > MaxVersuche):
         ErgebnisZeigen('Nach '+str(MaxVersuche)+' Versuchen sollte abgebrochen werden.')
    VersuchNr = VersuchNr + 1
    if len(Verlauf) >= MaxVerlauf: return 0 #nicht weiter suchen
    Feld = Verlauf[len(Verlauf)-1]
    yx = MannPos(Feld)
    y = yx[0]
    x = yx[1]
    # oben
    #b1 = GehZuFeld(x,y,x,y-1,x,y-2,copy.deepcopy(Verlauf),copy.deepcopy(Feld)) 
    # unten
    #b2 = GehZuFeld(x,y,x,y+1,x,y+2,copy.deepcopy(Verlauf),copy.deepcopy(Feld)) 
    # rechts
    #b3 = GehZuFeld(x,y,x+1,y,x+2,y,copy.deepcopy(Verlauf),copy.deepcopy(Feld))
    # links
    #b4 = GehZuFeld(x,y,x-1,y,x-2,y,copy.deepcopy(Verlauf),copy.deepcopy(Feld))

    # oben
    #GehZuFeld(x,y,x,y-1,x,y-2,Verlauf,copy.copy(Feld)) 
    # unten
    #GehZuFeld(x,y,x,y+1,x,y+2,Verlauf,copy.copy(Feld))
    # rechts
    #GehZuFeld(x,y,x+1,y,x+2,y,Verlauf,copy.copy(Feld))
    # links
    #GehZuFeld(x,y,x-1,y,x-2,y,Verlauf,copy.copy(Feld))

    # oben
    #GehZuFeld(x,y,x,y-1,x,y-2,copy.copy(Verlauf),copy.copy(Feld)) 
    # unten
    #GehZuFeld(x,y,x,y+1,x,y+2,copy.copy(Verlauf),copy.copy(Feld)) 
    # rechts
    #GehZuFeld(x,y,x+1,y,x+2,y,copy.copy(Verlauf),copy.copy(Feld))
    # links
    #GehZuFeld(x,y,x-1,y,x-2,y,copy.copy(Verlauf),copy.copy(Feld))

    #cV = copy.copy(Verlauf)
    #cF = copy.copy(Feld)
    # oben
    #b1 = GehZuFeld(x,y,x,y-1,x,y-2,cV,cF) 
    # unten
    #b2 = GehZuFeld(x,y,x,y+1,x,y+2,cV,cF) 
    # rechts
    #b3 = GehZuFeld(x,y,x+1,y,x+2,y,cV,cF)
    # links
    #b4 = GehZuFeld(x,y,x-1,y,x-2,y,cV,cF)

    #b1 = GehZuFeld(x,y,x,y-1,x,y-2,(Verlauf),(Feld.copy())) 
    # unten
    #b2 = GehZuFeld(x,y,x,y+1,x,y+2,(Verlauf),(Feld.copy())) 
    # rechts
    #b3 = GehZuFeld(x,y,x+1,y,x+2,y,(Verlauf),(Feld.copy()))
    # links
    #b4 = GehZuFeld(x,y,x-1,y,x-2,y,(Verlauf),(Feld.copy()))
    
    GehZuFeld(x,y,x,y-1,x,y-2,Verlauf,Feld) 
    # unten
    GehZuFeld(x,y,x,y+1,x,y+2,Verlauf,Feld) 
    # rechts
    GehZuFeld(x,y,x+1,y,x+2,y,Verlauf,Feld)
    # links
    GehZuFeld(x,y,x-1,y,x-2,y,Verlauf,Feld)

def Suchen():
    level = levelset1.levels
    if len(sys.argv) <= 1: Fehler("Kein Parameter uebergeben, z.B.:  2")
    try:
        L = int(sys.argv[1])
    except:
        Fehler("Als Parameter nur eine Zahl...")
    if (L<0) or (L > len(level)-1): Fehler("Zahl zu gross/klein")
    setFeld1(level[L])
    global VersuchtListe
    yx = MannPos(Feld1bew)
    VersuchtListe[yx[0]][yx[1]].append(Feld1bew)
    global ProbierListe
    ProbierListe.append(Feld1bew)
    while len(ProbierListe) > 0:
        d = ProbierListe[0]
        if type(d) == type({}):
            d2 = []
            d2.append(d)
            Knacken(d2)
        else:
            Knacken(d)
        del ProbierListe[0]
    if ZeigAlleLoesungen:
        ErgebnisZeigen('')

Suchen()
Wie man an Zeile 223-275 sehen kann, probier ich die ganze Sache noch schneller zu machen(manche Felder mit einem 400MHZ über 1Std :oops: ). Das was so lange dauert ist Listen mit Dict's zu kopieren - hab noch keinen schnelleren Weg gefunden als wie mit copy.copy()

Das Programm nutzt mawe's levelset1.py -als Parameter die Nummer des gewünschten Feldes übergeben.
Beispiel:(wenn Code den Namen knacksoko.py bekommt)

knacksoko.py 1 > Loesung.txt

In diesem Fall wird das 2.Feld gecheckt und ein Lösungsweg in Loesung.txt gespeichert.

Zerreisst mich nicht wenn ihr den Code so grausam findet - noch nicht so lange Python...
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 29. April 2005, 20:19

:D Ist ja witzig!

Aber die auskommentierten Stellen brauchst du nicht zu posten...
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Gast

Freitag 29. April 2005, 20:50

Aber die auskommentierten Stellen brauchst du nicht zu posten...
Tschuldigung :oops:

Hatte nur gehofft das irgendjemand was besseres einfällt :wink: wollte zeigen das ich einiges probiert habe. Genau dieser Punkt hatte mir am meisten Probleme gemacht - wusste nicht das diese Variablen wie Pointer sind...nur deshalb muß ich die Listen kopieren und Programm so langsam... :(
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 29. April 2005, 21:01

Anonymous hat geschrieben:
Aber die auskommentierten Stellen brauchst du nicht zu posten...
Tschuldigung :oops:
Kein Problem.. ich wollts nur anmerken.
Anonymous hat geschrieben:Hatte nur gehofft das irgendjemand was besseres einfällt :wink: wollte zeigen das ich einiges probiert habe. Genau dieser Punkt hatte mir am meisten Probleme gemacht - wusste nicht das diese Variablen wie Pointer sind...nur deshalb muß ich die Listen kopieren und Programm so langsam... :(
Ich guck mir das Ding mal an, denn die globals müssen weg.. vielleicht kann man es ja kürzer fassen. Mal sehen wann ich Zeit habe :roll:
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Gast

Freitag 29. April 2005, 21:15

@Leonidas

Mercy, da bin aber mal gespannt...:)


Ich hatte gedacht das so ein Feld in ein paar Sekunden geknackt sein kann - aber mit vielen Kisten/Diamanten gibt es doch Millionen(?) Stellungs-Möglichkeiten.
Gast

Montag 9. Mai 2005, 15:29

Hab das Programm optimiert, tote Stellungen werden gleich am Anfang berechnet und während der Suche verworfen. Auf diese Weise ist die Suche jetzt bei einigen Feldern -je nach Feldbeschaffenheit- 25x schneller, manche Felder aber kaum schneller.
Aber wenn man bedenkt das z.B. Feld22 9227446944279201 (9Trillionen) verschiedene Stellungen einnehmen kann, dann sollte man eine schnelle CPU voraussetzen. (Spielt solche Felder überhaupt jemand?)

Code: Alles auswählen

#!/usr/bin/env python
    
import levelset1, sys, copy, time 
    
###>>> diese Variablen anpassen:
ZeigAlleLoesungen = 0       # 1=sucht nach allen Moeglichkeiten: viel Zeit/RAM
                            # 0=erster Loesungsweg wird gezeigt und dann Exit
MaxVersuche       = 5000000 # 
MaxVerlauf        = 300     # max Schritte bis Loesung: 
                            # zu klein=evtl keine Loesung, zu gross=viel Zeit/RAM
###<<<

Mauer        =  "#"  
Ziel         =  "."  
Mann         =  "@"  
Diamant      =  "$"  
DiamantZiel  =  "*"  
leer         =  " "  
MannZiel     =  "+"  
ausserhalb   =  " "


class knacksokoban:
    def __init__(self):
        self.VersuchNr    =  0
        self.FeldHoehe    =  0
        self.FeldBreite   =  0
        self.Feld1        =  {}
        self.Feld1bew     =  {} # nur die beweglichen Figuren
        self.Spielfeld    =  {} # Spielflaeche ohne Aussenfelder und Mauern
        self.TotesDFeld   =  {} # fuer Diamanten tote Felder
        self.StartZeit    =  time.time()
        self.VersuchtListe=  [] # bereits probierte Felder - kein Ergebnis
        self.ProbierListe =  [] # Felder(inkl. Verlauf) die noch probiert werden muessen
        self.BingoListe   =  [] # gefundene Ergebnisse(ganzer Verlauf)
    
    def Fehler(self,s):
        print s
        sys.exit(1)
    
    def MannPos(self,F): # wo ist der Mann ?
        for i in F.keys():
            if F[i] in ["@","+"]:
                return i
    
    def getSpielfeld(self,F):
        yx = self.MannPos(F)
        SF = {(yx[0],yx[1]):[yx[0],yx[1]]}
        weiter = 1
        while weiter:
            weiter = 0
            K = SF.keys()
            for i in range(len(K)):
                Pos = K[i]
                yx = SF[Pos]
                y = (yx[0])
                x = (yx[1])
                if (self.Feld1.get((y,x+1),"?") in [" ","@","+",".","$","*"]) :
                    if not SF.has_key((y,x+1)):   # rechts
                        SF[(y,x+1)] = [y,x+1]
                        weiter = 1
                if (self.Feld1.get((y,x-1),"?") in [" ","@","+",".","$","*"]) :
                    if not SF.has_key((y,x-1)):   # links
                        SF[(y,x-1)] = [y,x-1]
                        weiter = 1
                if (self.Feld1.get((y-1,x),"?") in [" ","@","+",".","$","*"]) :
                    if not SF.has_key((y-1,x)):   # oben
                        SF[(y-1,x)] = [y-1,x]
                        weiter = 1
                if (self.Feld1.get((y+1,x),"?") in [" ","@","+",".","$","*"]) :
                    if not SF.has_key((y+1,x)):   # unten
                        SF[(y+1,x)] = [y+1,x]
                        weiter = 1
        return SF

    # waagerechte Wand fuer Diamanten Endstationen?    
    def ToteXDWand(self,y,x,y2):
        if (y2<0) or (y2>self.FeldHoehe): return 0
        x1 = x
        x2 = x
        DNr = 0
        ZNr = 0
        while (x1-1>0):
            if (self.Feld1[(y,x1-1)] == Mauer):
                break
            x1 = x1 - 1
        while (x2+1<self.FeldBreite):
            if (self.Feld1[(y,x2+1)] == Mauer):
                break
            x2 = x2 + 1
        for i in range(x1-1,x2+2):
            if self.Feld1.get((y2,i),"?") <> Mauer:
                return 0    
        for i in range(x1,x2+1):
            if self.Feld1[(y,i)] in [Ziel,MannZiel]:
                ZNr = ZNr + 1
            if self.Feld1[(y,i)] == DiamantZiel:
                ZNr = ZNr + 1
                DNr = DNr + 1
            if self.Feld1[(y,i)] == Diamant:
                DNr = DNr + 1
        if (ZNr == 0) or (DNr > ZNr): return 1
        return 0
    
    # senkrechte Wand fuer Diamanten Endstationen?    
    def ToteYDWand(self,y,x,x2):
        if (x2<0) or (x2>=self.FeldBreite): return 0
        y1 = y
        y2 = y
        DNr = 0
        ZNr = 0
        while (y1-1>0):
            if (self.Feld1[(y1-1,x)] == Mauer):
                break
            y1 = y1 - 1
        while (y2+1<self.FeldHoehe):
            if (self.Feld1[(y2+1,x)] == Mauer):
                break
            y2 = y2 + 1
        for i in range(y1-1,y2+2):
            if self.Feld1.get((i,x2),"?") <> Mauer:
                return 0    
        for i in range(y1,y2+1):
            if self.Feld1[(i,x)] in [Ziel,MannZiel]:
                ZNr = ZNr + 1
            if self.Feld1[(i,x)] == DiamantZiel:
                ZNr = ZNr + 1
                DNr = DNr + 1
            if self.Feld1[(i,x)] == Diamant:
                DNr = DNr + 1
        if (ZNr == 0) or (DNr > ZNr): return 1
        return 0
    
    # Setup diverser Variablen
    def setFeld1(self,F): 
        f = F.split("\n")
        self.FeldBreite = 0
        self.FeldHoehe = len(f)
        for i in range(len(f)): # maximale Breite rausbekommen
            while (len(f[i])>0) and (f[i][len(f[i])-1]==" "): 
                f[i] = f[i][0:len(f[i])-1]
            if len(f[i]) > self.FeldBreite :
                self.FeldBreite = len(f[i])
        for y in range(self.FeldHoehe):
            for x in range(self.FeldBreite):
                try:
                    if f[y][x] in [" ",".","*","@","+","#","$","?"]:
                        self.Feld1[(y,x)] = f[y][x]
                    if f[y][x] in [".","*","@","+","$"]:
                        self.Feld1bew[(y,x)] = f[y][x]
                    if f[y][x] in [leer,Mann,Diamant]:
                        self.TotesDFeld[(y,x)] = [y,x]
                except: 
                    self.Feld1[(y,x)] = ausserhalb
        self.VersuchtListe = self.FeldHoehe * [[0]]
        for y in range(self.FeldHoehe):
            self.VersuchtListe[y] = self.FeldBreite * [[0]]
        self.Spielfeld = self.getSpielfeld(self.Feld1)
        for i in self.TotesDFeld.keys():
            if not self.Spielfeld.has_key(i):
                del self.TotesDFeld[i]
                continue
            yx = self.TotesDFeld[i]
            y = yx[0]
            x = yx[1]
            if (y-1>=0) and (x-1>=0):                 # links oben
                if self.Feld1[(y,x-1)] == Mauer:            #links
                    if self.Feld1[(y-1,x)] == Mauer:        #oben
                        continue
            if (y-1>=0) and (x+1<self.FeldBreite):         # rechts oben
                if self.Feld1[(y,x+1)] == Mauer:            #rechts
                    if self.Feld1[(y-1,x)] == Mauer:        #oben
                        continue
            if (y+1<self.FeldHoehe) and (x+1<self.FeldBreite):  # rechts unten
                if self.Feld1[(y,x+1)] == Mauer:
                    if self.Feld1[(y+1,x)] == Mauer:
                        continue

            if (y+1<self.FeldHoehe) and (x-1>=0):          # links unten
                if self.Feld1[(y,x-1)] == Mauer:
                    if self.Feld1[(y+1,x)] == Mauer:
                        continue
            if (self.Feld1[(y,x)] <> Mauer):
                if (y>=1) and self.ToteXDWand(y,x,y-1): continue
                if (y+1<self.FeldHoehe) and self.ToteXDWand(y,x,y+1): continue
                if (x>=1) and self.ToteYDWand(y,x,x-1): continue
                if (x+1<self.FeldBreite) and self.ToteYDWand(y,x,x+1): continue                
            del self.TotesDFeld[i]
    
    def Bingo(self,F):  # true = Yeah, Weg gefunden
        for i in F.keys():
            if F[i] in ["+",".","$"]:
                return 0
        return 1
    
    def IstNeuesFeld(self,y,x,F): # noch nie benutzte Feld-Konstellation
        return self.VersuchtListe[y][x].count(F) == 0
    
    def DiamantInEcke(self,Feld): # noch weiterprobieren > Quatsch
        for i in Feld.keys():
            if Feld[i] == "$":
                if self.TotesDFeld.has_key(i):
                    return 1
        return 0 
    
    def ErgebnisZeigen(self,s):
        print s
        if len(self.BingoListe) < 1:
            print "Kein Ergebnis gefunden..."
            sys.exit(0)
        stime = str(time.time() - self.StartZeit)
        print "Suchzeit : ",stime[:stime.find(".")+4]," Sek."
        F1 = self.Feld1.copy()
        for i in F1.keys():
            if F1[i] in ["@",".","*","+","$"]:
                F1[i] = leer
        yxalt = [0,0]
        yxneu = [0,0]
        for x in range(len(self.BingoListe)):
            print
            print "Ergebnis ",x + 1
            for i in range(len(self.BingoListe[x])): 
                print
                print "Schritt", i,"  ",
                F = F1.copy()
                d = self.BingoListe[x][i]
                d = d.keys()
                for dd in d:
                    F[dd] = self.BingoListe[x][i][dd]
                yxalt = yxneu
                yxneu = self.MannPos(self.BingoListe[x][i])
                if i > 0:
                    if yxneu[0] < yxalt[0]:     # nach oben
                        print "hoch"
                    elif yxneu[0] > yxalt[0]:  # nach unten
                        print "runter"
                    elif yxneu[1] < yxalt[1]:  # links
                        print "links"
                    elif yxneu[1] > yxalt[1]:  # rechts
                        print "rechts"
                else: 
                    print
                for y2 in range(self.FeldHoehe):
                    s = ""
                    for x2 in range(self.FeldBreite):
                        s = s + F[(y2,x2)]
                    print s                 
        sys.exit(0)
    
    # hier findet die eigentliche/meiste Suche statt
    def GehZuFeld(self,vonX,vonY,nachX,nachY,nachX2,nachY2,Verlauf,neu):
        # erstmal checken ob ueberhaupt gesprungen werden kann...
        if (nachX < 0) or (nachX > self.FeldBreite-1): return 0
        if (nachY < 0) or (nachY > self.FeldHoehe-1): return 0
        if (self.Feld1[(nachY,nachX)] in [Mauer]): return 0
        neu = neu.copy()
        # Diamant verschieben geht nicht ?
        if neu.has_key((nachY,nachX)):
            if (neu[(nachY,nachX)] in [Diamant,DiamantZiel]):
                if (nachX2 < 0) or (nachY2 < 0): return 0
                if (nachX2 > self.FeldBreite-1) or (nachY2 > self.FeldHoehe-1): return 0
                if (self.Feld1[(nachY2,nachX2)] in [Mauer]): return 0
                if neu.has_key((nachY2,nachX2)):
                    if (neu[(nachY2,nachX2)] in [Mauer,Diamant,DiamantZiel]): return 0
                else:
                    neu[(nachY2,nachX2)] = leer
        else:
            neu[(nachY,nachX)] = leer
        # Es kann gesprungen werden
        if neu[(vonY,vonX)] == Mann:  # Altes Feld wieder herstellen
            del neu[(vonY,vonX)]
        elif neu[(vonY,vonX)] == MannZiel:
            neu[(vonY,vonX)] = Ziel
        if neu[(nachY,nachX)] == Diamant:
            neu[(nachY,nachX)] = Mann
            if neu[(nachY2,nachX2)] == leer: neu[(nachY2,nachX2)] = Diamant
            elif neu[(nachY2,nachX2)] == Ziel: neu[(nachY2,nachX2)] = DiamantZiel
        elif neu[(nachY,nachX)] == DiamantZiel:
            neu[(nachY,nachX)] = MannZiel
            if neu[(nachY2,nachX2)] == leer: neu[(nachY2,nachX2)] = Diamant
            elif neu[(nachY2,nachX2)] == Ziel: neu[(nachY2,nachX2)] = DiamantZiel
        if neu[(nachY,nachX)] == Ziel: neu[(nachY,nachX)] = MannZiel 
        elif neu[(nachY,nachX)] == leer: neu[(nachY,nachX)] = Mann 
         # alle Diamanten im Ziel?
        if self.Bingo(neu):
            Verlauf = copy.copy(Verlauf)
            Verlauf.append(neu)
            self.BingoListe.append(Verlauf)
            if not ZeigAlleLoesungen:
                self.ErgebnisZeigen('Bei der 1. Loesung Suche abgebrochen...')
            return 0 
        else:    
            if self.DiamantInEcke(neu) or (not self.IstNeuesFeld(vonY,vonX,neu)):
                pass
            else: 
                # diese Konstellation gabs noch nicht, in Versuchsliste uebernehmen
                self.VersuchtListe[vonY][vonX].append(neu)
                Verlauf = Verlauf[:]
                neu = copy.copy(neu)
                Verlauf.append(neu)
                self.ProbierListe.append(Verlauf)
                return 1
    
    def Knacken(self,Verlauf): # Vorarbeit
        if (self.VersuchNr > MaxVersuche):
             ErgebnisZeigen('Nach '+str(MaxVersuche)+' Versuchen sollte abgebrochen werden.')
        self.VersuchNr = self.VersuchNr + 1
        if len(Verlauf) >= MaxVerlauf: return 0 #nicht weiter suchen
        Feld = Verlauf[len(Verlauf)-1]
        yx = self.MannPos(Feld)
        y = yx[0]
        x = yx[1]
        
        # oben
        self.GehZuFeld(x,y,x,y-1,x,y-2,Verlauf,Feld) 
        # unten
        self.GehZuFeld(x,y,x,y+1,x,y+2,Verlauf,Feld) 
        # rechts
        self.GehZuFeld(x,y,x+1,y,x+2,y,Verlauf,Feld)
        # links
        self.GehZuFeld(x,y,x-1,y,x-2,y,Verlauf,Feld)
    
    def Suchen(self):
        level = levelset1.levels
        if len(sys.argv) <= 1: Fehler("Kein Parameter uebergeben, z.B.:  2")
        try:
            L = int(sys.argv[1])
        except:
            Fehler("Als Parameter nur eine Zahl...")
        if (L<0) or (L > len(level)-1): Fehler("Zahl zu gross/klein")
        self.setFeld1(level[L])
        bew = 1 #Mann
        for i in self.Spielfeld.keys():
            if self.Feld1[i] in ["$","*"]:
                bew = bew + 1
        print "Feld kann",len(self.Spielfeld)**bew,"Stellungen haben..."
        yx = self.MannPos(self.Feld1bew)
        self.VersuchtListe[yx[0]][yx[1]].append(self.Feld1bew)
        self.ProbierListe.append(self.Feld1bew)
        while len(self.ProbierListe) > 0:
            d = self.ProbierListe[0]
            if type(d) == type({}):
                d2 = []
                d2.append(d)
                self.Knacken(d2)
            else:
                self.Knacken(d)
            del self.ProbierListe[0]
        if ZeigAlleLoesungen:
            self.ErgebnisZeigen('')


KS = knacksokoban()    
KS.Suchen()
Antworten