How hard is LeetCode 773. Sliding Puzzle?

LeetCode 773. Sliding Puzzle is rated Hard on LeetCode.

Sliding Puzzle — LeetCode 773 Python Solution

HardBreadth-First SearchMemoizationArrayDynamic ProgrammingBacktrackingMatrix

Problem: #773
Pattern: Backtracking
Reading time: 8 min
Source: leetcode.com

The 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.

Example

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

Python solution

Python

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        t = [None] * 6

        def gets():
            for i in range(2):
                for j in range(3):
                    t[i * 3 + j] = str(board[i][j])
            return ''.join(t)

        def setb(s):
            for i in range(2):
                for j in range(3):
                    board[i][j] = int(s[i * 3 + j])

        def f():
            res = []
            i, j = next((i, j) for i in range(2) for j in range(3) if board[i][j] == 0)
            for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                x, y = i + a, j + b
                if 0 <= x < 2 and 0 <= y < 3:
                    board[i][j], board[x][y] = board[x][y], board[i][j]
                    res.append(gets())
                    board[i][j], board[x][y] = board[x][y], board[i][j]
            return res

        start = gets()
        end = "123450"
        if start == end:
            return 0
        vis = {start}
        q = deque([(start)])
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                x = q.popleft()
                setb(x)
                for y in f():
                    if y == end:
                        return ans
                    if y not in vis:
                        vis.add(y)
                        q.append(y)
        return -1

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 773. Sliding Puzzle is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 773. Sliding Puzzle?: LeetCode 773. Sliding Puzzle is rated Hard on LeetCode.
What topics does LeetCode 773. Sliding Puzzle cover?: LeetCode 773. Sliding Puzzle is tagged Breadth-First Search, Memoization, Array, Dynamic Programming, Backtracking and Matrix on LeetCode.