How do I improve the algorithm for my Traffic Jam recursive solver?

Question

Theres a cute little game on Android called Traffic Jam

I've written a recursive solver:

import copy,sys
sys.setrecursionlimit(10000)


def lookup_car(car_string,ingrid):
  car=[]
  i=0
  for row in ingrid:
    j=0 
    for cell in row:
      if cell == car_string:
        car.append([i,j])
      j+=1
    i+=1
  return car

#True if up/down False if side to side
def isDirectionUp(car):
  init_row=car[0][0]
  for node in car:
    if node[0] != init_row:
      return True
  return False   

def space_up(car,grid):
  top_node=car[0]
  m_space_up = (top_node[0]-1,top_node[1])
  if top_node[0] == 0:
    return -1
  elif grid[m_space_up[0]][m_space_up[1]] != " ":
    return -1
  else:
    return m_space_up

def space_down(car,grid):
  bottom_node = car[-1]
  m_space_down = (bottom_node[0]+1,bottom_node[1])
  if bottom_node[0] == 5 :
    return -1
  elif grid[m_space_down[0]][m_space_down[1]] != " ":
    return -1
  else:
    return m_space_down

def space_left(car,grid):
  left_node = car[0]
  m_space_left = (left_node[0],left_node[1]-1)
  if left_node[1] == 0 :
    return -1
  elif grid[m_space_left[0]][m_space_left[1]] != " ":
    return -1
  else:
    return m_space_left

def space_right(car,grid):
  right_node = car[-1]
  m_space_right = (right_node[0],right_node[1]+1)
  if right_node[1] == 5 :
    return -1
  elif grid[m_space_right[0]][m_space_right[1]] != " ":
    return -1
  else:
    return m_space_right

def list_moves(car,grid):
  ret =[]
  if isDirectionUp(car):
    up = space_up(car,grid) 
    if up != -1:
      ret.append(("UP",up))
    down = space_down(car,grid)
    if down != -1:
      ret.append(("DOWN",down))
  else:
    left = space_left(car,grid)
    if left != -1:
      ret.append(("LEFT",left))
    right = space_right(car,grid)
    if right != -1:
      ret.append(("RIGHT",right))
  return ret

def move_car(car_string,move,ingrid):
  grid = copy.deepcopy(ingrid)
  car = lookup_car(car_string,grid)
  move_to = move[1]
  front = car[0]
  back = car[-1]
  if(move[0] == "UP" or move[0] == "LEFT"):
    grid[back[0]][back[1]] = " "
    grid[move_to[0]][move_to[1]] = car_string 
  elif(move[0] == "DOWN" or move[0] == "RIGHT"):
    grid[front[0]][front[1]] = " "
    grid[move_to[0]][move_to[1]] = car_string 
  return grid

def is_solution(grid):       
  car = lookup_car("z",grid)
  if(car[-1] == [2,5]):
    return True
  elif space_right(car,grid) == -1:
    return False
  else:
    solgrid = move_car("z",("RIGHT",space_right(car,grid)),grid)
    return is_solution(solgrid)

def print_grid(grid):
  for row in grid:
    print ''.join(row)

def solve(grid,solution,depth):
  global stop
  global state
  if grid in state:
    return
  else:
    state.append(grid)
  if stop:
    return
  if is_solution(grid):
    print_grid(grid)
    print len(solution)
  else:
    for each in "abcdefzhijklm":
      car = lookup_car(each,grid)
      moves = list_moves(car,grid)
      for move in moves:
        solution.append((each,move))
        moved_grid = move_car(each,move,grid)
        solve(moved_grid,solution,depth)

stop=False
state=[]
recdepth=0

#grid file using a-w  and x means free space, and ' ' means yellow car
grid=[list(x) for x in file(sys.argv[1]).read().split('\n')[0:-1]]
solve(grid,[],0)

WHERE grid is in a file:

abccdd
abeef 
azzhfi
jjjhfi
  kll
  kmm

But, it takes over 8000 moves to find a solution ,and fails to find a simple 30 move solution. What is wrong with the algorithm?

Answer 1

If the branching factor of your search space is r then the number of vertices in the search tree to depth n is (1-r^n)/(1-r). A problem with a minimal 30 step solution, even in the simple case where r = 2, will have a search tree with around 2^30 - 1 ~= 1,000,000,000 vertices. Now, your branching factor is likely to be bigger than 2, so a 30 step problem is a long way from trivial!

That said, I'd be inclined to (a) find a better representation of your problem (searching arrays of strings is slow) and (b) consider best-first search where you guide your search with a heuristic (e.g., distance of the yellow car from its destination or the number of cars blocking the path of the yellow car).

Hope this helps.

Answer 2

This is essentially a (relatively token) searching problem, with a huge search space. As others recommended, read up on Depth-first search, and then read up on Breadth-first search, and when you learn the difference, read up on A* Search, and coming up with a pessimistic scoring function.

Also, note that in this case, you already know what the end state should be, thus, another approach would be to search from both ends and meet in the middle. This should reduce your search space considerably.

If that's still not enough, you can combine the techniques!