# Python problem

This topic is 3989 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I just learned python and wanted to practice by implementing the A* algorithm and using it to solve the 8-puzzle. So I made a node class that looks like this:
class Node:
def  __init__(self, data):
self.data = data
parent = 0
f,g,h=0,0,0


where data is a 1D representation of the 2D board (so that data[x+3*y] is the (x,y) square) where the emty square has the value 0. I also have a function called GenerateNeighbors(node) which takes a node as input and returns a list of neighboring nodes. Now, just to check that everything was working I made a function that shuffles a board using the GenerateNeighbors function:
def Shuffle(node, depth):
if depth==0:
return node.data, depth
print node.data , depth
Shuffle(GenerateNeighbors(node)[0],depth-1)


I know that it's not random at all but I did it just to see if it would work. So then I did:
start = [1,2,3,4,5,6,7,8,0]
print Shuffle(Node(start),10)


and got: [1, 2, 3, 4, 5, 6, 7, 8, 0] 10 [1, 2, 3, 4, 5, 0, 7, 8, 6] 9 [1, 2, 0, 4, 5, 3, 7, 8, 6] 8 [1, 2, 3, 4, 5, 0, 7, 8, 6] 7 [1, 2, 0, 4, 5, 3, 7, 8, 6] 6 [1, 2, 3, 4, 5, 0, 7, 8, 6] 5 [1, 2, 0, 4, 5, 3, 7, 8, 6] 4 [1, 2, 3, 4, 5, 0, 7, 8, 6] 3 [1, 2, 0, 4, 5, 3, 7, 8, 6] 2 [1, 2, 3, 4, 5, 0, 7, 8, 6] 1 None So I know that the functions are working but why did I get None at the end? Thanks.

##### Share on other sites

print Shuffle(Node(start),10)

This prints only the return value of the first or outermost call to Shuffle. Shuffle only returns (node.data, depth) if depth == 0. But depth == 10, and since there is no return statement in the remaining part of the function, it returns None. A function that doesn't specify a return value returns None. It's similar to void in C++.

The rest of the printed lines come from the print statement within the Shuffle function. Since this is being called recursively, the first call returns last, hence the None is printed last rather than first.

##### Share on other sites
So how do I make it return the innermost (shuffled) value?
Thanks.

##### Share on other sites
You would have to return it all the way back down the call stack.
def Shuffle(node, depth):    if depth==0:        return node.data, depth    return Shuffle(GenerateNeighbors(node)[0],depth-1)

Returning depth is redundant though. It will always == 0 at the point it is returned.
Recursion seems unnecessary in this case. Consider an iterative approach:
def Shuffle(node, depth):    for i in xrange(depth):        node = GenerateNeighbors(node)[0]    return node.data

As far as I can tell, this is equivelent to the recursive version.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633736
• Total Posts
3013601
×