Lecture "Backtracking algorithms", exercise 2 about 2020-2021 HOT 5 OPEN

from anytree import Node
from collections import deque

#test
def test(paths, entrance, exit, last_move, expected):
    result = solve_labyrinth(paths, entrance, exit, last_move)
    return result.name["back"] == expected


bad_moves = set()

def solve_labyrinth(paths, entrance, exit, last_move):
    result = None
    if last_move not in bad_moves:
        if entrance == exit:
            result = last_move
        else:
            last_move.children = possible_paths(entrance, paths)
            if len(last_move.children) == 0:
                if [last_move.siblings] != []:
                    bad_moves.add(last_move)
                    undo_move(last_move, paths)
            else:
                move_stack = deque(last_move.children)
                while result == None and len(move_stack) > 0:
                    current_move = move_stack.pop()
                    new_pos = make_move(current_move, paths)[0]
                    new_path = make_move(current_move, paths)[1]
                    result = solve_labyrinth(new_path, new_pos, exit, current_move)
                if result == None:
                    bad_moves.add(last_move)
                    undo_move(last_move, paths)
    else:
        undo_move(last_move, paths)
    return result

#create labyrinth
def create_labyrinth():
    begin = (2,3) #begin mayn not be in labyrinth, but end has to be!
    end = (5, 2)
    all_path = {(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)}
    return all_path, begin, end

def make_move(node, pth):
    move= node.name
    new_pos = move.get("move")
    old_pos = move.get("back")
    if old_pos in pth:
        pth.remove(old_pos)
    return new_pos, pth #returns tuple!!!!!!!!!

def undo_move(node, pth):
    move = node.name
    old_pos = move.get("back")
    pth.add(old_pos)

#check possible paths
def possible_paths(entr, pth):
    result = list()
    x = entr[0]
    y = entr[1]
    if (x+1, y) in pth:
        result.append(Node({"move": (x+1, y), "back": (x,y)}))
    if (x-1, y) in pth:
        result.append(Node({"move": (x-1, y), "back": (x,y)}))
    if (x, y+1) in pth:
        result.append(Node({"move": (x, y+1), "back": (x,y)}))
    if (x, y-1) in pth:
        result.append(Node({"move": (x, y-1), "back": (x,y)}))
    return result

path, entrance, exit = create_labyrinth()

print(test(path, entrance, exit, Node("start"), (3,5))) # True

from anytree import Node
from collections import deque

paths = [
            (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)
]


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

def solve_labyrinth(paths, entrance, exit, previous_position):
    result = None
    entrance.children = valid_moves(paths, entrance, previous_position)  # generate children
    possible_moves = deque(entrance.children)
    if len(entrance.children) > 0:
        if entrance.name != exit:  # keep moving
            while result == None and len(possible_moves) > 0:
                current_move = possible_moves.pop()
                result = solve_labyrinth(paths, current_move, exit, entrance)   # recursion
        else:                                                                             # win, provided that you are in the exit box
            result = previous_position.name
        return result
    elif len(entrance.children) <= 0 and entrance.name != exit:  # leaf-node lose
        return result                                         # backtracking
    elif len(entrance.children) <= 0 and entrance.name == exit:   # leaf-node win
        result = previous_position.name
        return result


def valid_moves(paths, current_position, previous_position):
    result = list()
    x = current_position.name[0]
    y = current_position.name[1]
    if (x + 1, y) in paths and (x + 1, y) != previous_position.name:
        result.append(Node((x + 1, y)))
    if (x - 1, y) in paths and (x - 1, y) != previous_position.name:
        result.append(Node((x - 1, y)))
    if (x, y + 1) in paths and (x, y + 1) != previous_position.name:
        result.append(Node((x, y + 1)))
    if (x, y - 1) in paths and (x, y - 1) != previous_position.name:
        result.append(Node((x, y - 1)))
    return result


none_node = Node(None)   # previous position of the start position
print(test_solve_labyrinth(paths, Node((2, 3)), (4, 4), none_node,(4,5))) # returns True
print(test_solve_labyrinth(paths, Node((0, 1)), (5, 3), none_node,(5,2))) # returns True
print(test_solve_labyrinth(paths, Node((2, 1)), (4, 2), none_node,(5,2))) # returns True
print(test_solve_labyrinth(paths, Node((2, 1)), (5, 5), none_node,None)) # returns True

from anytree import Node
from collections import deque


# Test case for the algorithm
def test_solve_labirynth(paths,entrance,exit,last_move,expected):
    result = solve_labirynth(paths,entrance,exit,last_move)
    if (expected==result==None):
        return True
    elif result!=None:
        return (expected == result.name["to"])
    else:
        return False


def create_labirynth():

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

    return paths


def valid_moves(paths,cell):
    result = list()
    pos_x=cell[0]
    pos_y=cell[1]

    if (pos_x-1, pos_y) in paths:
        result.append(Node({"from": (pos_x, pos_y), "to": (pos_x-1, pos_y)}))
    if (pos_x+1, pos_y) in paths:
        result.append(Node({"from": (pos_x, pos_y), "to": (pos_x+1, pos_y)}))
    if (pos_x, pos_y-1) in paths:
        result.append(Node({"from": (pos_x, pos_y), "to": (pos_x, pos_y-1)}))
    if (pos_x, pos_y+1) in paths:
        result.append(Node({"from": (pos_x, pos_y), "to": (pos_x, pos_y+1)}))

    return result


def apply_move(node, paths):
    move = node.name
    prev_pos = move.get("from")

    paths.remove(prev_pos)


