I moved this from code review because folks over there suggest this should be posted here
I'm trying to do 8-puzzle using pycharm, I will first generate a 3x3 list and then shuffle it to get the initial board state example:
[1 , 2 , 3 ] [4 , 5 , 6 ] [7 , 8 , 9 ]
then I'll do some random moves on it to get the goal board state:
[ 3 , 2 , 1 ] [ 6 , 5 , 4 ] [ 9 , 8 , 7 ]
when I set the size to be 3(3x3) it never complete the search, and when I set the size to be 2 it solves but sometimes it will exhaust the frontier list and returns nothing, which should not be possible.
EDIT
I changed the
return Solution (start_node, numExplored, memoryRequired)
to
return Solution (fr_node, numExplored, memoryRequired)
and it always return an solution for 2x2 , 3x3 is still very slow though
I have these code in Python:
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
frontier = util.Queue()
explored = []
numExplored = 0
memoryRequired = 0
# generate start node
start_node = Node(problem.getStartState(), None, 0, None)
# return immediately if start node is the goal state
if problem.isGoalState(start_node.state):
return Solution(start_node, 0, 0)
# push start node into frontier
frontier.push (start_node)
# while frontier list is not empty
while not frontier.isEmpty():
# get the first-in frontier node from frontier list
fr_node = frontier.pop()
explored.append(fr_node)
# get successor nodes
successors = problem.getSuccessors(fr_node.state)
numExplored += 1
# append into explored list
# if len(successors) >0:
# explored.append(fr_node)
# else:
# explored.append(fr_node)
# for each successor node
for sc_state, sc_action, sc_cost in successors:
# generate successor node
sc_node = Node(sc_state, sc_action, sc_cost, fr_node)
# check for goal state immediately after generate
if problem.isGoalState(sc_node.state): # if found solution
return Solution (sc_node, numExplored, memoryRequired)
# insert successor node into frontier list (if not found in explored and frontier)
if sc_node not in explored and sc_node not in frontier.list:
frontier.push(sc_node)
memoryRequired = max ([memoryRequired, len(frontier.list)+len(explored)])
print ('Frontier size = %d, Explored size = %d, Total size = %d ,Successor Length= %d' %(len(frontier.list), len(explored), len(frontier.list)+len(explored), len(successors)))
return Solution (start_node, numExplored, memoryRequired)
Node is defined as:
class Node:
def __init__(self, state, action, cost, parent):
self.state = state
self.cost = cost
self.action = action
self.parent = parent
if parent is None:
self.totalCost = cost
self.depth = 0
else:
self.totalCost = parent.totalCost + cost
self.depth = parent.depth + 1
def __eq__(self, other):
return hasattr(other,'state') and self.state == other.state
and then there's the file that defines NPuzzle and Puzzle state.
class ActionType:
UP = 'up'
DOWN = 'down'
LEFT = 'left'
RIGHT = 'right'
Actions = [ActionType.UP, ActionType.DOWN, ActionType.LEFT,
ActionType.RIGHT]
class PuzzleState (SearchState):
def __init__ (self, n, board = None):
self.n = n
self.board = [[j for j in range(n*i,n*i+n)] for i in range(n)]
self.blankCellPos = self.getBlankCellPos()
def __eq__ (self, other):
if self.board == other.board:
return True
else:
return False
def deepCopy(self):
state = copy.deepcopy(self) #PuzzleState(self.n)
return state
def getBlankCellPos (self):
for i in range(self.n):
for j in range(self.n):
if self.board[i][j] == 0:
return (i,j)
def isValidAction (self, action):
(r,c)= self.blankCellPos
if action == ActionType.UP:
if r - 1 < 0:
return False
else:
return True
elif action == ActionType.DOWN:
if r + 1 > self.n-1:
return False
else:
return True
elif action == ActionType.LEFT:
if c - 1 < 0:
return False
else:
return True
elif action == ActionType.RIGHT:
if c + 1 > self.n-1:
return False
else:
return True
def getValidActions (self):
ValidActions = []
for action in Actions:
if(self.isValidAction(action) == True):
ValidActions.append(action)
return ValidActions
def move (self, action):
(r,c) = self.blankCellPos
if action == ActionType.UP:
self.blankCellPos = (r-1,c)
self.board[r][c], self.board[r-1][c] = self.board[r-1][c], self.board[r][c]
elif action == ActionType.DOWN:
self.blankCellPos = (r+1,c)
self.board[r][c], self.board[r+1][c] = self.board[r+1][c], self.board[r][c]
elif action == ActionType.LEFT:
self.blankCellPos = (r, c-1)
self.board[r][c], self.board[r][c-1] = self.board[r][c-1], self.board[r][c]
elif action == ActionType.RIGHT:
self.blankCellPos = (r, c+1)
self.board[r][c], self.board[r][c+1] = self.board[r][c+1], self.board[r][c]
def randomMove (self, numMoves):
#(r,c) = self.board.blankCellPos
ValidActions = []
actions = []
tmp = -1
for num in range(numMoves):
ValidActions = self.getValidActions()
tmp = random.choice(ValidActions)
#remove loopy choices#
if num > 0:
if actions[-1] == ActionType.UP and tmp == ActionType.DOWN:
ValidActions.remove(ActionType.DOWN)
tmp = random.choice(ValidActions)
elif actions[-1] == ActionType.DOWN and tmp == ActionType.UP:
ValidActions.remove(ActionType.UP)
tmp = random.choice(ValidActions)
elif actions[-1] == ActionType.LEFT and tmp == ActionType.RIGHT:
ValidActions.remove(ActionType.RIGHT)
tmp = random.choice(ValidActions)
elif actions[-1] == ActionType.RIGHT and tmp == ActionType.LEFT:
ValidActions.remove(ActionType.LEFT)
tmp = random.choice(ValidActions)
actions.append(tmp)
self.move(tmp)
def randomInitialize (self):
random.shuffle(self.board)
for ii, sublist in enumerate(self.board):
random.shuffle(self.board[ii])
self.blankCellPos = self.getBlankCellPos()
def display (self):
print( ' ',)
#for c in range (self.n):
print (self.board)
#print (' %d' %(c),)
class NPuzzle (SearchProblem):
def __init__ (self, n, startState = None, goalState = None):
self.n = PuzzleState(n)
self.startState = self.n.deepCopy()
self.goalState = self.n.deepCopy()
def randomStartState (self):
self.startState.randomInitialize()
def randomGoalState(self, numMoves):
self.goalState.randomMove(numMoves)
def setStartState (self, startState):
self.startState = startState
def setGoalState (self, goalState):
self.goalState = goalState
def getStartState (self):
return self.startState
def getGoalState (self):
return self.goalState
def isGoalState(self, state):
if state == self.goalState:
return True
else:
return False
def getSuccessors (self, state):
successorlist = []
validActions = state.getValidActions()
for action in validActions:
#if not deep copy what will happen?
successor = state.deepCopy()
successor.move(action)
self.cost = 1
successorlist.append([successor, action, self.cost])
return successorlist
According to what I read and what my lecturer told me , the machine should punch out something around thousands of searches every second but when I run it it only appear to be very fast at the first few thousand nodes and then slows down terribly after that.
I have no idea what's wrong. Any hint will be greatly appreciated.
