leetcode-773 Sliding Puzzle

# Given a 2x3 board with tiles 0-5 (0 is empty), return minimum moves to solve.

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        from collections import deque

        # Convert board to string
        start = ''.join(str(cell) for row in board for cell in row)
        target = '123450'

        # Neighbors for each position in 1D representation
        neighbors = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }

        queue = deque([(start, 0)])
        visited = {start}

        while queue:
            state, moves = queue.popleft()

            if state == target:
                return moves

            # Find 0 position
            zero_pos = state.index('0')

            # Try all possible swaps
            for neighbor in neighbors[zero_pos]:
                # Swap 0 with neighbor
                new_state = list(state)
                new_state[zero_pos], new_state[neighbor] = new_state[neighbor], new_state[zero_pos]
                new_state = ''.join(new_state)

                if new_state not in visited:
                    visited.add(new_state)
                    queue.append((new_state, moves + 1))

        return -1

# Time: O(m*n * (m*n)!), Space: O((m*n)!)
# AirBnB: Tests BFS and state space search