Lecture "Backtracking algorithms", exercise 2
Opened this issue · 5 comments
essepuntato commented
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.
dbrembilla commented
This function won't find the fastest route but it returns the first it finds.
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
I tried putting begin = (2,3) and end = (5,2):
print(test(path, entrance, exit, Node("start"), (5,1))) # True
gabrielefiorenza commented
I have replaced your "last_move" with "previous_position". At the end the algorithm returns the position occupied before finding the exit.
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
diegochillo commented
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))
AlessandroBertozzi commented
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)))
AlessandraFa commented
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