Move Function not Working for N-Puzzle Problem

Question

I'm trying to make a IDDFS algorithm for a n-puzzle problem. However, the move function doesn't work properly. It will output the next move but change the values of the previous one (argument). Any advice on how to prevent this from happening would be greatly appreciated :)

def move_blank(i, j, n):
    if i + 1 < n:
        yield i + 1, j
    elif i - 1 >= 0:
        yield i - 1, j
    elif j + 1 < n:
        yield i, j + 1
    elif j - 1 >= 0:
        yield i, j - 1


def move(state):
    [i, j, grid] = state
    n = len(grid)
    for pos in move_blank(i, j, n):
        i1, j1 = pos
        grid[i][j], grid[i1][j1] = grid[i1][j1], grid[i][j]
        yield [i1, j1, grid]
        grid[i][j], grid[i1][j1] = grid[i1][j1], grid[i][j]


def is_goal(state, goal):
    return state == goal


def dfs_rec(puz, goal):
    if is_goal(puz[-1], goal):
        return puz
    else:
        for next_state in move(puz[-1]):
            if next_state not in puz:
                next_path = puz + [next_state]
                solution = dfs_rec(next_path, goal)
                if solution != None:
                    return solution
    return None

goal = [0, 2, [[3, 2, 0], [6, 1, 8], [4, 7, 5]]]
test = [0, 0, [[0, 7, 1], [4, 3, 2], [8, 6, 5]]]
path = dfs_rec([test], goal)

I assume "DFS" stands for "depth-first search", but I don't know what "IDDFS" means. I don't know what "an n-puzzle" means, either. Never assume that the acronyms you're using have a universal meaning. — Stef, Nov 10 '21 at 17:15
I have no idea what your "move" function is supposed to do and whether it does it or not, but `grid[i][j], grid[i1][j1] = grid[i1][j1], grid[i][j]` obviously modifies `grid`. If you don't want to modify `grid`, then one possibility is to make a copy of it instead. For instance, you can add one line of code `new_grid = [[cell for cell in row] for row in grid]` and then use `new_grid` instead of `grid`. — Stef, Nov 10 '21 at 17:17
Sorry, I mean Iterative Deepening Depth First Search and n-puzzle/n-tile is referring to the game with 8 tiles and one space, challenge being to move the tiles usually in chronological order. I'm trying to use IDDFS to rearrange the tiles. — , Nov 10 '21 at 17:18
Yes I have tried to copy the grid but not too sure on the syntax, I previously tried to use .copy() — , Nov 10 '21 at 17:22
Consider taking a look at [the `copy` module](https://docs.python.org/3/library/copy.html), and particularly the `deepcopy` function; also this related question: [python copy a list of lists?](https://stackoverflow.com/questions/28684154/python-copy-a-list-of-lists) — Stef, Nov 10 '21 at 17:27

Marat · Answer 1 · 2021-11-11T15:11:08.913

The problem is in move_blank. The generated moves are not mutually exclusive, yet only one of them will be generated. Replace all elifs with a simple if:

def move_blank(i, j, n):
    if i + 1 < n:
        yield i + 1, j
    if i - 1 >= 0:
        yield i - 1, j
    if j + 1 < n:
        yield i, j + 1
    if j - 1 >= 0:
        yield i, j - 1

There are other, less critical, issues with implementation:

if next_state not in puz is awfully expensive. Enumerating states and storing their id in a set would be much better (there are 362k states for an 8-puzzle, list lookup is faster than set only up to ~30 elements)
reliance on mutable arguments isn't a good practice. No immediate issues here but it might bite when you don't expect. Storing state as a 9-tuple would fix this and the previous concern.
solution = dfs_rec(next_path, goal) This problem is solvable and would be much cheaper without recursion. Yes, wikipedia pseudocode is not optimal.
it is not IDDFS - there is no depth limit per iteration

Move Function not Working for N-Puzzle Problem

1 Answers1