{x}
blog image

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 == 2
  • board[i].length == 3
  • 0 <= board[i][j] <= 5
  • Each value board[i][j] is unique.

Solution Explanation for Sliding Puzzle

This problem asks for the minimum number of moves to solve a sliding puzzle. The puzzle consists of a 2x3 board with tiles numbered 1-5 and a blank space (0). We can swap the blank space with an adjacent tile. The goal is to arrange the tiles in the order [[1,2,3],[4,5,0]].

The optimal solution uses a combination of Breadth-First Search (BFS) and state representation to efficiently explore the search space.

Approach:

  1. State Representation: We represent each board state as a string. This allows us to easily check for visited states and use a set (or unordered_set in C++) for efficient lookup. The string is created by concatenating the board elements row-by-row. For example, [[1,2,3],[4,0,5]] becomes "123405".

  2. Breadth-First Search (BFS): BFS is used to explore the possible board states. Starting from the initial state, we explore all reachable states level by level. The level represents the number of moves. This guarantees that the first time we reach the solved state, it will be the shortest path.

  3. Finding Neighbors: For each board state, we need to find its neighboring states (states reachable by a single move). This involves locating the '0' (blank space), and then checking the four adjacent positions. If an adjacent position is within the board bounds, we swap the '0' with the tile in that position to generate a new state.

  4. Visited States: A set (vis in the code) is used to keep track of visited states. This prevents cycles and ensures that we don't explore the same state multiple times.

  5. Queue: A queue (q in the code) is used in BFS to store the states to be explored. We add the initial state to the queue and repeatedly dequeue states, generating and enqueueing their neighbors until we find the solved state.

Time Complexity Analysis:

  • In the worst-case scenario, we might have to explore all possible states of the puzzle. The number of possible arrangements of 6 elements is 6! = 720. However, not all arrangements are reachable from a given starting state due to parity constraints (the number of inversions must have the same parity for the starting and goal states). In practice, the number of reachable states will be significantly less than 720.
  • BFS explores each reachable state once. Therefore, the time complexity is approximately O(B), where B is the number of reachable states. B is bounded by 6! = 720 but could be much smaller in practice.

Space Complexity Analysis:

  • The space complexity is dominated by the vis set (or unordered_set), which stores visited states. In the worst case, it can store up to the number of reachable states B.
  • The queue also stores states, but its size is at most B as well.
  • So, the space complexity is O(B).

Code Explanation (Python):

The Python code implements the described algorithm. Functions gets() and setb() convert between the board representation and the string representation. f() finds the neighbors of a given state. The main part of the code performs BFS, keeping track of visited states and the number of moves. If the solved state is not found, it returns -1.

Code Explanation (Java and C++):

The Java and C++ codes follow the same logic as the Python code, with appropriate data structure usage for each language. The core algorithm of BFS, state representation, and neighbor generation remains the same. The main differences are in syntax and data structure specifics (e.g., Deque in Java, queue in C++, unordered_set in C++).

Solution 2 (A Search with Heuristic):*

Solution 2 uses A* search, which is a more informed search algorithm than BFS. It uses a heuristic function f(s) to estimate the distance to the goal state. This heuristic is the sum of Manhattan distances of each tile from its target position. This helps to prioritize states that are closer to the solution. The use of a priority queue (heapq in Python, PriorityQueue in Java) ensures that states with lower f(s) are explored first. This often reduces the number of states explored, leading to improved performance, although the time complexity remains exponential in the worst case. The time complexity is O(B log B) where B is the number of explored states, due to the use of a priority queue. Space complexity remains O(B).

In summary, both solutions tackle the Sliding Puzzle problem using graph search techniques, but Solution 2 provides a more efficient approach by incorporating a heuristic for better exploration of the search space, especially for larger and more complex puzzles. However, both solutions have exponential worst-case time complexity.