Sliding Puzzle Python Solution with Tests

Tested Python solution for LeetCode 773 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 773, Hard. Topics: Array, Breadth-First Search, Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

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

​

Problem

On an 2 x 3 board, there are five tiles labeled from 1 to 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given the puzzle board board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

​

Examples

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]]

​

Constraints

• board.length == 2
• board[i].length == 3
• 0 <= board[i][j] <= 5
• Each value board[i][j] is unique.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

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

​

Complexity

Time	Space
O((n * m)!) states, each expanded once	O((n * m)!)

​

Tags

NeetCode All.