import search import util import random # Module Classes class EightPuzzleState: """ The Eight Puzzle is described in the course textbook on page 64. This class defines the mechanics of the puzzle itself. The task of recasting this puzzle as a search problem is left to the EightPuzzleSearchProblem class. """ def __init__( self, numbers ): """ Constructs a new eight puzzle from an ordering of numbers. numbers: a list of integers from 0 to 8 representing an instance of the eight puzzle. 0 represents the blank space. Thus, the list [1, 0, 2, 3, 4, 5, 6, 7, 8] represents the eight puzzle: ------------- | 1 | | 2 | ------------- | 3 | 4 | 5 | ------------- | 6 | 7 | 8 | ------------ The configuration of the puzzle is stored in a 2-dimensional list (a list of lists) 'cells'. """ self.cells = [] numbers = numbers[:] # Make a copy so as not to cause side-effects. numbers.reverse() for row in range( 3 ): self.cells.append( [] ) for col in range( 3 ): self.cells[row].append( numbers.pop() ) if self.cells[row][col] == 0: self.blankLocation = row, col def isGoal( self ): """ Checks to see if the puzzle is in its goal state. ------------- | | 1 | 2 | ------------- | 3 | 4 | 5 | ------------- | 6 | 7 | 8 | ------------- >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).isGoal() True >>> EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).isGoal() False """ current = 0 for row in range( 3 ): for col in range( 3 ): if current != self.cells[row][col]: return False current += 1 return True def legalMoves( self ): """ Returns a list of legal moves from the current state. Moves consist of moving the blank space up, down, left or right. These are encoded as 'up', 'down', 'left' and 'right' respectively. >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).legalMoves() ['down', 'right'] """ moves = [] row, col = self.blankLocation if(row != 0): moves.append('up') if(row != 2): moves.append('down') if(col != 0): moves.append('left') if(col != 2): moves.append('right') return moves def result(self, move): """ Returns a new eightPuzzle with the current state and blankLocation updated based on the provided move. The move should be a string drawn from a list returned by legalMoves. Illegal moves will raise an exception, which may be an array bounds exception. NOTE: This function *does not* change the current object. Instead, it returns a new object. """ row, col = self.blankLocation if(move == 'up'): newrow = row - 1 newcol = col elif(move == 'down'): newrow = row + 1 newcol = col elif(move == 'left'): newrow = row newcol = col - 1 elif(move == 'right'): newrow = row newcol = col + 1 else: raise "Illegal Move" # Create a copy of the current eightPuzzle newPuzzle = EightPuzzleState([0, 0, 0, 0, 0, 0, 0, 0, 0]) newPuzzle.cells = [values[:] for values in self.cells] # And update it to reflect the move newPuzzle.cells[row][col] = self.cells[newrow][newcol] newPuzzle.cells[newrow][newcol] = self.cells[row][col] newPuzzle.blankLocation = newrow, newcol return newPuzzle # Utilities for comparison and display def __eq__(self, other): """ Overloads '==' such that two eightPuzzles with the same configuration are equal. >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]) == \ EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).result('left') True """ for row in range( 3 ): if self.cells[row] != other.cells[row]: return False return True def __hash__(self): return hash(str(self.cells)) def __getAsciiString(self): """ Returns a display string for the maze """ lines = [] horizontalLine = ('-' * (13)) lines.append(horizontalLine) for row in self.cells: rowLine = '|' for col in row: if col == 0: col = ' ' rowLine = rowLine + ' ' + col.__str__() + ' |' lines.append(rowLine) lines.append(horizontalLine) return '\n'.join(lines) def __str__(self): return self.__getAsciiString() # TODO: Implement The methods in this class class EightPuzzleSearchProblem(search.SearchProblem): """ Implementation of a SearchProblem for the Eight Puzzle domain Each state is represented by an instance of an eightPuzzle. """ def __init__(self,puzzle): "Creates a new EightPuzzleSearchProblem which stores search information." self.puzzle = puzzle self._expanded = 0 def getStartState(self): return puzzle def isGoalState(self,state): return state.isGoal() def getSuccessors(self,state): """ Returns list of (successor, action, stepCost) pairs where each successor is either left, right, up, or down from the original state and the cost is 1.0 for each """ self._expanded += 1 succ = [] for a in state.legalMoves(): succ.append((state.result(a), a, 1)) return succ def getCostOfActions(self, actions): """ actions: A list of actions to take This method returns the total cost of a particular sequence of actions. The sequence must be composed of legal moves """ return len(actions) EIGHT_PUZZLE_DATA = [[1, 0, 2, 3, 4, 5, 6, 7, 8], [1, 7, 8, 2, 3, 4, 5, 6, 0], [4, 3, 2, 7, 0, 5, 1, 6, 8], [5, 1, 3, 4, 0, 2, 6, 7, 8], [1, 2, 5, 7, 6, 8, 0, 4, 3], [0, 3, 1, 6, 8, 2, 7, 5, 4]] def loadEightPuzzle(puzzleNumber): """ puzzleNumber: The number of the eight puzzle to load. Returns an eight puzzle object generated from one of the provided puzzles in EIGHT_PUZZLE_DATA. puzzleNumber can range from 0 to 5. >>> print loadEightPuzzle(0) ------------- | 1 | | 2 | ------------- | 3 | 4 | 5 | ------------- | 6 | 7 | 8 | ------------- """ return EightPuzzleState(EIGHT_PUZZLE_DATA[puzzleNumber]) def createRandomEightPuzzle(moves=100): """ moves: number of random moves to apply Creates a random eight puzzle by applying a series of 'moves' random moves to a solved puzzle. """ puzzle = EightPuzzleState([0,1,2,3,4,5,6,7,8]) for i in range(moves): # Execute a random legal move puzzle = puzzle.result(random.sample(puzzle.legalMoves(), 1)[0]) return puzzle def numMisplacedHeuristic(state, problem): """ use state.cells[x][y] to get the contents of (x,y) in the problem """ misplaced = 0 current = 0 for row in range(3): for col in range(3): if state.cells[row][col] != current: if current != 0: misplaced += 1 current += 1 return misplaced def manhattanMisplacedHeuristic(state, problem): """ use state.cells[x][y] to get the contents of (x,y) in the problem use util.manhattanDistance((x1,y1), (x2,y2)) """ dist = 0 current = 0 for row in range(3): for col in range(3): r = state.cells[row][col] / 3 c = state.cells[row][col] % 3 if current > 0: dist += util.manhattanDistance((row,col), (r,c)) current += 1 return dist if __name__ == '__main__': import sys, time verbose = False #puzzle = createRandomEightPuzzle(25) #print('A random puzzle:') puzzle = loadEightPuzzle(1) print(puzzle) start_time = time.time() problem = EightPuzzleSearchProblem(puzzle) #path = search.breadthFirstSearch(problem) #path = search.aStarSearch(problem, numMisplacedHeuristic) path = search.aStarSearch(problem, manhattanMisplacedHeuristic) print('found a path of %d moves: %s' % (len(path), str(path))) print 'nodes expanded [%d]' %problem._expanded print 'time (secs) [%1.2f]' %(time.time() - start_time) if not verbose: sys.exit() curr = puzzle i = 1 for a in path: curr = curr.result(a) print('After %d move%s: %s' % (i, ("", "s")[i>1], a)) print(curr) #raw_input("Press return for the next state...") # wait for key stroke i += 1