Problem
Sliding Puzzle
On a 2x3 board, there are 5 tiles represented by the integers 1 through 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 a puzzle 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.
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]]
Solution
Let's observe the changing process, the problem is a bfs problem. The adjacency list is given by the neighbor states that can reach in one step. We can iterate the indexes, for each 2-D index, we exchange the value with the right and the bottom if there are any.
4 1 2 4 1 2 0 1 2 1 0 2 1 2 0 1 2 3
5 0 3 0 5 3 4 5 3 4 5 3 4 5 3 4 5 0
bfs all adjacency state until reach
1 2 3
4 5 0
given the adjacency list is: for each element, change with right/below
4 1 2 1 4 2 5 1 2 4 2 1 4 0 2 4 1 3 4 1 2 4 1 2
5 0 3 5 0 3 4 0 3 5 0 3 5 1 3 5 0 2 0 5 3 5 3 0
import java.util.*;
class SlidingPuzzle {
public static int solve(int[][] start, int[][] end) {
Set<Node> visited = new HashSet<>();
Queue<Node> queue = new ArrayDeque<>();
Map<Node, Node> path = new HashMap<>();
Node source = new Node(start, 0);
Node target = new Node(end, 0);
queue.add(source);
visited.add(source);
while(!queue.isEmpty()) {
Node w = queue.poll();
for(Node v : w.adj()) {
if(!visited.contains(v)) {
queue.add(v);
visited.add(v);
path.put(v, w);
if(v.equals(target)) {
printPath(path, source, target);
return v.distance;
}
}
}
}
return -1;
}
private static void printPath(Map<Node, Node> path, Node source, Node target) {
Node x = target;
for(x = target; !x.equals(source); x = path.get(x)) {
System.out.println("========" + x.distance + "=======");
System.out.println(Arrays.deepToString(x.board));
}
}
public static void main(String...args) {
int[][] start = new int[][] {
{4,1,2},{5,0,3}
};
int[][] end = new int[][] {
{1,2,3},{4,5,0}
};
System.out.println(solve(start, end));
}
private static class Node {
public int[][] board = new int[2][3];
public int distance = 0;
int N = board.length;
int M = board[0].length;
public Node(int[][] board, int distance) {
this.board = board;
this.distance = distance;
}
@Override
public boolean equals(Object other) {
if(other == null) return false;
if(!(other instanceof Node)) return false;
return hashCode() == ((Node)other).hashCode();
}
@Override
public int hashCode() {
return Arrays.deepToString(board).hashCode();
}
public List<Node> adj() {
List<Node> list = new ArrayList<>();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(i + 1 < N) {
int[][] newBoard = copy();
int t = newBoard[i][j];
newBoard[i][j] = newBoard[i+1][j];
newBoard[i+1][j]=t;
list.add(new Node(newBoard, distance+1));
}
if(j + 1 < M) {
int[][] newBoard = copy();
int t = newBoard[i][j];
newBoard[i][j] = newBoard[i][j+1];
newBoard[i][j+1] = t;
list.add(new Node(newBoard, distance+1));
}
}
}
return list;
}
private int[][] copy() {
int[][] newBoard = new int[N][M];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
newBoard[i][j] = board[i][j];
}
}
return newBoard;
}
}
}
class SlidingPuzzle {
public static int solve(int[][] start, int[][] end) {
Set<Node> visited = new HashSet<>();
Queue<Node> queue = new ArrayDeque<>();
Map<Node, Node> path = new HashMap<>();
Node source = new Node(start, 0);
Node target = new Node(end, 0);
queue.add(source);
visited.add(source);
while(!queue.isEmpty()) {
Node w = queue.poll();
for(Node v : w.adj()) {
if(!visited.contains(v)) {
queue.add(v);
visited.add(v);
path.put(v, w);
if(v.equals(target)) {
printPath(path, source, target);
return v.distance;
}
}
}
}
return -1;
}
private static void printPath(Map<Node, Node> path, Node source, Node target) {
Node x = target;
for(x = target; !x.equals(source); x = path.get(x)) {
System.out.println("========" + x.distance + "=======");
System.out.println(Arrays.deepToString(x.board));
}
}
public static void main(String...args) {
int[][] start = new int[][] {
{4,1,2},{5,0,3}
};
int[][] end = new int[][] {
{1,2,3},{4,5,0}
};
System.out.println(solve(start, end));
}
private static class Node {
public int[][] board = new int[2][3];
public int distance = 0;
int N = board.length;
int M = board[0].length;
public Node(int[][] board, int distance) {
this.board = board;
this.distance = distance;
}
@Override
public boolean equals(Object other) {
if(other == null) return false;
if(!(other instanceof Node)) return false;
return hashCode() == ((Node)other).hashCode();
}
@Override
public int hashCode() {
return Arrays.deepToString(board).hashCode();
}
public List<Node> adj() {
List<Node> list = new ArrayList<>();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(i + 1 < N) {
int[][] newBoard = copy();
int t = newBoard[i][j];
newBoard[i][j] = newBoard[i+1][j];
newBoard[i+1][j]=t;
list.add(new Node(newBoard, distance+1));
}
if(j + 1 < M) {
int[][] newBoard = copy();
int t = newBoard[i][j];
newBoard[i][j] = newBoard[i][j+1];
newBoard[i][j+1] = t;
list.add(new Node(newBoard, distance+1));
}
}
}
return list;
}
private int[][] copy() {
int[][] newBoard = new int[N][M];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
newBoard[i][j] = board[i][j];
}
}
return newBoard;
}
}
}
For bfs, the time cost and space cost are O(V + E). There are 6! board states, so V = 6! Each node has 6 neighbors. The time cost and space cost are O(row x column x (row x column)!).
