773. Sliding Puzzle - Detailed Explanation

Problem Statement

You are given a 2 x 3 board which represents a sliding puzzle. The board is represented as a 2D list. The board contains numbers from 0 to 5 where 0 represents the empty space. You can move the empty space by swapping it with one of its neighbors (up, down, left, or right).

Goal:
Rearrange the board to reach the target configuration:

[[1, 2, 3],
 [4, 5, 0]]

Return the minimum number of moves required to reach the target configuration. If it is impossible to solve the puzzle, return -1.

Example 1:

• Input: board = [[1, 2, 3], [4, 0, 5]]
• Output: 1
• Explanation:
  Swap the empty space (0) with 5:
  [[1, 2, 3], [4, 5, 0]]
  The board is solved in 1 move.

Example 2:

• Input: board = [[1, 2, 3], [5, 4, 0]]
• Output: -1
• Explanation:
  There is no sequence of moves that transforms the board into the target configuration.

Example 3:

• Input: board = [[4, 1, 2], [5, 0, 3]]
• Output: 5
• Explanation:
  One possible sequence of moves is:
  1. [[4, 1, 2], [5, 0, 3]]
  2. [[4, 1, 2], [0, 5, 3]] (swap 0 and 5)
  3. [[0, 1, 2], [4, 5, 3]] (swap 0 and 4)
  4. [[1, 0, 2], [4, 5, 3]] (swap 0 and 1)
  5. [[1, 2, 0], [4, 5, 3]] (swap 0 and 2)
  6. [[1, 2, 3], [4, 5, 0]] (swap 0 and 3)

Constraints:

• The board is always a 2x3 grid.
• Each number from 0 to 5 appears exactly once on the board.

Hints to Approach the Problem

1. Think of the board as a state represented by a string.
   You can convert the 2D board into a one-dimensional string (e.g., "123450") which makes it easier to track visited states and swap positions.

2. Use Graph Search Algorithms.
   Consider each state as a node in a graph. A valid move (swapping the empty space with one of its neighbors) is an edge. You want to find the shortest path from the initial state to the target state. This naturally suggests using a Breadth-First Search (BFS).

3. Approaches to Solve the Problem

Approach 1: Breadth-First Search (BFS) – The Brute Force Method

Idea:
Since the board has only 6 cells, the total number of states is limited (at most 6! = 720). We can perform a BFS where:

• State: Represented as a string (e.g., "412503").
• Neighbors: For each state, find all states reachable by swapping the empty space (0) with its adjacent cells.
• Goal: Stop when the state equals "123450".

Step-by-Step:

1. Convert the 2D board to a string.
2. Define a mapping of indices to their neighbor indices. For example:

   • Position 0 can swap with positions 1 and 3.

   • Position 1 can swap with positions 0, 2, and 4.

   • And so on...

3. Use a queue to hold states along with the number of moves taken.
4. Use a set to keep track of visited states.
5. In each iteration, dequeue a state, check if it is the target. If not, generate all valid moves by swapping 0 with its neighbors.
6. If the queue is exhausted and the target is not reached, return -1.

Complexity Analysis:

• Time Complexity: O(6!) = O(720) in the worst-case (which is constant given the fixed size).
• Space Complexity: O(6!) due to the set storing all states.

Approach 2: A* Search (Optimal with Heuristic)

Idea:
Although BFS is sufficient given the small state space, you can also use the A* search algorithm to potentially improve performance using a heuristic. A common heuristic is the Manhattan distance which calculates the sum of the distances of each number from its target position.

Key Points:

• Heuristic: Must be admissible (never overestimate the true cost).
• Priority Queue: Instead of a simple queue, use a priority queue (min-heap) where states with lower estimated total cost (moves so far + heuristic) are processed first.

Step-by-Step:

1. Convert the board into a string.

2. Calculate the Manhattan distance for each state.

3. Use a priority queue to select the state with the lowest estimated cost.

4. Proceed similarly as in BFS, but with the ordering given by the heuristic.

5. This approach is more scalable to larger puzzles (e.g., 3x3 puzzles), though for a 2x3 puzzle, the benefit is marginal.

Complexity Analysis:

• Time Complexity: Depends on the heuristic’s efficiency. In worst-case, it still explores many states, but with a good heuristic, fewer states are processed.
• Space Complexity: Similar to BFS, O(6!).

Code Implementation

Python Code