Python backtracking problem, maximum recursion depth reached

Question

Given an m*n parking lot and there are several cars in the parking lot, each car is below:

car=[i,j,w,h,direction]
#i,j are top left position
#w,h are width and height
#direction can be -1/1 for horizontal/vertical
#horizontal cars can only move left or right
#vertical cars can only move up and down
#move one step at a time

and there's an exit at the edge or gird

exit=[i,j]
#i=0 or m-1
#j=0 or n-1

so the problem is to find if a specific car can get out of the parking lot. My idea is to use recursion to solve it, as following

grid=[[0]*n for _ in range(m)]

#use dict to store cars info
cars={'car0':[i,j,w,h,dir],'car1':[...],'target_car':[...]}

#and a function to determine if it's possible to move a car in a certain direction
#which will return True if I can move cars[car_name] one step to move_direction
#false otherwise
is_valid_move(car_name,move_direction)

#and I have a function to actually move the car if previous function return True
move_car(car_name,direction) 

and now here is the function to solve the problem
def solver(grid,cars):
    #base cases
    if (some basic conditions):
        return True or False based on condition
    
    #otherwise, we try to move one car at a time
    for car_name in cars.keys():
        if is_valid_move(car_name,direction):
            move_car(car_name,direction)
            if solver(gird,cars):
                return True
            #just recover the parking gird
            move_car(car_name,inverse_direction)
        if is_valid_move(car_name,inverse_direction):
            move_car(car_name,inverse_direction)
            if solver(gird,cars):
                return True
            #just recover the parking gird
            move_car(car_name,direction)
    return False

As you can see it cannot work properly because it will move one car back and forth until the maximum recursion depth reached. I am not sure how to deal with it, maybe there's a way to enumerate all unique grids and examine them one by one.

In your question, a car can't change direction, right? We need to check if a given car is in the same row (if the car is horizontal) or in the same column (if the car is vertical). If not, output false. If yes, return "there is no car between the car and exit in the corresponding row/column" — Kate Melnykova
– Kate Melnykova, Commented Oct 21, 2020 at 20:11
For your solution, add visited global variable where you store coordinate of visited cell (and, maybe, including vert/hor orientation) — Kate Melnykova
– Kate Melnykova, Commented Oct 21, 2020 at 20:12

Prune · Accepted Answer · 2020-10-21 20:19:27Z

2

To identify, this is a generalized version of the puzzle game marketed as "Rush Hour".

You need recognize this as a graph traversal problem. Every board position is a node of the graph; a single move represents an edge between two nodes.

You have to implement an algorithm to traverse this graph, searching for a path to a solution state. This is a well-known paradigm; you have some research to do. The critical part to include is to avoid visiting any node you have already seen. That is the simplest way to avoid any loops.

answered Oct 21, 2020 at 20:19

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python backtracking problem, maximum recursion depth reached

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related