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.
s/executable/source/ !-)
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.
So the problem is not that you "can't" swap 2 elements, but that there seems to be some logical bug(s) in your code.
# Puzzle.py # class for a sliding block puzzle
(snip)
import random import copy
class Puzzle:
def __init__(self, dim): self.dim = dim self.elements = [[0 for column in range(dim)] for row in range(dim) ]
So at this stage you've got 3 rows of 3 colums: [ ['row 0 - col 0', 'row 0 - col 1', 'row 0 - col 2'], ['row 1 - col 0', 'row 1 - col 1', 'row 1 - col 2'], ['row 2 - col 0', 'row 2 - col 1', 'row 2 - col 2'] ]
Is that right ?
def __str__(self):
s = ""
i = 0
j = 0
while i <= self.dim-1:
ok, looping on rows
while j <= self.dim-1:
and now looping on columns in current row...
s = s + str(self.elements[j][i])
oops ! Looks like you're addressing row[j] column[i] instead of row[i] column[j] !-)
j=j+1
s = s + "\t"
i=i+1
j = 0
s = s + "\n"
return s
(snip the rest of the code)
Ok, let's try with a slightly more pythonic (and thus more readable) version of this code (I used another method name so we can compare both versions):
def to_string(self):
s = []
for row in self.elements:
for col in row:
s.append('%d\t' % col)
s.append('\n')
return ''.join(s)For testing purpose, let's modify the __init__ a bit (this will break the code but what, it's just to check something, we can get back to original code later):
def __init__(self, dim):
self.dim = dim
self.range = range(self.dim)
#self.elements = [[0 for column in self.range] for row in self.range]
self.elements = [[int('%d%d' % (row, column)) for column in self.range] for row in self.range]
# check we have a correct layout, remove me when fixed:
print "%s" % self.elements
and now let's try: >>> p = Puzzle(3) [[0, 1, 2], [10, 11, 12], [20, 21, 22]]
so far, so good, we have 3 rows of 3 columns each. let's continue: >>> print p.to_string() 0 1 2 10 11 12 20 21 22
Ok, so our new to_string() method is ok. Now the real test: >>> print p 0 10 20 1 11 21 2 12 22
Remember ?
"""
oops ! Looks like you're addressing row[j] column[i] instead of row[i] column[j]
"""
Looks like we found one bug...
Let's continue and rewrite some more code:
def compare(self, other):
if (self.dim != other.dim):
return False for self_row, other_row in zip(self.elements, other.elements):
for self_col, other_col in zip(self_row, other_row):
if self_col != other_col:
return Falsereturn True
Ok, that one was easy. Let's try with another one
def getEmptySlot(self):
for row in self.elements:
for cell in row:
if cell == -1:
return ???Mmmm... won't work. Seems we need indices here, let's try again:
def getEmptySlot(self):
for row in self.range:
for col in self.range:
if self.elements[row][col] == -1:
return (row, col)Ok, not so clean but still readable (notice how using explicit names like 'row' and 'col' helps understanding the code...).
Now let's do the swap:
def swapElements(self, from_cell, to_cell):
from_row, from_col = from_cell
to_row, to_col = to_cell
elts = self.elements
elts[to_row][to_col], elts[from_row][from_col] = elements[from_row][from_col], elts[to_row][to_col]
Mmmm... this begins to smell. I don't like having to split the coords like this. I'd prefer something like:
def swapElements(self, from_cell, to_cell): self.elements[from_cell], self.elements[to_cell] \ = self.elements[to_cell], self.elements[from_cell]
This could be possible if we used another data structure. Something like a dict of coords:value pairs. We could build it like this:
def __init__(self, dim):
self.dim = dim
self.range = range(self.dim)
self.elements = {}
for row in self.range:
for col in self.range:
self.elements[(row,col)] = 0and then the search for the empty slot:
def getEmptySlot(self):
for coords, value in self.elements.items():
if value == -1:
return coords
assert(False) # shouldn't be here anyway !Hey, that looks nicer, isn't it ? But what with the __str__() method ?
We can't use the dict.items() method since dicts are not ordered. But we can recompute the keys... What about :
def __str__(self):
s = []
for row in self.range:
for col in self.range:
s.append("%d\t" % self.elements[(row, col)])
s.append('\n')
return ''.join(s)Was not so difficult, finally. Now the compare() has to be rewritten too:
def compare(self, other):
if (self.dim != other.dim):
return 0 for row in self.range:
for col in self.range:
if self.elements[(row,col)] != other.elements[(row,col)]:
return False
# no difference
return TrueErr... Wait a minute... What are we doing here ? Comparing 2 dicts ? Wait, wait, let's check something...
>>> '__eq__' in dir(dict) True
Haha ! Our good'ole dict already has an 'equality' special method... Now is this a 'value' or 'identity' equality ?
>>> d1 = {1:1, 2:2}
>>> d2 = {2:2, 1:1}
>>> d1 == d2
TrueBingo ! Play it again, sam :
def compare(self, other): return self.elements == other.elements
Hehehe. Less code, better code, as grand'ma used to say !-)
Now the fine part : let's make it move. What was it like ?
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)This won't work since our swapElements() method now expects 2 tuples. Let's look closer. The first pair is always the same, it's the actually the empty slot. Quite sensible. We just have to create the second tuple from the first. And BTW, I don't like the if/elif neither. What about using a dict again ? :
def performMove(self, direction):
slot = self.getEmptySlot()
to_slot = {'up' : lambda (row, col): (row-1, col),
'down' : lambda (row, col): (row+1, col),
'left' : lambda (row, col): (row, col-1),
'right': lambda (row, col): (row, col+1)}
self.swapElements(slot, to_slot[direction](slot))Better, but not quite ok: it's silly to recreate the to_slot dict each time. Let's put it in the __init__ :
def __init__(self, dim):
self.dim = dim
self.range = range(self.dim)
self.elements = {} for row in self.range:
for col in self.range:
self.elements[(row,col)] = 0 self.to_slot = {'up' : lambda (row, col): (row-1, col),
'down' : lambda (row, col): (row+1, col),
'left' : lambda (row, col): (row, col-1),
'right': lambda (row, col): (row, col+1)}
and now our performMove() method become:
def performMove(self, direction): slot = self.getEmptySlot() self.swapElements(slot, self.to_slot[direction](slot))
Begins to look better, isn't it ? Ok, your turn to play !-) Just two more things :
1/ getPossibleMoves(self): emptySlot = self.getEmptySlot() y = emptySlot[1] x = emptySlot[0] (...)
could benefit from being rewritten as:
getPossibleMoves(self): row, col = self.getEmptySlot() (...)
(Yes, Python will automagically 'unpack' the tuple !-)
2/
def getChildren(self):
moves = self.getPossibleMoves()
self.children = []
for eachMove in moves:
newchild = copy.copy(self.performMove(eachMove))performMove() doesn't explicitly return anything, so it implicitly returns None. This may not give you what you want !-)
If the idea is to 'capture' the state of the puzzle object, you may want to have performMove() returning self. *But* remember that the state of the puzzle object is affected by performMove(), so this may not behave as expected either, since after each move, the possible moves change.
So the solution would be to 'clone' self *before* each performMove(), call the performMove() on each clone and store the clone.
(BTW, the name of the method may be somewhat misleading, and I'm not sure this method really belongs to the Puzzle class. )
and finally (pun intend !-) :
try:
self.children.append(newchild)
except:
print "Exception: " + str(len(self.children))This is the only place where you handle exceptions. But there is no particular reason to expect an exception here. So your try/except block is useless. Worse, it's badly coded, since you don't specify which exception you want to catch. This may put you into troubles (probably not here, but... I recently had hard time to debug some code that had many 'catch-all' except clauses.)
Well... You seem to like puzzles, so I leave it up to you to finish that one.
*warning* : this 100% untested code. You should write some unit tests to make sure every method woks as expected.
HTH Bruno -- http://mail.python.org/mailman/listinfo/python-list
