Я пытаюсь запустить DFS на этом решении головоломок из 8 головоломок. исходное состояние такое:
1 4 2
3 _ 5
6 7 8
где '_' представляет собой пробел.
целевое состояние следующее (в моем коде оно отформатировано как _12345678):
_ 1 2
3 4 5
6 7 8
Нам дан ожидаемый результат: 7U,8L,5D,2D,4R,7U,8U,5L,2D,4D,7R,8U,5U,2L,4D,7D ,8R,5U,2U,4L,7D,8D,5R,2U,4U,7L,8D,5D,2R,1R
(переместить плитку 7 вверх, плитку 8 влево и т. д.)
когда я запускаю свой код, он начинается правильно и проходит большинство состояний, как и ожидалось. однако ближе к концу это ведет себя странно, вот что происходит ближе к концу...
Исследование состояния: Здесь только что произошло 8D, и для его завершения осталось всего несколько коротких ходов
п>
1 2 5
3 4 _
6 7 8
Изучаем состояние: это 5D
1 2 _
3 4 5
6 7 8
Состояние исследования: здесь должно было произойти 2R, а затем 1R, но вместо этого пустая плитка просто случайно перескочила в середину, корректируя также 4 и 5. Я не уверен, почему это происходит, тем более что до этого момента DFS проходил правильно
1 2 5
3 _ 4
6 7 8
Изучение состояния: а затем просто продолжается цикл
1 2 5
3 7 4
6 _ 8
У меня есть две основные функции: get_neighbor и dfs. get_neighbor получает соседей, перемещая пустую плитку («_») в допустимых направлениях. Я не уверен, есть ли логические проблемы в этих функциях или где-то еще, но меня это действительно ставит в тупик.
если вы хотите запустить его самостоятельно, вот полный код . предупреждение: будьте готовы нажать Ctrl+C, потому что процесс продолжится:
import sys
state = "1423_5678"
# check if the current state matches the goal state
def is_goal(state):
return state == "_12345678"
# get neighbors by moving the empty tile ('_') in valid directions
def get_neighbors(state):
neighbors = []
state_list = list(state)
idx = state.index('_') # find the index of the empty tile
# Get the coordinates of the empty tile
row, col = divmod(idx, 3)
# possible moves
moves = [('U', 1, 0), ('L', 0, 1), ('D', -1, 0), ('R', 0, -1)]
# go over possible moves and check if they are valid
for move_desc, row_delta, col_delta in moves:
new_row, new_col = row + row_delta, col + col_delta
if 0
Подробнее здесь: https://stackoverflow.com/questions/790 ... s-8-puzzle
