Sliding Puzzle
HardPrompt
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] <= 5- Each value
board[i][j]is unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This problem can be modeled as finding the shortest path in a state graph, where each node is a unique board configuration and edges connect configurations that are reachable in a single move. Breadth-First Search (BFS) is a classic and ideal algorithm for finding the shortest path in an unweighted graph like this. We start from the initial board configuration and explore its neighbors, then the neighbors of those neighbors, and so on, level by level. This guarantees that the first time we reach the target configuration, we have done so in the minimum possible number of moves.
Algorithm
- Convert the 2x3
boardinto a single stringstartfor easier manipulation and storage. - Define the
targetstring as "123450". - Initialize a queue and add the
startstate. - Initialize a
visitedset to keep track of states we've already processed, and addstartto it. - Initialize a
movescounter to 0. - While the queue is not empty, perform a level-order traversal:
- Process all states at the current level (get the queue
size). - For each
currentstate dequeued:- If
currentmatches thetarget, we have found the shortest path. Return the currentmovescount. - Find the index of the empty tile '0'.
- Generate all valid neighbor states by swapping '0' with its adjacent tiles.
- For each
nextStatethat has not been visited, add it to the queue and thevisitedset.
- If
- Increment the
movescounter after processing each level.
- Process all states at the current level (get the queue
- If the queue becomes empty and the target has not been reached, it means the puzzle is unsolvable. Return -1.
Walkthrough
To implement BFS, we first need a convenient way to represent the board state. A 2x3 integer array is cumbersome to use as a key in a hash set or map for tracking visited states. A better approach is to flatten the 2x3 board into a 6-character string, e.g., [[1,2,3],[4,0,5]] becomes "123405". This string representation is unique for each board state and easy to work with.
The core of the algorithm is a queue that holds the states to be explored and a set that stores states we have already visited to prevent cycles and redundant work. We start by adding the initial state string to the queue and the visited set. The search proceeds in levels, where each level corresponds to one move. In each iteration of the main loop, we process all the states currently in the queue. For each state, we generate all possible next states by swapping the '0' tile with its valid neighbors. If a generated neighbor state has not been visited before, we add it to the queue and the visited set. We continue this process until we find the target state "123450" or the queue becomes empty, indicating the puzzle is unsolvable.
class Solution { public int slidingPuzzle(int[][] board) { String target = "123450"; StringBuilder sb = new StringBuilder(); for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { sb.append(board[i][j]); } } String start = sb.toString(); if (start.equals(target)) { return 0; } // Precomputed possible moves for the '0' at each index (0-5) int[][] moves = new int[][]{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}; Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.offer(start); visited.add(start); int level = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String current = queue.poll(); if (current.equals(target)) { return level; } int zeroPos = current.indexOf('0'); for (int nextPos : moves[zeroPos]) { char[] chars = current.toCharArray(); char temp = chars[zeroPos]; chars[zeroPos] = chars[nextPos]; chars[nextPos] = temp; String nextState = new String(chars); if (!visited.contains(nextState)) { visited.add(nextState); queue.offer(nextState); } } } level++; } return -1; }}Complexity
Time
O(N * K), where N is the total number of states and K is the maximum number of neighbors for a state. For this problem, N = 720 and K = 4. The algorithm visits each state and each transition at most once. Since N and K are constants, the time complexity is effectively O(1).
Space
O(N), where N is the total number of possible states. For a 2x3 board with 6 unique tiles, N = 6! = 720. The space is needed for the queue and the visited set, which in the worst case might store all possible states. Since N is a constant, the complexity is O(1).
Trade-offs
Pros
Guaranteed to find the shortest path because it explores the graph level by level.
Relatively simple to understand and implement.
Cons
Explores the state space blindly without any guidance, which can be inefficient for problems with larger state spaces.
May visit many states that are far from the solution before finding the target.
A* Search is an informed search algorithm that improves upon BFS by using a heuristic function to guide its search towards the goal. It prioritizes exploring states that appear to be closer to the solution. The priority of a state n is determined by the formula f(n) = g(n) + h(n), where g(n) is the actual cost (number of moves) from the start state to n, and h(n) is the estimated (heuristic) cost from n to the target state. By exploring states with the lowest f(n) value first, A* can find the shortest path much more efficiently than a blind search.
Algorithm
- Define a
Stateobject to hold the board string,gcost (moves from start), andfcost (g+ heuristic). - Initialize a priority queue ordered by the
fcost (lowest first). - Initialize a map
gCoststo store the minimum moves found so far to reach any state. - Calculate the heuristic (Manhattan distance) for the
startstate. - Add the initial
State(start, 0, h(start))to the priority queue andgCostsmap. - While the priority queue is not empty:
- Poll the state
currentwith the lowestfcost. - If
currentis the target state, return itsgcost. - Generate all valid neighbor states.
- For each
nextState:- Calculate its new
gcost (current.g + 1). - If a shorter or equal path to
nextStatehas already been found (i.e., it's ingCostswith a lower value), skip it. - Otherwise, update its
gcost ingCosts, calculate its heuristich, and add the newStateto the priority queue.
- Calculate its new
- Poll the state
- If the loop finishes, the target is unreachable, so return -1.
Walkthrough
For the A* algorithm, we use a priority queue to store states, ordered by their f(n) value. A good heuristic h(n) for sliding puzzles is the Manhattan distance. For each tile (from 1 to 5), we calculate the sum of the absolute differences of its current coordinates and its target coordinates. This heuristic is admissible (it never overestimates the true cost), which is a crucial property that guarantees A* will find the optimal solution.
We also maintain a map to store the minimum g(n) cost found so far for each visited state. This prevents us from exploring longer paths to states we've already reached more efficiently.
The algorithm proceeds by repeatedly extracting the most promising state (lowest f value) from the priority queue. If it's the target, we're done. Otherwise, we generate its neighbors, calculate their g and h costs, and add them to the priority queue if they represent a better path to that state. This guided approach prunes large parts of the search space that are unlikely to be on the shortest path.
class Solution { class State { String board; int g; // cost from start int h; // heuristic cost to target State(String board, int g, int h) { this.board = board; this.g = g; this.h = h; } } public int slidingPuzzle(int[][] board) { String target = "123450"; StringBuilder sb = new StringBuilder(); for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { sb.append(board[i][j]); } } String startStr = sb.toString(); if (startStr.equals(target)) return 0; // Precompute target positions for heuristic calculation int[][] targetPos = new int[6][2]; targetPos[1] = new int[]{0, 0}; targetPos[2] = new int[]{0, 1}; targetPos[3] = new int[]{0, 2}; targetPos[4] = new int[]{1, 0}; targetPos[5] = new int[]{1, 1}; targetPos[0] = new int[]{1, 2}; PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> (a.g + a.h) - (b.g + b.h)); Map<String, Integer> gCosts = new HashMap<>(); int startH = calculateHeuristic(startStr, targetPos); pq.offer(new State(startStr, 0, startH)); gCosts.put(startStr, 0); int[][] moves = new int[][]{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}; while (!pq.isEmpty()) { State current = pq.poll(); if (current.board.equals(target)) { return current.g; } int zeroPos = current.board.indexOf('0'); for (int nextPos : moves[zeroPos]) { char[] chars = current.board.toCharArray(); char temp = chars[zeroPos]; chars[zeroPos] = chars[nextPos]; chars[nextPos] = temp; String nextStateStr = new String(chars); int newG = current.g + 1; if (gCosts.getOrDefault(nextStateStr, Integer.MAX_VALUE) <= newG) { continue; } gCosts.put(nextStateStr, newG); int newH = calculateHeuristic(nextStateStr, targetPos); pq.offer(new State(nextStateStr, newG, newH)); } } return -1; } private int calculateHeuristic(String board, int[][] targetPos) { int h = 0; for (int i = 0; i < 6; i++) { int tile = board.charAt(i) - '0'; if (tile == 0) continue; int currentX = i / 3; int currentY = i % 3; int targetX = targetPos[tile][0]; int targetY = targetPos[tile][1]; h += Math.abs(currentX - targetX) + Math.abs(currentY - targetY); } return h; }}Complexity
Time
O(N log N), where N is the number of states explored. The `log N` factor comes from the priority queue operations. Since A* explores fewer states than BFS, it's generally faster despite the logarithmic factor. For this problem's fixed state space, the complexity is constant, O(1).
Space
O(N), where N is the number of states. In the worst case, it might need to store all states in the priority queue and the cost map. For this problem, N=720, so the space is constant, O(1).
Trade-offs
Pros
Generally more efficient than blind search algorithms like BFS because it explores fewer states.
Guaranteed to find the shortest path if the heuristic function is admissible (like Manhattan distance).
Cons
More complex to implement than BFS due to the priority queue and heuristic calculation.
The performance is highly dependent on the quality of the heuristic function.
Bidirectional BFS is a powerful optimization that performs two simultaneous searches: one forward from the initial state and one backward from the target state. The search terminates as soon as the two search frontiers intersect. This approach dramatically reduces the search space compared to a single-ended search. If the shortest path has length d and the branching factor is b, a standard BFS explores roughly b^d states, whereas a bidirectional BFS explores roughly 2 * b^(d/2) states. This exponential reduction makes it highly efficient for finding shortest paths.
Algorithm
- Initialize two sets,
q_fwdfor the forward search frontier andq_bwdfor the backward search frontier. Add thestartstate toq_fwdand thetargetstate toq_bwd. - Use a single
visitedset to track all states explored from both directions, initially containingstartandtarget. - Initialize a
movescounter to 0. - In a loop that continues as long as both frontiers are non-empty:
- To keep the search balanced, always choose to expand the smaller of the two frontiers.
- Increment
moves. - Create a
next_levelset to store the new frontier. - For each
statein the chosen frontier:- Generate all its neighbor states.
- For each
nextState:- If the
nextStateis found in the other frontier, it means the two searches have met. A path is found, so return the currentmovescount. - If the
nextStatehas not been visited before, add it to thevisitedset and thenext_levelset.
- If the
- Replace the expanded frontier with the
next_levelset.
- If the loop terminates because one frontier becomes empty, the puzzle is unsolvable. Return -1.
Walkthrough
The implementation uses two sets to represent the frontiers of the forward and backward searches. We also use a general visited set to ensure we don't process any state more than once. We initialize the forward frontier with the start state and the backward frontier with the target state.
The main loop proceeds level by level, but with a twist. In each step, we first check which frontier is smaller and choose to expand that one. This keeps the two search 'circles' roughly the same size, maximizing the chance of an early intersection. We generate all neighbors for each state in the chosen frontier. If any neighbor is already in the other frontier, we have found a meeting point and thus the shortest path. The length of this path is the current number of moves made. If a neighbor is new (not in the visited set), we add it to a temporary set for the next level and to the visited set. This process continues until the frontiers meet or one becomes empty.
class Solution { public int slidingPuzzle(int[][] board) { String target = "123450"; StringBuilder sb = new StringBuilder(); for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { sb.append(board[i][j]); } } String start = sb.toString(); if (start.equals(target)) return 0; int[][] moves = new int[][]{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}; Set<String> q_fwd = new HashSet<>(); Set<String> q_bwd = new HashSet<>(); Set<String> visited = new HashSet<>(); q_fwd.add(start); q_bwd.add(target); visited.add(start); visited.add(target); int dist = 0; while (!q_fwd.isEmpty() && !q_bwd.isEmpty()) { // Always expand the smaller frontier if (q_fwd.size() > q_bwd.size()) { Set<String> temp = q_fwd; q_fwd = q_bwd; q_bwd = temp; } dist++; Set<String> next_level = new HashSet<>(); for (String current : q_fwd) { int zeroPos = current.indexOf('0'); for (int nextPos : moves[zeroPos]) { char[] chars = current.toCharArray(); char temp = chars[zeroPos]; chars[zeroPos] = chars[nextPos]; chars[nextPos] = temp; String nextState = new String(chars); if (q_bwd.contains(nextState)) { return dist; } if (!visited.contains(nextState)) { visited.add(nextState); next_level.add(nextState); } } } q_fwd = next_level; } return -1; }}Complexity
Time
O(b^(d/2)). The algorithm runs two searches that meet in the middle, each exploring to a depth of roughly `d/2`. This provides an exponential speedup over standard BFS. For this problem, the complexity is constant, O(1).
Space
O(b^(d/2)), where `b` is the branching factor and `d` is the shortest path length. This is needed to store the two frontiers and the visited set. For this problem, this is constant space, O(1), but theoretically much smaller than a single BFS.
Trade-offs
Pros
Significantly faster than standard BFS by drastically reducing the number of states explored.
Often the most efficient algorithm for shortest path problems on unweighted graphs with a known target.
Lower overhead per node compared to A* as it doesn't require heuristic calculations or a priority queue.
Cons
Slightly more complex to implement than a standard BFS.
Requires the target state to be known and the graph transitions to be reversible, both of which are true for this problem.
Solutions
Solution
class Solution {private int m = 2;private int n = 3;public int slidingPuzzle(int[][] board) { String start = ""; String end = "123450"; String seq = ""; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { start += board[i][j]; if (board[i][j] != 0) { seq += board[i][j]; } } } if (!check(seq)) { return -1; } PriorityQueue<Pair<Integer, String>> q = new PriorityQueue<>(Comparator.comparingInt(Pair : : getKey)); Map<String, Integer> dist = new HashMap<>(); dist.put(start, 0); q.offer(new Pair<>(f(start), start)); int[] dirs = {-1, 0, 1, 0, -1}; while (!q.isEmpty()) { String state = q.poll().getValue(); int step = dist.get(state); if (end.equals(state)) { return step; } int p1 = state.indexOf("0"); int i = p1 / n, j = p1 % n; char[] s = state.toCharArray(); for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n) { int p2 = x * n + y; swap(s, p1, p2); String next = String.valueOf(s); if (!dist.containsKey(next) || dist.get(next) > step + 1) { dist.put(next, step + 1); q.offer(new Pair<>(step + 1 + f(next), next)); } swap(s, p1, p2); } } } return -1; }private void swap(char[] arr, int i, int j) { char t = arr[i]; arr[i] = arr[j]; arr[j] = t; }private int f(String s) { int ans = 0; for (int i = 0; i < m * n; ++i) { if (s.charAt(i) != '0') { int num = s.charAt(i) - '1'; ans += Math.abs(i / n - num / n) + Math.abs(i % n - num % n); } } return ans; }private boolean check(String s) { int n = s.length(); int cnt = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (s.charAt(i) > s.charAt(j)) { ++cnt; } } } return cnt % 2 == 0; }}class Solution {public: int m = 2; int n = 3; int slidingPuzzle(vector<vector<int>> &board) { string start, seq; string end = "123450"; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { start += char(board[i][j] + '0'); if (board[i][j] != 0) seq += char(board[i][j] + '0'); } } if (!check(seq)) return -1; typedef pair<int, string> PIS; priority_queue<PIS, vector<PIS>, greater<PIS>> q; unordered_map<string, int> dist; dist[start] = 0; q.push({f(start), start}); vector<int> dirs = {-1, 0, 1, 0, -1}; while (!q.empty()) { PIS t = q.top(); q.pop(); string state = t.second; int step = dist[state]; if (state == end) return step; int p1 = state.find('0'); int i = p1 / n, j = p1 % n; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x < 0 || x >= m || y < 0 || y >= n) continue; int p2 = x * n + y; swap(state[p1], state[p2]); if (!dist.count(state) || dist[state] > step + 1) { dist[state] = step + 1; q.push({step + 1 + f(state), state}); } swap(state[p1], state[p2]); } } return -1; } bool check(string s) { int n = s.size(); int cnt = 0; for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) if (s[i] > s[j]) ++cnt; return cnt % 2 == 0; } int f(string s) { int ans = 0; for (int i = 0; i < m * n; ++i) { if (s[i] == '0') continue; int num = s[i] - '1'; ans += abs(num / n - i / n) + abs(num % n - i % n); } return ans; }};class Solution: def slidingPuzzle(self, board: List[List[int]]) -> int: m, n = 2, 3 seq = [] start, end = '', '123450' for i in range(m): for j in range(n): if board[i][j] != 0: seq . append(board[i][j]) start += str(board[i][j]) def check(seq): n = len(seq) cnt = sum(seq[i] > seq[j] for i in range(n) for j in range(i, n)) return cnt % 2 == 0 def f(s): ans = 0 for i in range(m * n): if s[i] != '0': num = ord(s[i]) - ord('1') ans += abs(i // n - num // n) + abs(i % n - num % n) return ans if not check(seq): return - 1 q = [(f(start), start)] dist = {start: 0} while q: _, state = heappop(q) if state == end: return dist[state] p1 = state . index('0') i, j = p1 // n, p1 % n s = list(state) for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n: p2 = x * n + y s[p1], s[p2] = s[p2], s[p1] next = '' . join(s) s[p1], s[p2] = s[p2], s[p1] if next not in dist or dist[next] > dist[state] + 1: dist[next] = dist[state] + 1 heappush(q, (dist[next] + f(next), next)) return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.