def undo_move(node, paths):
    move = node.name
    curr_pos = move.get("to")
    prev_pos = move.get("from")

    paths.remove(curr_pos)
    paths.add(prev_pos)


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

    if (exit not in paths): return None

    if (entrance==exit):  # leaf-win base case
        result = last_move
    else:
        last_move.children = valid_moves(paths,entrance)

        if len(last_move.children) == 0:  # leaf-lose base case
            undo_move(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()
                apply_move(current_move, paths)
                result = solve_labirynth(paths, current_move.name.get("to"),exit, current_move)

            if (result is None) and (last_move!=last_move.root):  # If the last_move is back to the root, it means the exit has not been found after trying all the paths
                undo_move(last_move, paths)  # backtracking

    return result


# TEST 1: solvable labirynth
paths=create_labirynth()
entrance=(5,3)
exit=(4,4)
print(test_solve_labirynth(paths,entrance,exit,Node('Start'),exit))


# TEST 2: same labirynth but exit out of paths
entrance=(5,3)
exit=(5,5)
print(test_solve_labirynth(paths,entrance,exit,Node('Start'),None))


# TEST 3: existent but unreachable exit
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)
    ])
entrance=(5,3)
exit=(4,4)
print(test_solve_labirynth(paths,entrance,exit,Node('Start'),None))

from anytree import Node
from collections import deque
from time import sleep


# Test case for the algorithm
def test_solve_labyrinth(paths, entrance, exit, last_move, expected):
    result = solve_labyrinth(paths, entrance, exit, last_move)
    if expected == result:
        return True
    else:
        return False


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

    if last_move.name["new_position"] == exit:  # leaf-win base case
        result = last_move.name["old_position"]

    else:
        if entrance == last_move:  # only first case
            last_move.children = valid_moves(entrance, paths)
            move = last_move.name
            street.append(move["new_position"])
            paths.remove(move["new_position"])
        else:
            last_move.children = valid_moves(last_move, paths)

        possible_moves = deque(last_move.children)

        while result is None and len(possible_moves) > 0:
            current_position = possible_moves.pop()
            apply_move(current_position, paths)
            result = solve_labyrinth(paths, entrance, exit, current_position)

    return result


def create_board():
    entrance = Node({"new_position": (int(input("starting_x: ")), int(input("starting_y: "))) , "old_position": (None, None)})

    paths = {(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)}

    exit = (int(input("finishing_x: ")), int(input("finishing_y: ")))
    return paths, entrance, exit


def valid_moves(last_move, paths):
    result = list()
    move = last_move.name
    x, y = move["new_position"]
    if (x - 1, y) in paths:
        result.append(Node({"new_position": (x - 1, y), "old_position": (x, y)}))
    if (x + 1, y) in paths:
        result.append(Node({"new_position": (x + 1, y), "old_position": (x, y)}))
    if (x, y - 1) in paths:
        result.append(Node({"new_position": (x, y - 1), "old_position": (x, y)}))
    if (x, y + 1) in paths:
        result.append(Node({"new_position": (x, y + 1), "old_position": (x, y)}))
    return result


def apply_move(current_positon, paths):
    move = current_positon.name
    new_pos = move.get("new_position")

    paths.remove(new_pos)


# pegs, holes = create_6x6_square_board()
paths, entrance, exit = create_board()
print(test_solve_labyrinth(paths, entrance, exit, entrance, (5, 0)))

from anytree import Node
from collections import deque


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


def valid_moves(entrance, paths):
    result = []
    x = entrance[0]
    y = entrance[1]
    if (x,y) in paths:
        if (x + 1, y) in paths:
            result.append(Node({"move from": (x, y), "to": (x + 1, y)}))
        if (x - 1, y) in paths:
            result.append(Node({"move from": (x, y), "to": (x - 1, y)}))
        if (x, y + 1) in paths:
            result.append(Node({"move from": (x, y), "to": (x, y + 1)}))
        if (x, y - 1) in paths:
            result.append(Node({"move from": (x, y), "to": (x, y - 1)}))
    return result


def apply_move(node, paths):
    move = node.name
    old_pos = move.get("move from")
    entrance = move.get("to")
    if old_pos in paths:
        paths.remove(old_pos)
    return entrance, paths, old_pos


def undo_move(node, paths):
    move = node.name
    old_pos = move.get("move from")
    paths.add(old_pos)


def solve_labyrinth(paths, entrance, exit, last_move):
    result = None
    initial_paths = set()
    initial_paths.update(paths)
    if entrance not in paths:
        return "No access to labyrinth"
    if exit not in paths:
        return result
    if entrance == exit:
        result = last_move.name
    else:
        last_move.children = valid_moves(entrance, paths)
        if len(last_move.children) == 0:
            undo_move(last_move, paths)
        else:
            possible_moves = deque(last_move.children)
            while result is None and len(possible_moves) > 0:
                cur_move = possible_moves.pop()
                new_entr = apply_move(cur_move, paths)[0]
                paths_updated = apply_move(cur_move, paths)[1]
                result = solve_labyrinth(paths_updated, new_entr, exit, cur_move)
            if result is None:
                undo_move(last_move, paths)
    paths.update(initial_paths)
    return result


cells = {(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)}


print(test_solve_labyrinth(cells, (1,0), (3,3), Node("Start"), {'move from': (2, 3), 'to': (3, 3)}))   # True
print(test_solve_labyrinth(cells, (4,4), (5,3), Node("Start"), {'move from': (5, 2), 'to': (5, 3)}))   # True
print(test_solve_labyrinth(cells, (0,0), (4,4), Node("Start"), "No access to labyrinth"))   # True 
print(test_solve_labyrinth(cells, (2,1), (3,6), Node("Start"), None))   # True