#-*- coding:Utf-8 -*- #=============================================================================== # enigme-135.py # Resoud l'enigme 135 du jeu "Professeur layton et l'etrange village" sur # Nintendo DS. Utilise un brute force pas beau pour faire ce taquin. # # # 0───1──┐2───3──┐4──┐5 # └──────┘└──────┘└──┘ # 6───7──┐8──┐9──┐10 11 # │ ││ │└──┘ # 12 13 │14 │15─┐16 17 # └──────┘└──┘└──┘ # 18──19─┐20──21─┐22─┐23 # └──────┘└──────┘└──┘ #=============================================================================== #imports import string # Consts PUZZLE_SIZE = 22 DIRECTIONS = { 'UP' : 1, 'RIGHT' : 2, 'DOWN' : 3, 'LEFT' : 4 } PC_HORIZ_RECT = '<' PC_VERTI_RECT = '^' PC_GROS_CARRE = '1' PC_PETT_CARRE = '@' FREE_PLACES_NEEDED = { PC_GROS_CARRE : { 'UP' : { 0 : True , 1 : -6, 2 : -5, 3 : -6 }, 'RIGHT' : { 0 : True , 1 : +2, 2 : +8, 3 : +1 }, 'DOWN' : { 0 : True , 1 :+12, 2 :+13, 3 : +6 }, 'LEFT' : { 0 : True , 1 : -1, 2 : +5, 3 : -1 } }, PC_HORIZ_RECT : { 'UP' : { 0 : True , 1 : -6, 2 : -5, 3 : -6 }, 'RIGHT' : { 0 : False, 1 : +2, 2 : 0, 3 : +1 }, 'DOWN' : { 0 : True , 1 : +6, 2 : +7, 3 : +6 }, 'LEFT' : { 0 : False, 1 : -1, 2 : 0, 3 : -1 } }, PC_VERTI_RECT : { 'UP' : { 0 : False, 1 : -6, 2 : 0, 3 : -6 }, 'RIGHT' : { 0 : True , 1 : +1, 2 : +7, 3 : +1 }, 'DOWN' : { 0 : False, 1 :+12, 2 : 0, 3 : +6 }, 'LEFT' : { 0 : True , 1 : -1, 2 : +5, 3 : -1 } }, PC_PETT_CARRE : { 'UP' : { 0 : False, 1 : -6, 2 : 0, 3 : -6 }, 'RIGHT' : { 0 : False, 1 : +1, 2 : 0, 3 : +1 }, 'DOWN' : { 0 : False, 1 : +6, 2 : 0, 3 : +6 }, 'LEFT' : { 0 : False, 1 : -1, 2 : 0, 3 : -1 } } } # Classes class Puzzle(): def __init__(self,puzzle,name): self.puzzle = puzzle self.name = name def explore(self,lists): child = 0 childsName = list() # check for every piece of puzzle for position in range(len(self.puzzle)): if (self.puzzle[position] == '<' or self.puzzle[position] == '@' or self.puzzle[position] == '^' or self.puzzle[position] == '1'): if self.puzzle[position] == '<': piece = PC_HORIZ_RECT elif self.puzzle[position] == '@': piece = PC_PETT_CARRE elif self.puzzle[position] == '^': piece = PC_VERTI_RECT elif self.puzzle[position] == '1': piece = PC_GROS_CARRE # check if can move in any direction for direction in DIRECTIONS.keys(): if self.canMove(direction,piece,position): childName = "%s-%d" % (self.name,child) newPuzzle = self.createPuzzle(direction,piece,position,childName) duplicate = lists.puzzleExists(newPuzzle) if duplicate == None: lists.addPuzzle(newPuzzle) childsName.append(childName) child = child + 1 else: if (not (self.puzzle[position] == ' ' or self.puzzle[position] == '2' or self.puzzle[position] == '3' or self.puzzle[position] == '4' or self.puzzle[position] == '>' or self.puzzle[position] == 'v' or self.puzzle[position] == '\n')): sys.stderr.write("Unknown puzzle piece : '%s'" % self.puzzle[position]) sys.exit(-1) def isFinal(self): if self.puzzle[9] == '1': return True else: return False def display(self): print "========================================================================" print "Puzzle. [Name: " + self.name + "]" print "------------------------------------------------------------------------" print string.join( self.puzzle, '' ) print "========================================================================" def canMove(self,direction,piece,position): # Calculate where free places need to be twoPlace = FREE_PLACES_NEEDED[piece][direction][0] pos1 = position + FREE_PLACES_NEEDED[piece][direction][1] pos2 = position + FREE_PLACES_NEEDED[piece][direction][2] # Want to move out off the puzzle ? if (pos1 > PUZZLE_SIZE or pos1 < 0 or pos2 > PUZZLE_SIZE or pos2 < 0 or pos1 % 6 == 5 or pos2 % 6 == 5): return False # Places free ? if (self.puzzle[pos1] == ' ' and ( not twoPlace or self.puzzle[pos2] == ' ')): return True else: return False def createPuzzle(self,direction,piece,position,name): newPuzzle = self.puzzle[:] # Calculate new positions newPosition = position + FREE_PLACES_NEEDED[piece][direction][3] #Draw blanks if(piece == PC_GROS_CARRE): newPuzzle[position] = ' ' newPuzzle[position+1] = ' ' newPuzzle[position+6] = ' ' newPuzzle[position+7] = ' ' elif(piece == PC_HORIZ_RECT): newPuzzle[position] = ' ' newPuzzle[position+1] = ' ' elif(piece == PC_VERTI_RECT): newPuzzle[position] = ' ' newPuzzle[position+6] = ' ' elif(piece == PC_PETT_CARRE): newPuzzle[position] = ' ' # Draw piece in new position if(piece == PC_GROS_CARRE): newPuzzle[newPosition] = '1' newPuzzle[newPosition+1] = '2' newPuzzle[newPosition+6] = '3' newPuzzle[newPosition+7] = '4' elif(piece == PC_HORIZ_RECT): newPuzzle[newPosition] = '<' newPuzzle[newPosition+1] = '>' elif(piece == PC_VERTI_RECT): newPuzzle[newPosition] = '^' newPuzzle[newPosition+6] = 'v' elif(piece == PC_PETT_CARRE): newPuzzle[newPosition] = '@' # Init new node newPuzzleObject = Puzzle(newPuzzle,name) return newPuzzleObject class Lists: def __init__(self): self.puzzles = list() self.toExplore = list() self.finalNodesNames = list() def exploreNext(self): if len(self.toExplore) > 0: next = self.toExplore.pop(0) next.explore(self) return True else: return False def addPuzzle(self,puzzle): if puzzle.isFinal(): self.finalNodesNames.append(puzzle.name) self.toExplore.append(puzzle) self.puzzles.append(puzzle) def puzzleExists(self,newPuzzle): for i in range(len(self.puzzles)-1,0,-1): if(newPuzzle.puzzle == self.puzzles[i].puzzle): return self.puzzles[i].name return None def displaySteps(self,nameToDisplay): for i in range(0,len(self.puzzles)-1,1): if nameToDisplay.startswith(self.puzzles[i].name): self.puzzles[i].display() # init print "Initializating" lists = Lists() lists.addPuzzle(Puzzle(['<','>','<','>','@','\n', '1','2','^','@',' ','\n', '3','4','v','@',' ','\n', '<','>','<','>','@'], "0")) # generate puzzle lists print "Generating puzzles (very long)" while lists.exploreNext(): pass # display first solution steps print "Solution steps :" lists.displaySteps(lists.finalNodesNames[0])