Thanks for the code. What I want to do is this: I want to solve the block puzzle problem. The problem is as follows: You have a nxn Array of Numbers and one empty space. Now you there are up to four possible moves: up, right, down and left, so that each neighbour of the empty slot can be moved there.
The method getEmptySlot is for getting the empty slot. The method getPossibleMoves returns the possible moves. Perfoming a move is swaping one element with the empty slot marked as -1. The full executable code is appended. The expected behaviour is that when the move is performed the appropiate elements should be swaped. But for some reason every now and then it swaps the wrong elements. # Puzzle.py # class for a sliding block puzzle # an starting state of a 8-puzzle could look like the following: # ------------ # | 7 2 4 | # | | # | 5 X 6 | # | | # | 8 3 1 | # ------------ # the goal is to reach this state: # ------------ # | X 1 2 | # | | # | 3 4 5 | # | | # | 6 7 8 | # ------------ import random import copy class Puzzle: def __init__(self, dim): self.dim = dim # self.elements = {} # for column in range(dim): # for row in range(dim): # elements[(column, row)] = 0 self.elements = [[0 for column in range(dim)] for row in range(dim) ] def __str__(self): s = "" i = 0 j = 0 while i <= self.dim-1: while j <= self.dim-1: s = s + str(self.elements[j][i]) j=j+1 s = s + "\t" i=i+1 j = 0 s = s + "\n" return s def compare(self, compareTo): if (self.dim != compareTo.dim): return 0 i = 0 j = 0 equal = 1 while i <= self.dim-1: while j <= self.dim-1: if self.elements[j][i] != compareTo.elements[j][i]: equal = 0 j = j+1 i = i+1 return equal def setAsGoalState(self): # create elements of puzzle i = 0 j = 0 while i <= self.dim-1: while j <= self.dim-1: self.elements[j][i] = i*3+j j=j+1 j=0 i=i+1 # create empty element seperately self.elements[0][0] = -1 def setRandomState(self): # container for the elements to pick from container = [1,2,3,4,5,6,7,8,-1] # create elements of puzzle randomly i = 0 j = 0 while i <= self.dim-1: while j <= self.dim-1: if len(container) > 0: randomindex = random.randint(0,len(container)-1) self.elements[j][i] = container[randomindex] del container[randomindex] j=j+1 else: break j=0 i=i+1 def getEmptySlot(self): i = 0 j = 0 while i <= self.dim-1: while j <= self.dim-1: if self.elements[j][i] == -1: return [j, i] j = j+1 j = 0 i = i + 1 def performMove(self, direction): slot = self.getEmptySlot() if (direction == "up"): self.swapElements(slot[1], slot[0], slot[1]+1, slot[0]) elif (direction == "down"): self.swapElements(slot[1], slot[0], slot[1]-1, slot[0]) elif direction == "left": self.swapElements(slot[1], slot[0], slot[1], slot[0]-1) elif (direction == "right"): self.swapElements(slot[1], slot[0], slot[1], slot[0]+1) def swapElements(self, fromx, fromy, tox, toy): dummy = self.elements[toy][tox] self.elements[toy][tox] = self.elements[fromy][fromx] self.elements[fromy][fromx] = dummy def getChildren(self): moves = self.getPossibleMoves() self.children = [] for eachMove in moves: newchild = copy.copy(self.performMove(eachMove)) try: self.children.append(newchild) except: print "Exception: " + str(len(self.children)) def getPossibleMoves(self): emptySlot = self.getEmptySlot() y = emptySlot[1] x = emptySlot[0] north = (y == 0) south = (y == (self.dim-1)) west = (x == 0) east = (x == (self.dim-1)) middle = not(north or south or west or east) northwest = north and west northeast = north and east southwest = south and west southeast = south and east # orientation has to be distinct # save original values orignorth = north origsouth = south # original north or south orignors = north or south north = north and not (west or east) south = south and not (west or east) west = west and not (orignors) east = east and not (orignors) if middle: return ["up", "down", "left", "right"] elif north: return ["up", "left", "right"] elif south: return ["down", "left", "right"] elif west: return ["up", "down", "left"] elif east: return ["up", "down", "right"] elif northwest: return ["up", "left"] elif northeast: return ["up", "right"] elif southwest: return ["down", "left"] elif southeast: return ["down", "right"] # ~Puzzle.py # SolvePuzzleAgent.py # imports from Puzzle import * from Tree import * import bintree # set up puzzle puzzle = Puzzle(3) puzzle.setRandomState() goalpuzzlestate = Puzzle(3) goalpuzzlestate.setAsGoalState() print "goal state of the puzzle: " print str(goalpuzzlestate) print "start state of the puzzle: " print str(puzzle) #start search tree = bintree.BinaryTree() done = 0 currentBranch = 0 while not done: tree.insert(puzzle) # get the fringe moves = puzzle.getPossibleMoves() children = puzzle.getChildren() #print "possible moves: " + str(moves) print "moving: " + str(moves[currentBranch]) puzzle.performMove(moves[currentBranch]) # test if we're have reached the goal state done = puzzle.compare(goalpuzzlestate) print "done ? : " + str(done) print "state:\n" + str(puzzle) done = 1 print "search tree: " + str(tree.inorder()) # bintree.py # a binary tree class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class BinaryTree: def __init__(self): self.root = None def insert(self, val): root = self.root lastdir = None while root: lastroot = root if val <= root.val: lastdir = 'left' root = root.left else: lastdir = 'right' root = root.right new = Node(val) if lastdir is None: self.root = new elif lastdir == 'left': lastroot.left = new else: lastroot.right = new def insertList(self, list): for x in list: self.insert(x) def inorder(self): result = [] self.__helper(self.root, result) return result def __helper(self, root, result): if root is not None: self.__helper(root.left, result) result.append(root.val) self.__helper(root.right, result) # ~bintree.py -- http://mail.python.org/mailman/listinfo/python-list