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 def 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 done. 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.

[frammenti]

Edit: added no_exit configuration

from anytree import Node
from collections import deque

def test_solve_labyrinth(paths, entrance, exit, last_move):
    result = solve_labyrinth(paths, entrance, exit, last_move)
    return result is not None and exit == result.name and (
        # Check whether all steps are within the boundaries of the labyrinth
        all(ancestor.name in paths for ancestor in result.ancestors if ancestor is not last_move.root))


def solve_labyrinth(paths, entrance, exit, last_move):
    result = None

    if last_move.name == exit:
        result = last_move
    elif last_move.name not in last_move.root.name: # avoid loop paths
        last_move.children = crossroads(paths, entrance, last_move)
        possible_moves = deque(last_move.children)

        while result is None and len(possible_moves) > 0: # implicit leaf-lose
            current_move = possible_moves.popleft()
            # In each recursive step, the entrance is shifted forward to avoid unintentional backtracking
            result = solve_labyrinth(paths, last_move.name, exit, current_move)

    return result


def crossroads(paths, entrance, last_move):
    result = []
    x, y = last_move.name

    # First execution
    if last_move.parent is None:
        last_move.parent = Node(set())

    # Last_move coordinates added to visited set    
    last_move.root.name.add((x, y))

    # Progression of search is North-East-South-West
    for direction in [(x, y - 1), (x + 1, y), (x, y + 1), (x - 1, y)]:
        if direction in paths and direction != entrance:
            result.append(Node(direction))
            
    return result

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), 
    ])

loop = 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),
        (5,4),  
    ])

no_exit = 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,3),
    ])

# Root node name is initialized with entrance coordinates
print(test_solve_labyrinth(paths, (2, 1), (3, 3), Node((2, 1)))) # 12 steps
print(test_solve_labyrinth(loop, (2, 1), (3, 3), Node((2, 1)))) # 26 steps
print(test_solve_labyrinth(paths, (2, 1), (2, 1), Node((2, 1)))) # 1 step
print(test_solve_labyrinth(loop, (5, 2), (4, 2), Node((5, 2)))) # 27 steps
print(test_solve_labyrinth(no_exit, (2, 1), (4, 2), Node((2, 1)))) # No exit returns False, 21 steps

[Liber-R]

[valetedd]

from anytree import Node
from collections import deque


### Ex. 2 ###

def test_labyrinth(paths, entrance, exit, last_move, expected):
    result = solve_labyrinth(paths, entrance, exit, last_move)
    if expected == result.name["next"]:
        return True
    else:
        return False 
   
def valid_directions(paths, entrance):
    result = list()
    x = entrance[0]
    y = entrance[1]
    if (x-1, y) in paths:
        result.append(Node({"previous": entrance, "next" : (x - 1, y)}))
    if (x+1, y) in paths:
        result.append(Node({"previous": entrance, "next" : (x + 1, y)}))
    if (x, y-1) in paths:
        result.append(Node({"previous": entrance, "next" : (x, y - 1)}))
    if (x, y+1) in paths:
        result.append(Node({"previous": entrance, "next" : (x, y + 1)}))
    return result

def step(node, paths):
    coords = node.name
    prev_pos = coords.get("previous")
    new_pos = coords.get("next")
    
    paths.discard(prev_pos)
    paths.add(new_pos)
    

def undo_movement(node, paths):
    coords = node.name
    prev_pos = coords.get("next")
    new_pos = coords.get("previous")
    
    paths.add(prev_pos)
    paths.discard(new_pos)
    
def solve_labyrinth(paths, entrance, exit, last_move):
    result = None
    if entrance == exit:
        return last_move
    else:
        last_move.children = valid_directions(paths, entrance)
        if len(last_move.children) == 0: # dead-end base case
            undo_movement(last_move, paths) # backtracking
        else: # recursive step
            possible_moves = deque(last_move.children)
            while result is None and len(possible_moves) > 0:
                current_move = possible_moves.pop()
                step(current_move, paths)
                curr_position = current_move.name.get("next")
                result = solve_labyrinth(paths, curr_position, exit, current_move)
            if result is None:
                undo_movement(last_move, paths) # backtracking
    return result

def create_board():       
    paths = set([
            (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)
        ])
    entrance = (1, 0)
    exit = (5, 3)

    return paths, entrance, exit

paths, entrance, exit = create_board()

##Test cases

#print(test_labyrinth(paths, entrance, exit, Node("start"), (5, 3)))
#print(test_labyrinth(paths, (4, 4), (4,2), Node("start"), (4,2)))
#print(test_labyrinth(paths, (3, 3), (4,4), Node("start"), (4,4)))
#print(test_labyrinth(paths, (0, 5), (1,0), Node("start"), (1,0)))