Итак, я пытаюсь написать программу, которая решает лабиринты. Я провел много тестов с разными лабиринтами, и я понял, что моя программа не способна решить все виды лабиринтов, только несколько, поскольку есть определенные тупики, в которых моя программа застревает и не может вернуться назад.
Логика, лежащая в основе моего кода, в основном заключается в том, что он работает по всему лабиринту до тех пор, пока не найдет выход, и, если он обнаружит тупик во время этих процессов, он сможет вернуться и найти новый неизведанный путь.
Мой код работал хорошо, пока я не начал тестировать его с более сложными лабиринтами с различными хитрыми тупиками. Например:
maze = (
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,1,0,0,0,0,0,1],
[1,1,1,0,1,1,1,0,1,0,1,0,1,0,1],
[1,1,1,0,1,0,1,0,1,0,1,1,1,0,1],
[1,1,1,1,1,0,1,0,1,0,0,1,0,0,1],
[1,1,0,0,0,0,1,0,1,1,0,1,0,1,1],
[1,1,0,1,1,0,0,0,0,1,0,1,0,1,1],
[1,1,0,0,1,1,0,1,0,1,0,1,0,0,1],
[1,1,0,1,0,0,1,0,0,0,1,0,0,1,1],
[1,1,1,1,1,1,1,1,1,1,1,3,1,1,1]
)
Это пример лабиринта с тупиками, который может решить моя программа, после чего 1 - стена, 0 - свободный путь, 3 - конец, а начало - maze[1][1]
maze = (
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
[1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
[1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
[1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
[1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
[1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
[1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
[1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
)
Теперь лабиринт, который не может решить моя программа. Я предполагаю, что проблема с этим лабиринтом в том, что он имеет тупики в форме буквы "L" или что-то вроде зигзага, но, честно говоря, я не знаю, что происходит. Например, тупик в maze[5][5] (где застряла моя программа)
Прежде чем показывать код, я хочу рассказать о некоторых темах:
- Все строки, которые я печатаю, написаны на английском и на португальском языках, языки разделены "/", так что не беспокойтесь об этом.
- Чтобы исследовать лабиринт, программа использует рекурсивную стратегию и отмечает 2 пути, которые были исследованы.
- Программа работает с координатами x и y на основе массива. x + 1 идет вниз, x - 1 идет вверх, y + 1 идет вправо, а y - 1 идет влево.
- Если он застрянет в тупике, стратегия смотрит на то, что вокруг, чтобы определить, какой это тупик, и затем возвращается назад, пока не найдет новый путь, помеченный 0.
Это случаи тупиков, которые вы увидите в моем коде.
- Если возможно, я хочу дать несколько советов о том, как улучшить мой код или сделать его чистым.
Итак, поехали:
maze = (
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
[1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
[1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
[1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
[1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
[1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
[1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
[1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
)
def solve(x, y):
if maze[x][y] == 0 or maze[x][y] == 2:
# To walk around and explore the maze
print('Visiting/Visitando xy({},{})'.format(x, y))
maze[x][y] = 2
if x < (len(maze) - 1) and (maze[x + 1][y] == 0 or maze[x + 1][y] == 3):
solve(x + 1, y)
elif y < (len(maze) - 1) and (maze[x][y + 1] == 0 or maze[x][y + 1] == 3):
solve(x, y + 1)
elif x > 0 and (maze[x - 1][y] == 0 or maze[x][y + 1] == 3):
solve(x - 1, y)
elif y > 0 and (maze[x][y - 1] == 0 or maze[x][y + 1] == 3):
solve(x, y - 1)
else:
# If it gets stuck in a dead end
step_back = 1
dead_end = True
# each possible kind of dead ends and the strategy to go back
if (maze[x + 1][y] == 1 or maze[x + 1][y] == 2) and maze[x][y - 1] == 1 and \
maze[x][y + 1] == 1 and maze[x - 1][y] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x - step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
solve(x - step_back, y - 1)
elif maze[x - step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
solve(x - step_back, y + 1)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x - step_back, y)
elif (maze[x - 1][y] == 1 or maze[x - 1][y] == 2) and maze[x][y - 1] == 1 and \
maze[x][y + 1] == 1 and maze[x + 1][y] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x + step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
solve(x + step_back, y - 1)
elif maze[x + step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
solve(x + step_back, y + 1)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x + step_back, y)
elif (maze[x][y + 1] == 1 or maze[x][y + 1] == 2) and maze[x + 1][y] == 1 and \
maze[x - 1][y] == 1 and maze[x][y - 1] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
solve(x - step_back, y)
elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
solve(x + step_back, y)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x, y + step_back)
elif (maze[x][y - 1] == 1 or maze[x][y - 1] == 2) and maze[x + 1][y] == 1 and \
maze[x - 1][y] == 1 and maze[x][y + 1] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
solve(x - step_back, y)
elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
solve(x + step_back, y)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x, y - step_back)
# to check if the end of the maze were found
if maze[x + 1][y] == 3 or maze[x - 1][y] == 3 or maze[x][y + 1] == 3 or maze[x][y - 1] == 3:
print('Exit found in/Saída encontrada em xy({},{})'.format(x, y))
solve(1,1)