Skip to main content
Talentd

Sliding Puzzle - Solution & Explanation

HardArrayDynamic ProgrammingBacktrackingBreadth-First Search11 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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 == 2
  • board[i].length == 3
  • 0 <= board[i][j] <= 5
  • Each value board[i][j] is unique.

Approach Overview

Problem Overview: You are given a 2x3 board containing numbers 1–5 and an empty tile represented by 0. Each move swaps the empty tile with one of its adjacent tiles. The task is to determine the minimum number of moves required to reach the target configuration [[1,2,3],[4,5,0]]. If the configuration cannot reach the goal state, return -1.

Approach 1: Breadth-First Search (BFS) (Time: O((m*n)!), Space: O((m*n)!))

This puzzle naturally forms a graph where each board configuration is a node and each valid tile swap is an edge. Breadth-First Search works well because every move has equal cost, and BFS guarantees the shortest path to the goal. Convert the board into a string such as "123450" so configurations can be stored in a hash set for fast visited checks. For every state, locate the index of 0, generate neighbors by swapping it with valid adjacent indices, and push unseen states into the queue. Since the puzzle has at most 6! = 720 states, BFS quickly explores all reachable configurations. This approach is straightforward and reliable for interview settings.

The board itself can be treated like a flattened array, and adjacency rules define which indices the blank tile can swap with. Using a visited set prevents revisiting states and avoids exponential blow‑up.

Approach 2: A* Search Algorithm (Time: O(b^d) worst case, typically faster; Space: O(b^d))

A* search improves exploration efficiency by prioritizing states closer to the goal. Each state is assigned a score f(n) = g(n) + h(n), where g(n) is the number of moves taken so far and h(n) is a heuristic estimating remaining distance. A common heuristic for sliding puzzles is the Manhattan distance between each tile’s current and target positions in the matrix. The algorithm stores states in a priority queue ordered by the smallest estimated total cost.

When expanding nodes, generate neighboring configurations the same way as BFS by swapping the blank tile. The heuristic guides the search toward promising states instead of exploring blindly. For larger sliding puzzles (like 8‑puzzle or 15‑puzzle), A* dramatically reduces the number of explored states compared to BFS. Even for the 2x3 variant, it demonstrates how heuristic search works in pathfinding problems.

Recommended for interviews: BFS is usually the expected solution because it clearly models the puzzle as an unweighted graph and guarantees the minimum number of moves. Implementing BFS with a queue and visited set demonstrates solid understanding of state‑space traversal. A* is a strong follow‑up optimization that shows deeper knowledge of heuristic search and algorithm design.

Approach 1: Breadth-First Search (BFS) Approach

The BFS approach performs a level-order traversal beginning from the initial board state, ensuring that the shortest path is found. Each state is enqueued with its move count, and dequeue states expand via possible '0' swaps. Unvisited states are tracked for efficiency.

This 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.

Code

PythonC#

Python

C#

Complexity

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.

Try this approach in the editor →

Approach 2: A* Search Algorithm

Utilizing A* search, the algorithm proceeds by maintaining a priority queue based on potential shortest paths (current state cost plus heuristic estimate). The heuristic here is the Manhattan distance, guiding exploration toward the goal efficiently.

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.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O((6! = 720) log(720))
Space Complexity: O(720), based on the number of states handled.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) Approach

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.

A* Search Algorithm

Time Complexity: O((6! = 720) log(720))
Space Complexity: O(720), based on the number of states handled.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS)O((m*n)!) ≈ O(720) for 2x3 boardO((m*n)!)Best general solution for shortest path in an unweighted puzzle state graph
A* Search AlgorithmO(b^d) worst case, typically faster with heuristicO(b^d)When heuristic guidance (like Manhattan distance) can reduce explored states

Video Solution

Sliding Puzzle - Leetcode 773 - Python • NeetCodeIO • 13,451 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sliding Puzzle easy or hard?
Sliding Puzzle is classified as a Hard problem because it requires modeling the board as a graph and implementing efficient state exploration. The difficulty comes from generating valid neighbors, avoiding repeated states, and recognizing BFS or A* as the correct approach.
Sliding Puzzle Python/Java solution
Python solutions commonly implement BFS using collections.deque and a set for visited states. Java implementations use Queue with HashSet for visited tracking, while A* variants use PriorityQueue. The algorithm logic is identical: generate neighbor states by swapping the zero tile and search until the target configuration appears.
How to solve Sliding Puzzle in O(n)?
Sliding Puzzle cannot generally be solved in strict O(n) time because it requires exploring permutations of board states. The optimal approach is BFS or A* search that explores the state graph efficiently. For the 2x3 puzzle, BFS effectively runs in constant time since there are only 720 possible configurations.
What is the best approach for Sliding Puzzle?
Breadth-First Search (BFS) is the most common approach because the puzzle can be modeled as an unweighted graph of board states. BFS explores configurations level by level, guaranteeing the minimum number of moves to reach the target state. For a 2x3 board the total number of states is only 720, making BFS efficient and easy to implement.
Is Sliding Puzzle asked at Google/Amazon/Meta?
Sliding puzzle style problems appear in interviews at companies like Google, Amazon, and Meta when testing graph traversal and state-space search. Interviewers use it to evaluate BFS, hashing for visited states, and understanding of shortest path problems in implicit graphs.
What data structure is used in Sliding Puzzle?
The typical solution uses a queue for BFS traversal and a hash set to track visited board configurations. The board is usually converted into a string representation like "123450" so it can be stored and compared efficiently. A* solutions additionally use a priority queue (min-heap).
What is the time complexity of Sliding Puzzle?
The BFS solution has time complexity O((m*n)!) because every board permutation may be explored in the worst case. For the 2x3 puzzle used in LeetCode 773, this is at most 6! = 720 states, so the search is effectively constant time. Space complexity is also O((m*n)!) due to the queue and visited set.

Ready to solve this problem?

Practice Sliding Puzzle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays