I'm trying to run DFS on this 8 puzzle solver. the initial state is like this: 1 4 2 3 _ 5 6 7 8 where '_' represents a space. the goal state is this (formatted in my code as _12345678): _ 1 2 3 4 5 6 7 8 We're given an expected output: 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 (move tile 7 up, tile 8 left, etc) when I run my code, it begins correctly and goes through most of the states as expected. however, near the end, it acts weird, here's what happens near the end... Exploring state: Here, 8D just happened and only a few short moves left to complete it 1 2 5 3 4 _ 6 7 8 Exploring state: this is 5D 1 2 _ 3 4 5 6 7 8 Exploring state: here, 2R and then 1R should've happened, but instead the empty tile just randomly jumped to the middle, adjusting 4 and 5 as well. I'm not sure why this is happening, especially since it was going through DFS correctly up until this point 1 2 5 3 _ 4 6 7 8 Exploring state: and then it just continues looping through 1 2 5 3 7 4 6 _ 8 I have 2 main functions, get_neighbor and dfs. get_neighbor gets neighbors by moving the empty tile ('_') in valid directions. I'm not sure if there are logic issues in these functions or somewhere else, but it's really stumping me. if you'd like to run it on your own, this is the full code. warning, be prepared to control+c because it'll just keep going: 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 Continue reading...
