Sliding Puzzle Python Solution with Tests

lcpy gen -n 773   # by problem number
lcpy gen -s sliding_puzzle   # by problem name

Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.

Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.

Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]

from collections import deque


class Solution:
    # Time: O((n * m)!) states, each expanded once
    # Space: O((n * m)!)
    def sliding_puzzle(self, board: list[list[int]]) -> int:
        target = (1, 2, 3, 4, 5, 0)
        start = tuple(x for row in board for x in row)
        neighbors = ((1, 3), (0, 2, 4), (1, 5), (0, 4), (1, 3, 5), (2, 4))

        queue = deque([(start, start.index(0), 0)])
        seen = {start}
        while queue:
            state, zero, moves = queue.popleft()
            if state == target:
                return moves
            for nz in neighbors[zero]:
                nxt = list(state)
                nxt[zero], nxt[nz] = nxt[nz], nxt[zero]
                ns = tuple(nxt)
                if ns not in seen:
                    seen.add(ns)
                    queue.append((ns, nz, moves + 1))
        return -1