Theres a cute little Android game called Traffic Jam
I wrote 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
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=[list(x) for x in file(sys.argv[1]).read().split('\n')[0:-1]]
solve(grid,[],0)
The WHERE table is in the file:
abccdd
abeef
azzhfi
jjjhfi
kll
kmm
But finding a solution requires more than 8000 moves, and it is not possible to find a simple solution for 30 steps. What is wrong with the algorithm?