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)
previous_states = previous_states.copy().add(state)
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
