Problem statement

https://binarysearch.com/problems/8-Puzzle/

Solution

Variation of Leetcode 0773 Sliding Puzzle, but here we have 3 x 3, not 2 x 3 puzzle.

Complexity

Time complexity is O(n!*n*4), where n = 9 is number of tiles here. One of the possible ways to make it faster is to use bidirectional bfs.

Code

class Solution:
    def solve(self, board):
        d = {0:(1,3),1:(0,2,4),2:(1,5),3:(0,4,6),4:(1,3,5,7),5:(2,4,8),6:(3,7),7:(4,6,8),8:(5,7)}
        start = tuple(board[0]) + tuple(board[1]) + tuple(board[2])
        queue = deque([(0, start)])
        visited = set([start])
        
        while queue:
            steps, pos = queue.popleft()
            if pos == (0,1,2,3,4,5,6,7,8): return steps
            ind = pos.index(0)
            for neib in d[ind]:
                board = list(pos)
                board[ind], board[neib] = board[neib], board[ind]
                board = tuple(board)
                if board not in visited:
                    visited.add(board)
                    queue.append((steps + 1, board))
                    
        return -1