The Sliding Puzzle problem presents you with a 2x3 board containing the numbers 0 through 5, where 0 represents the empty space. The board is given as a 2D list board. You can move the empty space by swapping it with one of its adjacent (up, down, left, or right) tiles.
The goal is to transform the board into the target configuration [[1,2,3],[4,5,0]] by making the minimal number of moves. If it is impossible to reach the target, return -1.
0) with a neighboring tile.0 to 5 are present exactly once.-1 if unsolvable.At first glance, the problem seems to invite a brute-force solution: try every possible sequence of moves until you reach the target board. However, with 6 tiles, there are 720 possible arrangements, and many of them could be revisited. This quickly becomes inefficient as the number of moves increases.
To solve this efficiently, we need a way to systematically explore possible board states without repeating ourselves, and always find the shortest path to the solution. This is a classic scenario for Breadth-First Search (BFS)—an algorithm that explores all possibilities level by level, guaranteeing the shortest solution if one exists.
By representing each board state as a unique string and tracking visited states, we can avoid cycles and unnecessary work. The BFS queue will let us process all possible states in increasing order of move count.
We use Breadth-First Search (BFS) to explore all possible board configurations starting from the initial state. Here's how the approach works:
"123450"). This makes it easy to compare and store board states.
"123450".
0 with its neighbors efficiently.
0 and generate all possible states by swapping with each neighbor.We use a hash set for visited states because lookups and insertions are O(1), keeping our solution efficient.
Suppose the input is board = [[1,2,3],[4,0,5]].
"123405". The target is "123450".
0 is index 4 (second row, second column).
"103425""123045""123450" (target!)"123450". So, the answer is 1.
BFS ensures that if a shorter solution exists, it will be found before longer paths are explored.
Brute-force approach: Would examine all 720 possible board configurations, with potentially exponential time complexity as it explores all move sequences.
BFS approach:
This is efficient for the 2x3 board, and BFS guarantees the shortest path.
The Sliding Puzzle problem is a classic application of Breadth-First Search for finding the shortest transformation sequence in a finite state space. By encoding the board as a string, using a queue for BFS, and tracking visited states with a set, we efficiently avoid cycles and ensure the shortest solution is found. This approach is both elegant and practical for small puzzles, and highlights the power of systematic state exploration in algorithm design.
from collections import deque
class Solution:
def slidingPuzzle(self, board):
start = ''.join(str(num) for row in board for num in row)
target = '123450'
neighbors = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4],
4: [1, 3, 5],
5: [2, 4]
}
queue = deque()
queue.append((start, 0))
visited = set()
visited.add(start)
while queue:
state, moves = queue.popleft()
if state == target:
return moves
zero = state.index('0')
for nei in neighbors[zero]:
lst = list(state)
lst[zero], lst[nei] = lst[nei], lst[zero]
new_state = ''.join(lst)
if new_state not in visited:
visited.add(new_state)
queue.append((new_state, moves + 1))
return -1
#include <vector>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;
class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
string start, target = "123450";
for (auto& row : board)
for (int num : row)
start += to_string(num);
vector<vector<int>> neighbors = {
{1,3}, {0,2,4}, {1,5},
{0,4}, {1,3,5}, {2,4}
};
queue<pair<string, int>> q;
q.push({start, 0});
unordered_set<string> visited;
visited.insert(start);
while (!q.empty()) {
auto [state, moves] = q.front(); q.pop();
if (state == target) return moves;
int zero = state.find('0');
for (int nei : neighbors[zero]) {
string next = state;
swap(next[zero], next[nei]);
if (!visited.count(next)) {
visited.insert(next);
q.push({next, moves+1});
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int slidingPuzzle(int[][] board) {
StringBuilder sb = new StringBuilder();
for (int[] row : board) {
for (int n : row) sb.append(n);
}
String start = sb.toString();
String target = "123450";
int[][] neighbors = {
{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 moves = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
String state = queue.poll();
if (state.equals(target)) return moves;
int zero = state.indexOf('0');
for (int nei : neighbors[zero]) {
char[] arr = state.toCharArray();
char tmp = arr[zero];
arr[zero] = arr[nei];
arr[nei] = tmp;
String next = new String(arr);
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
moves++;
}
return -1;
}
}
/**
* @param {number[][]} board
* @return {number}
*/
var slidingPuzzle = function(board) {
const start = board.flat().join('');
const target = "123450";
const neighbors = [
[1,3], [0,2,4], [1,5],
[0,4], [1,3,5], [2,4]
];
const queue = [[start, 0]];
const visited = new Set([start]);
while (queue.length) {
const [state, moves] = queue.shift();
if (state === target) return moves;
const zero = state.indexOf('0');
for (let nei of neighbors[zero]) {
const arr = state.split('');
[arr[zero], arr[nei]] = [arr[nei], arr[zero]];
const next = arr.join('');
if (!visited.has(next)) {
visited.add(next);
queue.push([next, moves+1]);
}
}
}
return -1;
};