Problem statement

https://leetcode.com/problems/sliding-puzzle/

Solution

Here we need to find minimal number of moves, so bfs can be a good idea here. Our state is tuple of 6 numbers. Also let us create dictionary of neighbors, so on each move we can find index of 0 and visit all possible neighbors.

Complexity

Time complexity is O(n!*n*4), where n = 6 is number of tiles here.

Code

class Solution:
    def slidingPuzzle(self, board):
        d = {0:(1,3), 1:(0,2,4), 2:(1,5), 3:(0,4), 4:(1,3,5), 5:(2,4)}
        start = tuple(board[0]) + tuple(board[1])
        queue = deque([(0, start)])
        visited = set([start])
        
        while queue:
            steps, pos = queue.popleft()
            if pos == (1,2,3,4,5,0): 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