LeetCode 773 - Sliding Puzzle

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Backtracking, Breadth-First Search, Memoization, Matrix

Solution

Problem Understanding

The Sliding Puzzle problem presents a 2 x 3 board containing five numbered tiles from 1 to 5 and a blank space represented as 0. The goal is to transform the board into a solved configuration [[1,2,3],[4,5,0]] using the fewest number of moves, where a move consists of swapping 0 with any of its adjacent tiles (up, down, left, right). The input board is a 2D list representing the current configuration of the tiles. The expected output is an integer representing the minimum number of moves required to reach the solved state, or -1 if it is impossible.

The problem constraints indicate that the board is small and fixed in size (2x3) and all values are unique, so the number of possible states is limited (6! = 720). Edge cases include boards that are already solved, boards with tiles in reverse order, and boards where the solution is impossible due to parity constraints (like unsolvable permutations).

Understanding these constraints allows us to leverage graph search techniques efficiently, since we can treat each board configuration as a node and moves as edges.

Approaches

A brute-force approach would involve generating all possible sequences of moves from the initial board state until we either reach the solved state or exhaust all possibilities. This could be done with recursive backtracking. While this approach is correct in theory, it is inefficient because it explores many redundant paths and can revisit previously seen board configurations multiple times, leading to exponential time complexity.

The optimal approach is to model the puzzle as a graph where each node represents a board configuration, and edges represent valid moves of 0. Breadth-First Search (BFS) is appropriate because we are searching for the shortest sequence of moves. BFS guarantees that the first time we reach the solved state, we have done so using the minimal number of moves. We also use a hash set to track visited states, preventing cycles and redundant computation. A key insight is to serialize the 2D board into a string or a tuple so that states can be easily compared and stored in a set.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(6!)	O(6!)	Explores all possible sequences of moves recursively, revisiting states multiple times.
Optimal BFS	O(6!)	O(6!)	BFS on state graph guarantees minimal moves; visited set prevents redundant exploration.

Algorithm Walkthrough

Serialize the board: Convert the 2x3 board into a string, e.g., '123450', to make it easier to track visited states and compare boards.
Define adjacency map: Precompute a mapping from each index of 0 in the string to the indices it can swap with. For a 2x3 board, the mapping is:

0 -> [1, 3]
1 -> [0, 2, 4]
2 -> [1, 5]
3 -> [0, 4]
4 -> [1, 3, 5]
5 -> [2, 4]

Initialize BFS queue: Begin BFS with the initial serialized board and a move count of 0. Track visited states using a set to avoid revisiting.
BFS traversal: While the queue is not empty, dequeue the front element. If it matches the target '123450', return the current move count. Otherwise, for each valid swap of 0, generate the new board state, and if it has not been visited, add it to the queue and mark it visited.
Return -1 if unsolvable: If BFS completes without reaching the solved state, return -1 indicating that the puzzle is unsolvable.

Why it works: BFS guarantees the minimal move count because it explores all states at depth d before moving to depth d+1. By marking visited states, it ensures each state is processed only once, avoiding infinite loops and redundant computation.

Python Solution

from collections import deque
from typing import List

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        start = ''.join(str(num) for row in board for num in row)
        target = '123450'
        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 = set([start])

        while queue:
            state, moves = queue.popleft()
            if state == target:
                return moves

            zero_index = state.index('0')
            for swap_index in neighbors[zero_index]:
                new_state = list(state)
                new_state[zero_index], new_state[swap_index] = new_state[swap_index], new_state[zero_index]
                new_state_str = ''.join(new_state)
                if new_state_str not in visited:
                    visited.add(new_state_str)
                    queue.append((new_state_str, moves + 1))

        return -1

This implementation first converts the board into a string for easy state comparison. The BFS queue keeps tuples of (state, moves) for tracking the current board and the number of moves taken. For each dequeued state, it finds the position of 0, generates all possible valid moves, and enqueues new states not yet visited. The BFS guarantees the shortest path due to level-order traversal.

Go Solution

package main

import (
    "container/list"
    "strconv"
)

func slidingPuzzle(board [][]int) int {
    start := ""
    for i := 0; i < 2; i++ {
        for j := 0; j < 3; j++ {
            start += strconv.Itoa(board[i][j])
        }
    }
    target := "123450"
    neighbors := [][]int{
        {1, 3},
        {0, 2, 4},
        {1, 5},
        {0, 4},
        {1, 3, 5},
        {2, 4},
    }

    visited := map[string]bool{start: true}
    queue := list.New()
    queue.PushBack([2]interface{}{start, 0})

    for queue.Len() > 0 {
        elem := queue.Front()
        queue.Remove(elem)
        state := elem.Value.([2]interface{})[0].(string)
        moves := elem.Value.([2]interface{})[1].(int)

        if state == target {
            return moves
        }

        zeroIndex := -1
        for i, ch := range state {
            if ch == '0' {
                zeroIndex = i
                break
            }
        }

        for _, swapIndex := range neighbors[zeroIndex] {
            newState := []byte(state)
            newState[zeroIndex], newState[swapIndex] = newState[swapIndex], newState[zeroIndex]
            newStateStr := string(newState)
            if !visited[newStateStr] {
                visited[newStateStr] = true
                queue.PushBack([2]interface{}{newStateStr, moves + 1})
            }
        }
    }
    return -1
}

The Go implementation mirrors the Python version, using a container/list for the BFS queue and a map for visited states. It carefully converts the board to a string and back, as Go does not have Python's dynamic list/string behavior.

Worked Examples

Example 1: [[1,2,3],[4,0,5]]

Queue State	Moves	Zero Index	New States
`'123405'`	0	4	`'103425'`, `'123045'`, `'123450'`
`'123450'`	1	-	solved

Output: 1.

Example 2: [[1,2,3],[5,4,0]]

BFS explores all 720 possible states but never reaches '123450'. Output: -1.

Example 3: [[4,1,2],[5,0,3]]

BFS finds a path of length 5 through the states:

'412503' -> '012453' -> '412053' -> '102453' -> '120453' -> '123450'

Output: 5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(6!)	There are 6! possible states; BFS may visit each once.
Space	O(6!)	Visited set stores all unique board states; queue may hold multiple states.

Even though O(6!) seems large, 720 states is small and tractable.

Test Cases

# Provided examples
assert Solution().slidingPuzzle([[1,2,3],[4,0,5]]) == 1  # Single move needed
assert Solution().slidingPuzzle([[1,2,3],[5,4,0]]) == -1 # Impossible configuration
assert Solution().slidingPuzzle([[4,1,2],[5,0,3]]) == 5  # Smallest path is 5 moves

# Edge cases
assert Solution().slidingPuzzle([[1,2,3