我正在尝试在这个 8 谜题求解器上运行 DFS。初始状态是这样的：
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 通过沿有效方向移动空图块 ('_') 来获取邻居。我不确定这些函数或其他地方是否存在逻辑问题，但这确实难倒了我。
如果您想自己运行它，这是完整的代码。警告，准备好 control+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 <= new_row < 3 and 0 <= new_col < 3: # check if new position is within bounds
new_idx = new_row * 3 + new_col # calculate the new index after the move
# Swap the empty space with the neighboring tile
new_state_list = state_list[:] # create a copy of the state list
tile_moved = new_state_list[new_idx] # get the tile that's going to move
new_state_list[idx], new_state_list[new_idx] = new_state_list[new_idx], new_state_list[idx]
new_state = ''.join(new_state_list) # join the list back into a string
# Append the new state and the move (with the tile that moved) to neighbors
neighbors.append((new_state, f"{tile_moved}{move_desc}"))
return neighbors
# Depth-First Search (DFS)
def dfs(initial_state):
stack = [(initial_state, [])] # stack stores (current_state, path_to_current_state)
visited = set([initial_state]) # mark initial state as visited
while stack:
current_state, path = stack.pop() # pop the last state added (DFS)
print(f"Exploring state:\n{format_state(current_state)}") # Print the current state
if is_goal(current_state):
return path # return the path leading to the goal when found
# Explore neighbors in the natural order (ULDR), but reversed when appending to stack
neighbors = get_neighbors(current_state)
for neighbor, move in neighbors[::-1]: # reverse the list to explore ULDR
if neighbor not in visited: # only explore unvisited states
visited.add(neighbor) # mark the neighbor as visited
stack.append((neighbor, path + [move])) # add the neighbor to the stack with updated path
return None # return None if no solution is found
# Helper function to format the state as a 3x3 grid (for better visualization in debugging)
def format_state(state):
return '\n'.join([state[i:i+3] for i in range(0, len(state), 3)])
# Main function to execute the DFS
if __name__ == '__main__':
#initial_state = read_initial_state() # read initial puzzle state from file
initial_state = state
solution_path = dfs(initial_state) # execute DFS to find the solution path
if solution_path:
print("The solution of Q1.1.a (DFS) is:")
print(','.join(solution_path)) # print the solution as a comma-separated list of moves
else:
print("No solution found.") # in case no solution is found
movesget_neighbors所以，应该是这样的：
moves = [('U', -1, 0), ('L', 0, -1), ('D', 1, 0), ('R', 0, 1)]
更改后的结果：
Exploring state:
142
3_5
678
Exploring state:
1_2
345
678
Exploring state:
_12
345
678
The solution of Q1.1.a (DFS) is:
4U,1L