Lecture "Backtracking algorithms", exercise 2

[essepuntato]

We define a labyrinth as a set of tuples representing the various cells of the paths within the labyrinth. The tuples are organised in an x/y grid, similar to the way used in Listing 1 for the peg solitaire, such as the one proposed as follows:

      (1,0)       (3,0) (4,0) (5,0)
(0,1) (1,1) (2,1) (3,1)       (5,1)
(0,2)       (2,2)       (4,2) (5,2)
(0,3)       (2,3) (3,3)       (5,3)
(0,4)                   (4,4)      
(0,5) (1,5) (2,5) (3,5) (4,5)      

Write the function solve_labyrinth(paths, entrance, exit, last_move), which takes as input the paths of the labyrinth (such as the ones mentioned above), two tuples representing the entrance and the exit of the labyrinth, and the last move did. The function returns the last move done to reach the exit if the labyrinth has an escape; otherwise, it returns None. Accompany the implementation of the function with the appropriate test cases.

[NoonShin]

Note: While trying to solve the problem, I didn't notice that the question just asks for the very last move made to escape, so I made the implementation with a stack for the last move, which shows the complete path. However, it isn't much different from the original question.

from collections import deque

def create_table():
  paths = set([(0, 1), (0, 2), (0, 3), (0, 4), (0,5),
  (1, 0), (1, 1), (1, 5),
  (2, 1), (2, 2), (2, 3), (2, 5),
  (3, 0), (3, 1), (3, 3), (3, 5),
  (4, 0), (4, 2), (4, 4), (4, 5),
  (5, 0), (5, 1), (5, 2), (5, 3)])
  return paths

def find_possible_locs(entrance, paths, last_move):
  x = entrance[0]
  y = entrance[1]
  locs = set()
  if last_move == 'start':
    locs = set([(x, y+1), (x, y-1), (x+1, y), (x-1, y)])
  elif last_move == 'left':
    locs =  set([(x, y+1), (x, y-1), (x-1, y)])
  elif last_move == 'right':
    locs = set([(x, y+1), (x, y-1), (x+1, y)])
  elif last_move == 'up':
    locs = set([(x, y-1), (x+1, y), (x-1, y)])
  elif last_move == 'down':
    locs = set([(x, y+1), (x+1, y), (x-1, y)])    
  return [x for x in locs if x in paths]

def make_move(entrance, loc):
  if entrance[0] == loc[0]:
    if entrance[1] == loc[1]-1:
      move = 'down'
    else:
      move = 'up'
  elif entrance[0] == loc[0]-1:
    move = 'right'
  else:
    move = 'left'
  return loc, move

def undo_move(entrance, last_move):
  move_made = last_move.pop()
  x = entrance[0]
  y = entrance[1]
  if move_made == 'left':
    return (x+1, y)
  elif move_made == 'right':
    return (x-1, y)
  elif move_made == 'up':
    return (x, y+1)
  else:
    return (x, y-1)

def solve_labyrinth(paths, entrance, exit, last_move):
  if entrance == exit:
    return last_move

  next_locs = find_possible_locs(entrance, paths, last_move[-1])
  if len(next_locs) == 0:
    return None

  for loc in next_locs:
    entrance, curr_move = make_move(entrance, loc)
    last_move.append(curr_move)
    result = solve_labyrinth(paths, entrance, exit, last_move)
    if result is not None:
      return result
    else:
      entrance = undo_move(entrance, last_move)

  return None

def test_solve_labyrinth(paths, entrance, exit, last_move, expected):
  result = solve_labyrinth(paths, entrance, exit, last_move)
  return result == last_move

paths = create_table()  
moves = deque()
moves.append('start')
print(test_solve_labyrinth(paths, (0, 1), (4, 2), moves, deque(['start', 'right', 'right', 'right', 'up', 'right', 'right', 'down', 'down', 'left'])))

moves = deque()
moves.append('start')
print(test_solve_labyrinth(paths, (5, 3), (4, 4), moves, deque(['start', 'up', 'up', 'up', 'left', 'left', 'down', 'left', 'left', 'left', 'down', 'down', 'down', 'down', 'right', 'right', 'right', 'right', 'up'])))

moves = deque()
moves.append('start')
print(test_solve_labyrinth(paths, (4, 4), (3, 3), moves, deque(['start', 'down', 'left', 'left', 'left', 'left', 'up', 'up', 'up', 'up', 'right', 'right', 'down', 'down', 'right'])))