Show problems as
Classic problem #773HardArrayDynamic ProgrammingBacktrackingBreadth-First SearchMemoizationMatrixHeuristic SearchBidirectional SearchA* Search

Sliding Puzzle

Real-world version: Fewest Slides to Order the Tray
Tracked in this browser only
Read Sliding Puzzle on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tray holds five marked tiles and one gap, laid out as tray, two rows of three. The tiles carry the marks 1 through 5 and the gap is written 0.

One slide moves a tile that sits directly beside the gap, edgewise, into the gap; the tile and the gap change places.

Return the fewest slides needed to reach the layout with 1, 2, 3 along the top row and 4, 5 then the gap along the bottom, or -1 when no number of slides can reach it.

Examples

Example 1

Input
tray = [[1, 2, 3], [4, 5, 0]]
Output
0

The tray is already in the wanted layout, so nothing needs sliding.

Example 2

Input
tray = [[0, 1, 2], [4, 5, 3]]
Output
3

Sliding the 4 up, then the 5 left, then the 3 left brings the tray into order in three slides.

Example 3

Input
tray = [[2, 1, 3], [4, 5, 0]]
Output
-1

Only the 1 and the 2 are out of order, with everything else already in place. A slide never changes the layout's parity, so this layout can never reach the wanted one.

Constraints

  • tray.length == 2
  • tray[i].length == 3
  • 0 <= tray[i][j] <= 5
  • No two cells of the tray hold the same mark.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sliding_puzzle(tray: list[list[int]]) -> int:
Java
public int slidingPuzzle(int[][] tray)

More on the same topics