Here, We see Sliding Puzzle LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Sliding Puzzle LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Sliding Puzzle LeetCode Solution
Table of Contents
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:
![slide1 grid](https://i0.wp.com/assets.leetcode.com/uploads/2021/06/29/slide1-grid.jpg?w=1400&ssl=1)
Input: board = [[1,2,3],[4,0,5]] Output: 1 Explanation: Swap the 0 and the 5 in one move.
Example 2:
![slide2 grid](https://i0.wp.com/assets.leetcode.com/uploads/2021/06/29/slide2-grid.jpg?w=1400&ssl=1)
Input: board = [[1,2,3],[5,4,0]] Output: -1 Explanation: No number of moves will make the board solved.
Example 3:
![slide3 grid](https://i0.wp.com/assets.leetcode.com/uploads/2021/06/29/slide3-grid.jpg?w=1400&ssl=1)
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]]
Sliding Puzzle LeetCode Solution C++
class Solution {
public:
string target = "123450";
vector<vector<int>> dir{{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};
int slidingPuzzle(vector<vector<int>>& board)
{
int m = board.size(),n = board[0].size();
string first = "";
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
first += to_string(board[i][j]);
}
}
queue<pair<string,int>> q;
unordered_set<string> visited;
q.push({first,0});
visited.insert(first);
while(!q.empty())
{
int sz = q.size();
while(sz--)
{
auto cur = q.front();
q.pop();
string s = cur.first;
int count = cur.second;
if(s == target)
{
return count;
}
int indx = s.find('0');
for(auto &x: dir[indx])
{
string temp = s;
swap(temp[x],temp[indx]);
if(!visited.count(temp))
{
visited.insert(temp);
q.push({temp,count+1});
}
}
}
}
return -1;
}
};
Code language: PHP (php)
Sliding Puzzle LeetCode Solution Java
class Solution {
int min = Integer.MAX_VALUE;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int slidingPuzzle(int[][] board) {
int[] zero = {-1, -1};
outer:
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == 0) {
zero = new int[]{i, j};
break outer;
}
}
}
helper_backtrack(board, 0, new int[]{-1, -1}, zero);
return min == Integer.MAX_VALUE ? -1 : min;
}
public void helper_backtrack(int[][] board, int moves, int[] last, int[] curr) {
if (moves >= 20) return;
if (helper_isDone(board)) {
min = Math.min(min, moves);
return;
}
for (int[] dir : dirs) {
int i = curr[0] + dir[0];
int j = curr[1] + dir[1];
if (i < 0 || i >= 2 || j < 0 || j >= 3 || (last[0] == i && last[1] == j)) continue;
int[] newMove = {i, j};
helper_flip(board, curr, newMove);
helper_backtrack(board, moves + 1, curr, newMove);
helper_flip(board, curr, newMove);
}
}
public void helper_flip(int[][] board, int[] f, int[] s) {
int temp = board[f[0]][f[1]];
board[f[0]][f[1]] = board[s[0]][s[1]];
board[s[0]][s[1]] = temp;
}
public boolean helper_isDone(int[][] board) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
if (i == 1 && j == 2) return true;
if (board[i][j] != 3 * i + j + 1) return false;
}
}
return true;
}
}
Code language: PHP (php)
Sliding Puzzle LeetCode Solution JavaScript
var slidingPuzzle = function (board) {
const mapping = {0: [1, 3],1: [0, 2, 4], 2: [1, 5],3: [0, 4], 4: [1, 3, 5],5: [2, 4]
}
function swap(state, pos, next) {
let array = state.split('');
[array[pos], array[next]] = [array[next], array[pos]];
return array.join('');
}
let state = '';
board.forEach(row => state += row.join(''));
let visited = new Set(state);
let q = [[state, state.indexOf('0'), 0]];
while (q.length) {
let [state, pos, moves] = q.shift();
if (state == '123450')
return moves;
for (let next of mapping[pos]) {
let newState = swap(state, pos, next);
if (visited.has(newState))
continue;
visited.add(newState);
q.push([newState, next, moves + 1])
}
}
return -1;
};
Code language: JavaScript (javascript)
Sliding Puzzle LeetCode Solution Python
class Solution(object):
def slidingPuzzle(self, board):
src = ""
zero = 0
for i in range(len(board)):
for j in range(len(board[i])):
src += str(board[i][j])
if board[i][j] == 0:
zero = len(src)-1
target = "123450"
step = {0:[1, 3], 1:[0, 2, 4], 2:[ 1, 5], 3:[0, 4], 4:[3, 1, 5], 5:[4, 2]}
q = collections.deque()
q.append((src, 0, zero))
visit = set()
visit.add(src)
while q:
for _ in range(len(q)):
arr, count, pos = q.popleft()
if arr == target:
return count
for adj_index in step[pos]:
n_arr = list(arr)
n_arr[pos], n_arr[adj_index] = n_arr[adj_index], n_arr[pos]
n_arr = "".join(n_arr)
if n_arr not in visit:
visit.add(n_arr)
q.append(( n_arr, count+1, adj_index))
return -1