Katkat
Back

Solve a Two-by-Three Sliding Puzzle

AirbnbSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

Find the minimum moves needed to solve a 2-by-3 sliding puzzle, or report that the target is unreachable. Model each arrangement as a compact graph state, generate legal swaps involving the blank, and use breadth-first search without revisiting configurations.

Solve a Two-by-Three Sliding Puzzle

You are given a 2 x 3 board containing the integers 0 through 5 exactly once. The value 0 is the empty square. In one move, swap 0 with a horizontally or vertically adjacent value.

Return the minimum number of moves needed to reach the target board [[1, 2, 3], [4, 5, 0]], or -1 if the target is unreachable.

Function Signature

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

Examples

Input: [[1, 2, 3], [4, 0, 5]]
Output: 1

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

Constraints

  • board has exactly two rows and three columns.
  • Every integer from 0 through 5 appears exactly once.
  • Only swaps involving 0 and an orthogonally adjacent cell are legal.

Clarifications

  • The input board need not be modified.
  • Return 0 when the board is already in the target arrangement.

Hints

  • Treat each complete arrangement as a state in an unweighted graph.
  • Choose a compact, hashable state representation and avoid revisiting states.