# shortest path recursive algorithm [closed]

This is the first time I come to this site, even though I tried to post in Stack Overflow but was told that this would be a better place to ask. So I hope this is the right place for my question.

As a programing exercise, I am trying to solve a puzzle game in Python (unblock me, a.k.a. rush hour). For this I'm using a recursive algorithm, which I thought to be a depth-first-search implementation. My problem is that I get a runtime error for reaching the maximum recursion limit, and I don't think I should be getting it.

I have seen a few posts about both the game and the algorithm. While I see this is a graph theory problem and I can see the resemblance on my code, I didn't really intended to write it as such but rather kept it in a game-style approach. So thank you for your help.

``````# Keep track of paths that I have found for given states.
best_paths = dict()

def find_path(state, previous_states = set()):

# The output is a tuple of the length of the path and the path.
if state in previous_states:
return (infty,None)

if state in target_states:
best_paths[state] = (0,[])

if state in best_paths:
return best_paths[state]

possible_moves = set((piece,spaces) that can be moved)
(shortest_moves,shortest_path) = (infty,None)
for (piece,spaces) in possible_moves:
move_piece(piece,spaces)
try_state = the resulting state after moving the piece
(try_moves,try_path) = find_path(try_state,previous_states)

if try_moves < shortest_moves:
shortest_moves = try_moves + 1
shortest_path  = try_path + [(piece,spaces)]

# Undo the move for the next call
move_piece(piece,-spaces)

if shortest_moves < infty:
best_paths[state] = shortest_path

return (best_moves, shortest_path)
``````

So here's my question. Is this algorithm promising? And by this I mean that, is there a structural mistake in calling the recursion in the for loop that is causing the long recursions?, or do you suggest (I was hoping not) to just try a direct implementation of a known algorith? Thank you in advance. Diego

-
To be ontopic here, you need to post the actual code. You've got several pieces where appear to be pseudocode. Please edit the post to include the actual code. (It's okay if they just call functions you don't provide if you won't want review on them) –  Winston Ewert Aug 17 '12 at 18:49
I second what Winston said, but if you can make a small self-contained program so that we can run it, then that would be even better. –  Gareth Rees Sep 16 '12 at 20:10

## closed as off topic by Winston EwertSep 18 '12 at 14:28

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

``````import sys