1074HardArrayDynamic ProgrammingBacktrackingBreadth-First SearchMemoizationMatrixHeuristic SearchBidirectional SearchA* Search

Fewest Slides to Order the Tray

Tracked in this browser only

Write code

Trains the technique from

LeetCode 773Sliding Puzzle

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def sliding_puzzle(tray: list[list[int]]) -> int:

Java

public int slidingPuzzle(int[][] tray)

The intended approach

Time O(1), since the layouts number at most seven hundred and twenty.Space O(1).

There are only six cells holding six different marks, so at most seven hundred and twenty layouts exist altogether. That is few enough to walk outward from the layout given, level by level, and read off the first level on which the wanted layout appears. Write a layout as the six marks in reading order, which makes it a short string that is cheap to compare and to remember. For each layout, find the gap and try each cell beside it, swapping the two to make a neighbouring layout. Remember every layout reached so none is worked on twice. Since every slide costs the same, walking outward level by level reaches each layout by the fewest slides, and the first time the wanted layout turns up is the answer. Running the walk dry without finding it means it cannot be reached at all, which happens because a slide never changes the layout's parity: only half the layouts are reachable from any given one.

Pythonentry point: sliding_puzzle

def sliding_puzzle(tray):
    from collections import deque
    start = "".join(str(tray[r][c]) for r in range(2) for c in range(3))
    goal = "123450"
    beside = {0: (1, 3), 1: (0, 2, 4), 2: (1, 5), 3: (0, 4), 4: (1, 3, 5), 5: (2, 4)}
    if start == goal:
        return 0
    seen = set([start])
    queue = deque([(start, 0)])
    while queue:
        state, slides = queue.popleft()
        gap = state.index('0')
        for other in beside[gap]:
            marks = list(state)
            marks[gap], marks[other] = marks[other], marks[gap]
            nxt = "".join(marks)
            if nxt == goal:
                return slides + 1
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, slides + 1))
    return -1

The obvious version

Turn the walk round: start from the wanted layout and walk outward over every layout reachable from it, recording how many slides each one takes. Then look the layout given up in that record, answering `-1` when it is not there. Builds the whole record whatever the layout given, rather than stopping at the first sight of the goal.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_sliding_puzzle(tray):
    from collections import deque
    start = "".join(str(tray[r][c]) for r in range(2) for c in range(3))
    goal = "123450"
    beside = {0: (1, 3), 1: (0, 2, 4), 2: (1, 5), 3: (0, 4), 4: (1, 3, 5), 5: (2, 4)}
    far = {goal: 0}
    queue = deque([goal])
    while queue:
        state = queue.popleft()
        gap = state.index('0')
        for other in beside[gap]:
            marks = list(state)
            marks[gap], marks[other] = marks[other], marks[gap]
            nxt = "".join(marks)
            if nxt not in far:
                far[nxt] = far[state] + 1
                queue.append(nxt)
    return far.get(start, -1)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in