Sliding Puzzle Problem

Problem Description

You are given a 2x3 sliding puzzle grid. The goal is to move the tiles to match the target state "123450" (where 0 represents the blank space). You can only move tiles adjacent to the blank space into the blank space. The task is to find the minimum number of moves to reach the target state or return -1 if it is impossible.

Code Explanation

1. Initialization

String target = "123450";
String start = "";

• The target string represents the goal configuration of the puzzle.
• The start string is constructed by concatenating the given 2D array board into a single string. This makes it easier to manipulate states in the BFS algorithm.

2. Create Adjacency List for Moves

int[][] dirs = new int[][] { 
    { 1, 3 }, 
    { 0, 2, 4 }, 
    { 1, 5 }, 
    { 0, 4 }, 
    { 1, 3, 5 }, 
    { 2, 4 } 
};

• Each index of the string (representing the board) corresponds to a possible position of the blank (0).
• dirs[i] contains the indices that the blank space (0) can swap with for the corresponding position i.

3. BFS Setup

Queue<String> queue = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
int res = 0;

• A queue is used for BFS to explore all possible states level by level.
• A HashSet visited is used to track states that have already been processed to avoid redundant calculations.
• res keeps track of the number of moves taken so far.

4. BFS Loop

while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        String cur = queue.poll();
        if (cur.equals(target)) {
            return res;
        }

• The BFS explores all possible states level by level.
• The size variable ensures that each level of moves is processed in one iteration.
• If the current state cur matches the target, the function returns res (the number of moves).

5. Generate Next States

int zero = cur.indexOf('0');
for (int dir : dirs[zero]) {
    String next = swap(cur, zero, dir);
    if (visited.contains(next)) {
        continue;
    }
    visited.add(next);
    queue.offer(next);
}

• Find the index of the blank space (0) in the current state (cur).
• Use the adjacency list dirs to determine possible swaps.
• For each valid swap, generate the new state next and:
  • Skip if it is already visited.
  • Otherwise, mark it as visited and add it to the BFS queue.

6. Swap Helper Function

private String swap(String str, int i, int j) {
    StringBuilder sb = new StringBuilder(str);
    sb.setCharAt(i, str.charAt(j));
    sb.setCharAt(j, str.charAt(i));
    return sb.toString();
}

• This function swaps the characters at indices i and j in the string to create a new board state.

7. Return the Result

return -1;

• If the queue is empty and no solution is found, return -1 to indicate that it is impossible to reach the target state.

Key Concepts

1. String Representation: The board is converted into a string to simplify state manipulation.
2. Breadth-First Search (BFS): This ensures the minimum number of moves is found because BFS explores all states at the current depth before moving deeper.
3. Visited Set: Tracks already-explored states to prevent infinite loops.

Test Cases

Example 1

Input:

int[][] board = {
    {1, 2, 3},
    {4, 0, 5}
};

Output:

1

Explanation: Swap 0 and 5 to achieve the target state.

Example 2

Input:

int[][] board = {
    {1, 2, 3},
    {5, 4, 0}
};

Output:

-1

Explanation: It is impossible to reach the target state from this configuration.

Example 3

Input:

int[][] board = {
    {4, 1, 2},
    {5, 0, 3}
};

Output:

5

Explanation: Requires 5 moves to achieve the target state.

Example 4

Input:

int[][] board = {
    {1, 2, 3},
    {0, 4, 5}
};

Output:

2

Explanation: Swap 0 with 4 and then with 5 to reach the target.

Edge Cases

1. Already Solved: Input:

   javaCopy

   int[][] board = {
       {1, 2, 3},
       {4, 5, 0}
   };
   

   Output:

   javaCopy

   0
   

   Explanation: The board is already in the target state.

2. Unsolvable Puzzle: Input:

   javaCopy

   int[][] board = {
       {3, 2, 1},
       {4, 5, 0}
   };
   

   Output:

   javaCopy

   -1
   

   Explanation: The puzzle configuration cannot be solved.