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])
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] != compareTo.elements[j]:
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*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] = 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] == -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
