Algorithm
Problem Name: 773. Sliding Puzzle
Problem Link: https://leetcode.com/problems/sliding-puzzle/
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.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
unordered_set < string>visited;
vector<vector<int>>dst({{1,2,3}, {4,5,0}});
string target = toString(dst);
int level = 0;
queue < vector<vector<int>>>cur, next;
cur.push(board);
while(!cur.empty()) {
auto node = cur.front();
cur.pop();
string s = toString(node);
if (s == target) {
return level;
}
visited.insert(s);
auto nextStates = nextState(node);
for (auto v: nextStates) {
string t = toString(v);
if (!visited.count(t)) {
next.push(v);
}
}
if (cur.empty()) {
++level;
swap(cur, next);
}
}
return -1;
}
vector < vector<vector<int>>> nextState(vector < vector<int>>& board) {
vector < vector<vector<int>>>res;
auto pos = findZero(board);
int r = pos[0];
int c = pos[1];
int left = c - 1;
int right = c + 1;
int up = r - 1;
int down = r + 1;
if (left >= 0) {
swap(board[r][left], board[r][c]);
res.push_back(board);
swap(board[r][left], board[r][c]);
}
if (right < 3) {
swap(board[r][right], board[r][c]);
res.push_back(board);
swap(board[r][right], board[r][c]);
}
if (up >= 0) {
swap(board[up][c], board[r][c]);
res.push_back(board);
swap(board[up][c], board[r][c]);
}
if (down < 2) {
swap(board[down][c], board[r][c]);
res.push_back(board);
swap(board[down][c], board[r][c]);
}
return res;
}
vector<int> findZero(vector < vector<int>>& board) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 3; ++j) {
if (board[i][j] == 0) {
return {i, j};
}
}
}
}
string toString(vector < vector<int>>& v) {
string s;
for (auto x: v) {
for (auto y: x) {
s += to_string(y) + ",";
}
}
return s;
}
};
Input
board = [[1,2,3],[4,0,5]]
Output
1
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const slidingPuzzle = function(board) {
const target = "123450";
let start = "";
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
start += board[i][j];
}
}
const visited = {};
// all the positions 0 can be swapped to
const dirs = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
const queue = [];
queue.push(start);
visited[start] = true;
let res = 0;
while (queue.length !== 0) {
// level count, has to use size control here, otherwise not needed
let size = queue.length;
for (let i = 0; i < size; i++) {
let cur = queue.shift();
if (cur === target) {
return res;
}
let zero = cur.indexOf("0");
// swap if possible
for (let dir of dirs[zero]) {
let next = swap(cur, zero, dir);
if (visited.hasOwnProperty(next)) {
continue;
}
visited[next] = true;
queue.push(next);
}
}
res++;
}
return -1;
};
function swap(str, i, j) {
const arr = str.split("");
const ic = str[i];
const jc = str[j];
arr.splice(i, 1, jc);
arr.splice(j, 1, ic);
return arr.join("");
}
Input
board = [[1,2,3],[4,0,5]]
Output
1
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def slidingPuzzle(self, board):
moves, used, cnt = {0: {1, 3}, 1:{0, 2, 4}, 2:{1, 5}, 3:{0, 4}, 4:{1, 3, 5}, 5:{2, 4}}, set(), 0
s = "".join(str(c) for row in board for c in row)
q = [(s, s.index("0"))]
while q:
new = []
for s, i in q:
used.add(s)
if s == "123450":
return cnt
arr = [c for c in s]
for move in moves[i]:
new_arr = arr[:]
new_arr[i], new_arr[move] = new_arr[move], new_arr[i]
new_s = "".join(new_arr)
if new_s not in used:
new.append((new_s, move))
cnt += 1
q = new
return -1
Input
board = [[1,2,3],[5,4,0]]
Output
-1
#4 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0773_SlidingPuzzle
{
private (int dr, int dc)[] direction = new (int dr, int dc)[4] { (1, 0), (-1, 0), (0, 1), (0, -1) };
public int SlidingPuzzle(int[][] board)
{
State final = new State(new int[2][]
{
new int[] { 1, 2, 3 },
new int[] { 4, 5, 0 },
});
State initState = new State(board);
Queue < State> queue = new Queue();
ISet visited = new HashSet();
queue.Enqueue(initState);
visited.Add(initState);
int count = 0;
while (queue.Count > 0)
{
int size = queue.Count;
for (int i = 0; i < size; i++)
{
var curr = queue.Dequeue();
if (curr.Equals(final)) return count;
foreach (var dir in direction)
{
var next = curr.Move(dir);
if (next != null && visited.Add(next))
{
queue.Enqueue(next);
}
}
}
count++;
}
return -1;
}
private class State : IEquatable < State>
{
private readonly int[][] _board;
public State(int[][] board)
{
_board = board;
}
public override bool Equals(object obj) => Equals(obj as State);
public override int GetHashCode()
{
unchecked
{
int res = 0;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 3; j++)
{
res *= 10;
res += _board[i][j];
}
return res.GetHashCode();
}
}
public bool Equals(State other)
{
for (int i = 0; i < 2; i++)
for (int j = 0; j < 3; j++)
if (_board[i][j] != other._board[i][j])
return false;
return true;
}
private State Clone()
{
int[][] newBoard = new int[2][];
for (int i = 0; i < 2; i++)
{
newBoard[i] = new int[3];
for (int j = 0; j < 3; j++)
newBoard[i][j] = _board[i][j];
}
return new State(newBoard);
}
public State Move((int dr, int dc) dir)
{
for (int i = 0; i < 2; i++)
for (int j = 0; j < 3; j++)
if (_board[i][j] == 0)
{
int newI = i + dir.dr;
int newJ = j + dir.dc;
if (newI >= 0 && newI < 2 && newJ >= 0 && newJ < 3)
{
var tmp = _board[i][j];
_board[i][j] = _board[newI][newJ];
_board[newI][newJ] = tmp;
State res = Clone();
tmp = _board[i][j];
_board[i][j] = _board[newI][newJ];
_board[newI][newJ] = tmp;
return res;
}
return null;
}
return null;
}
}
}
}
Input
board = [[1,2,3],[5,4,0]]
Output
-1