I have written a depth first search that searches the path in a labyrinth, based on this question:
# for convenience
matrix = [
["0", "0", "0", "0", "1", "0", "0", "0"],
["0", "1", "1", "0", "1", "0", "1", "0"],
["0", "1", "0", "0", "1", "0", "1", "0"],
["0", "0", "0", "1", "0", "0", "1", "0"],
["0", "1", "0", "1", "0", "1", "1", "0"],
["0", "0", "1", "1", "0", "1", "0", "0"],
["1", "0", "0", "0", "0", "1", "1", "0"],
["0", "0", "1", "1", "1", "1", "0", "0"]
]
num_rows = len(matrix)
num_cols = len(matrix[0])
goal_state = (num_rows - 1, num_cols - 1)
print(goal_state)
def dfs(current_path):
# anchor
row, col = current_path[-1]
if (row, col) == goal_state:
print("Anchored!")
return True
# try all directions one after the other
for direction in [(row, col + 1), (row, col - 1), (row + 1, col), (row - 1, col)]:
new_row, new_col = direction
if (0 <= new_row < num_rows and 0 <= new_col < num_cols and # stay in matrix borders
matrix[new_row][new_col] == "0" and # don't run in walls
(new_row, new_col) not in current_path): # don't run in circles
current_path.append((new_row, new_col)) # try new direction
print(result == current_path)
if dfs(current_path): # recursive call
return True
else:
current_path = current_path[:-1] # backtrack
# the result is a list of coordinates which should be stepped through in order to reach the goal
result = [(0, 0)]
if dfs(result):
print("Success!")
print(result)
else:
print("Failure!")
It works as I would expect, except that the last two coordinates do not get added to the list called result. Which is the reason why I included the line print(result == current_path), which should in my expectation always be true - it is the same object, which gets passed as a reference. How could it ever not be equal? The code should be executable as is, but just in case, this is the output I am getting:
True
True
...
True
False
False
Anchored!
Success!
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (6, 1), (6, 2), (6, 3), (6, 4), (5, 4), (4, 4), (3, 4), (3, 5), (2, 5), (1, 5), (0, 5), (0, 6), (0, 7), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (5, 6)]
As should be clear from the output, the function can only have anchored if the last state was (7, 7), which is, together with (6, 7), not present in the result variable. I am stupefied as to why.
edit: The coordinate (5, 6), which is present in the result list, should not be there. It is the last position from which the algorithm backtracks, the dead-end just before reaching the goal state. I have, again, no clue why it was not properly removed from both lists during the backtracking step.
