Abstract / Summary

Move tiles on a 3x3 grid to arrange them in order by sliding one tile at a time.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 75% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Backtracking
• Breadth First Search
• Dynamic Programming
• Matrix
• Memoization

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic 2 × 3 sliding puzzle using a breadth-first search (BFS) over the state space. Each board configuration is encoded as a six-element tuple, where the integer 0 represents the empty slot. The algorithm explores all reachable configurations level by level until it either discovers the target arrangement or exhausts the search space. Because the puzzle contains only six cells, the total number of distinct permutations is limited to 720, which makes a full BFS feasible.

Key Steps

State Representation

The board is flattened into a tuple of six integers. This compact representation enables constant-time hashing and equality checks, which are essential for tracking visited configurations.

a, b, c = board[0]
d, e, f = board[1]
initial_state = (a, b, c, d, e, f)

Initialization

A dictionary named seen records the number of moves required to reach each visited state. The search frontier todo starts with the goal configuration (1, 2, 3, 4, 5, 0), and a step counter steps is set to zero.

seen  = {}
todo  = [(1, 2, 3, 4, 5, 0)]
steps = 0

BFS Loop

The outer while loop continues until there are no more states to explore. For each iteration, a new list next collects the successors of the current frontier. The inner for loop processes each state in todo.

while todo:
    next = []
    for key in todo:
        # processing of each state
    steps += 1
    todo = next

Duplicate Detection

Before expanding a state, the algorithm checks whether it has already been recorded in seen. If the state is present, the loop skips further processing, preventing redundant work.

if key in seen:
    continue
seen[key] = steps

Generating Successor States

The core of the algorithm enumerates possible moves based on the position of the empty slot (value 0). For each possible location of 0, the code appends the resulting board configurations to next. The explicit conditional blocks cover all six positions and list the legal swaps.

a, b, c, d, e, f = key
if a == 0:
    next.append((d, b, c, a, e, f))
    next.append((b, a, c, d, e, f))
if b == 0:
    next.append((b, a, c, d, e, f))
    next.append((a, c, b, d, e, f))
    next.append((a, e, c, d, b, f))
if c == 0:
    next.append((a, b, f, d, e, c))
    next.append((a, c, b, d, e, f))
if d == 0:
    next.append((d, b, c, a, e, f))
    next.append((a, b, c, e, d, f))
if e == 0:
    next.append((a, b, c, e, d, f))
    next.append((a, b, c, d, f, e))
    next.append((a, e, c, d, b, f))
if f == 0:
    next.append((a, b, f, d, e, c))
    next.append((a, b, c, d, f, e))

Termination and Result Retrieval

After the BFS completes, the algorithm looks up the number of steps required to reach the initial board configuration. If the configuration was never visited, -1 is returned to indicate impossibility.

return seen.get(initial_state, -1)

Edge Cases Handled

The implementation implicitly handles several edge conditions:

• Already Solved Puzzle - When the input board matches the goal state, the initial lookup in seen yields a step count of zero because the goal configuration is inserted into todo before any expansion.
• Unsolvable Configurations - The BFS explores the entire reachable state space. If a configuration cannot be transformed into the goal, it never appears in seen, and the final get call returns -1.
• Multiple Paths to the Same State - The seen dictionary ensures that once a state is recorded, any later encounter of the same configuration is ignored, preventing infinite loops and redundant processing.
• All Possible Moves from Each Position - The conditional blocks enumerate every legal slide for each location of the empty slot, guaranteeing that no valid transition is omitted.

Performance Optimizations

Several design choices contribute to efficient execution:

• Tuple-Based State Encoding - Using immutable tuples as keys enables fast dictionary operations and avoids the overhead of converting mutable structures for hashing.
• Early Duplicate Filtering - By checking seen before generating successors, the algorithm avoids unnecessary expansion of already visited states, reducing the number of generated tuples.
• Level-Order Expansion - Incrementing steps only after processing the entire current frontier ensures that the first time a state is recorded corresponds to the minimal number of moves, eliminating the need for additional distance calculations.
• Compact Successor Generation - The explicit if blocks directly construct new tuples without intermediate list or array allocations, minimizing memory churn during the BFS.
• Limited Search Space - The problem’s combinatorial bound (720 permutations) allows the algorithm to keep the entire frontier and visited set in memory without resorting to external storage or pruning heuristics. This bounded nature makes the straightforward BFS both simple and performant.

Imagine a puzzle board with little number tiles that can only slide into an empty space. This code acts like a very smart thinker trying to solve that puzzle by exploring every possible way the tiles can be arranged.

First, the code creates a list called todo which holds the goal arrangement of the tiles. Then, it creates a way to keep track of every board position it has already looked at so it does not get confused by checking the same one twice. It looks at the empty space, which is represented by a zero, and imagines all the different neighboring tiles that could slide into that spot. For every slide, it creates a new arrangement of numbers and adds it to the list to explore later.

As the code finds these new arrangements, it counts how many moves it took to get there. It keeps doing this over and over, slowly uncovering every possible way the board can look until it has a complete map of all the ways the puzzle can be solved. Finally, the code takes the board you gave it and checks the map it built to see if there is a known path to the goal.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		TS			Python
	WalkCCC	C++		Java
	leetcode.ca	C++		Java					Python
	LeetcodeHelp	C++		Java					Python
	Progiez	C++		Java					Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fengvyi	C++
	gouthampradhan			Java
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007								Python
	luangong					TS
	martianoff						Scala
	ruoru							Rust
	Shamik07									Dart
	suxrobGM				C#
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
luangong	TypeScript
martianoff	Scala
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality