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. Im 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’s 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