nested lists as arrays

[benjamin.cordes at blawrc.de]

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