On an 2 x 3 board, there are five tiles labeled from 1 to 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
Given the puzzle board board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
Example 1:
Input: board = [[1,2,3],[4,0,5]] Output: 1 Explanation: Swap the 0 and the 5 in one move.
Example 2:
Input: board = [[1,2,3],[5,4,0]] Output: -1 Explanation: No number of moves will make the board solved.
Example 3:
Input: board = [[4,1,2],[5,0,3]] Output: 5 Explanation: 5 is the smallest number of moves that solves the board. An example path: After move 0: [[4,1,2],[5,0,3]] After move 1: [[4,1,2],[0,5,3]] After move 2: [[0,1,2],[4,5,3]] After move 3: [[1,0,2],[4,5,3]] After move 4: [[1,2,0],[4,5,3]] After move 5: [[1,2,3],[4,5,0]]
Constraints:
board.length == 2board[i].length == 30 <= board[i][j] <= 5board[i][j] is unique.The Sliding Puzzle problem asks you to determine the minimum number of moves required to reach a target board configuration by sliding tiles into the empty space. The key idea is to treat each board configuration as a state and explore all reachable states until the target configuration is found.
A common strategy is to model the puzzle as a graph and apply Breadth-First Search (BFS). Convert the board into a compact representation such as a string, which allows easy comparison and storage in a visited set. From each state, generate new states by swapping the blank tile with its valid neighbors. BFS guarantees the shortest path because it explores configurations level by level.
For optimization, predefine neighbor indices of the blank tile to quickly generate transitions. Since the puzzle size is fixed (e.g., 2×3 board), the total number of possible permutations is limited. BFS combined with memoization of visited states efficiently avoids repeated exploration.
Time Complexity: approximately O(N!) for all possible permutations of tiles, but bounded for small boards. Space Complexity: O(N!) to store visited states and the BFS queue.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search with state encoding | O(N!) | O(N!) |
| A* Search (heuristic optimization) | O(N!) worst case, often faster in practice | O(N!) |
code_report
Use these hints if you're stuck. Try solving on your own first.
Perform a breadth-first-search, where the nodes are the puzzle boards and edges are if two puzzle boards can be transformed into one another with one move.
Time Complexity: O(1) - There are a constant number of states (720) due to permutation limits.
Space Complexity: O(1) - As with time, space usage peaks at 720 given state permutations.
1from collections import deque
2
3def sliding_puzzle(board):
4 start = ''.join(str(num) for row in board for num in row)
5 target = '123450'
6 neighbors = {
7 0: [1, 3],
8 1: [0, 2, 4],
9 2: [1, 5],
10 3: [0, 4],
11 4: [3, 1, 5],
12 5: [2, 4]
13 }
14 queue = deque([(start, start.index('0'), 0)]) # (board_str, zero_index, depth)
15 visited = {start}
16 while queue:
17 board_str, zero_index, depth = queue.popleft()
18 if board_str == target:
19 return depth
20 for adj in neighbors[zero_index]:
21 new_board = list(board_str)
22 new_board[zero_index], new_board[adj] = new_board[adj], new_board[zero_index]
23 new_board_str = ''.join(new_board)
24 if new_board_str not in visited:
25 visited.add(new_board_str)
26 queue.append((new_board_str, adj, depth + 1))
27 return -1This Python code uses a BFS approach to solve the sliding puzzle. We convert the board into a string and use a map to determine swap positions for '0'. Initially, each configuration is enqueued with its depth. The goal is to find the shortest path to the solved state.
Time Complexity: O((6! = 720) log(720))
Space Complexity: O(720), based on the number of states handled.
1import java.util.*;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, sliding puzzle style problems are popular in technical interviews because they test graph traversal, state encoding, and search strategies. Variants using BFS or A* search have appeared in interviews at major tech companies.
The most common optimal approach is Breadth-First Search (BFS). By treating each board configuration as a graph node and exploring neighbors level by level, BFS guarantees the minimum number of moves to reach the target state.
Converting the board into a string or serialized format makes it easier to store and compare states. It allows efficient use of hash sets or maps to track visited configurations and avoid redundant exploration.
A queue is typically used for BFS to process states level by level. Additionally, a hash set is essential to track visited configurations so the algorithm does not revisit the same board states repeatedly.
This Java code implements the A* search algorithm to tackle the sliding puzzle. Nodes are compared based on the cost estimation which combines depth and heuristic calculations. Using Manhattan distance as a heuristic ensures the solution is efficiently discovered through optimal path estimation.