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