Practice/Microsoft/Leetcode 773. Sliding Puzzle

Leetcode 773. Sliding Puzzle

CodingMust

Problem

You are given a 2×3 board representing a sliding tile puzzle. The board contains tiles numbered 1 through 5 and one empty space represented by 0. In each move, you can swap the empty space (0) with any adjacent tile in the four cardinal directions (up, down, left, right).

Your task is to determine the minimum number of moves required to transform the board into the solved configuration: [[1,2,3],[4,5,0]]. If it's impossible to reach the solved state, return -1.

Requirements

1. Implement a function that takes a 2×3 board as input
2. Return the minimum number of moves to solve the puzzle
3. Return -1 if the puzzle cannot be solved
4. The empty space (0) can only swap with orthogonally adjacent tiles

Constraints

• The board is always 2×3 (2 rows, 3 columns)
• The board contains exactly one 0 and the numbers 1-5 each appearing once
• Time complexity should be reasonable for the state space size
• Space complexity should account for storing visited states

Examples

Example 1:

Input: board = [[1,2,3],[4,0,5]] Output: 1 Explanation: Swap the 0 with 5 to get [[1,2,3],[4,5,0]]

Example 2:

Input: board = [[1,2,3],[4,5,0]] Output: 0 Explanation: The board is already solved

Example 3:

Input: board = [[4,1,2],[5,0,3]] Output: 5 Explanation: One possible solution path: [[4,1,2],[5,0,3]] → [[4,1,2],[0,5,3]] → [[0,1,2],[4,5,3]] → [[1,0,2],[4,5,3]] → [[1,2,0],[4,5,3]] → [[1,2,3],[4,5,0]]

Example 4:

Input: board = [[1,2,3],[5,4,0]] Output: -1 Explanation: This configuration cannot be solved (wrong parity)