[SOLVED] html AI eightpuzzle.py (original)

eightpuzzle.py (original)

# eightpuzzle.py
#
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero ([email protected]) and Dan Klein ([email protected]).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

import search
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
.join(lines)

def __str__(self):
return self.__getAsciiString()

# TODO: Implement The methods in this class

class EightPuzzleSearchProblem(search.SearchProblem):

Implementation of a SearchProblem for theEight 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

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 succesor is either left, right, up, or down
from the original state and the cost is 1.0 for each

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

if __name__ == __main__:
puzzle = createRandomEightPuzzle(25)
print(A random puzzle:)
print(puzzle)

problem = EightPuzzleSearchProblem(puzzle)
path = search.breadthFirstSearch(problem)
print(BFS found a path of %d moves: %s % (len(path), str(path)))
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