773. Sliding Puzzle


Problem Description

The problem presents a sliding puzzle on a 2 by 3 board, where we have tiles labeled from 1 to 5 and one empty space represented by 0. We can move the tiles in the four cardinal directions (up, down, left, right) into the empty space, essentially swapping the tile and the 0. The goal is to transform the board into a specific target state, [[1,2,3],[4,5,0]], through a series of these moves. The objective is to figure out the minimum number of moves necessary to reach this state, or determine if the puzzle is unsolvable (-1 if it cannot be solved).

Intuition

To solve this puzzle in an efficient manner, we utilize an algorithm called A* search. This algorithm is commonly used in pathfinding and graph traversals. The intuition behind using A* search is that it can find the shortest path to the goal state by considering both the cost taken to reach a certain state and an estimate (heuristic) of the cost needed to get from that state to the goal.

Here's how we approach the solution:

  1. Representation: First, we represent the board state as a string for simplicity, which makes it easy to manipulate and store states during the search process.

  2. Heuristic Function: We define a heuristic function to estimate the distance (cost) from any state of the board to the goal state. A commonly used heuristic is the sum of the Manhattan distances for each tile from its current position to its goal position.

  3. Solvability Check: Next, we introduce a function to check if a sequence is solvable. For certain configurations, it's mathematically proven that no series of moves can lead to the solution. Particularly for this problem, we check the number of inversions (a pair of tiles that are in the reverse order from their appearance in the goal state) and if this count is even, the puzzle is solvable.

  4. Search Algorithm: Using A* search, we maintain a priority queue where each entry is a tuple consisting of the total estimated cost to reach the goal from the initial state through the current state and the representation of the current state.

  5. Expanding Nodes: We iterate over the priority queue, each time taking out the state with the lowest total estimated cost. We generate successor states by swapping the empty space with adjacent tiles.

  6. Tracking Cost and Visited States: We track the least cost to reach each visited state and only consider a new state if it hasn't been visited yet or if it has been reached with a lower cost.

  7. Goal Test: If at any point the goal state is reached, we return the cost to reach that state as the solution.

  8. Search Termination: If the priority queue is exhausted without finding the goal state, we conclude that the puzzle is not solvable and return -1.

Using A* search allows the solution to efficiently navigate towards the goal state by prioritizing moves that seem to be leading closer to the goal, making it an ideal approach to finding the least number of moves required to solve the puzzle.

Learn more about Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The solution approach involves several key components that work together using the A* search algorithm. Here, we explain how each part is implemented in the given solution:

  1. Converting to a String Representation:

    • Since the board is small, a state can be compactly represented as a six-character string. This representation is convenient for state manipulation and comparisons.
  2. Solvability Function (check):

    • Before attempting to solve, we determine if the puzzle is solvable by using a function that counts inversions. If the number of inversions is odd, the puzzle is unsolvable, and the function immediately returns -1.
  3. Heuristic Function (f):

    • We utilize the Manhattan distance as the heuristic function. The function f(s) calculates the total Manhattan distance for each tile in the string representation s from its position to the target position in the solved state.
  4. Priority Queue:

    • A min-heap priority queue is used where each entry is a tuple with the first element being the estimated total cost (distance traveled to get to the current state plus the heuristic cost) and the second element being the state representation as a string.
    • In Python, the heapq module provides the functionality to maintain the queue efficiently as a min-heap.
  5. Exploring States:

    • The A* search algorithm begins by adding the starting state to the priority queue with its estimated total cost.
    • The main loop continues as long as there are states in the priority queue to process.
    • For each state pulled from the priority queue, the algorithm generates all possible successor states by switching the zero with its adjacent tiles.
  6. Checking for Goal State:

    • If the current state is equal to the solved state, ('123450'), then the solution is found, and the function returns the cost to reach that state.
  7. Updating Costs and States:

    • Each successor state is checked to see if it has a recorded cost in the dist dictionary.
    • If the new state has not been visited or if it can be reached in fewer moves than previously recorded, it is added back into the priority queue with its new cost.
  8. Return -1 if Unsolved:

    • If the priority queue is exhausted and the solution state has never been reached, the function returns -1, indicating that the puzzle is unsolvable from the given initial state.

By following this approach, the algorithm adeptly navigates through the state space of the puzzle, minimizing the number of moves and ensuring we either reach the solution with the least number of moves or conclude that the puzzle is not solvable.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Example Walkthrough

Let's use an example to illustrate the solution approach:

Imagine the initial state of the 2 by 3 board is:

11 2 3
25 0 4

We represent this state as the string '123504'. Our goal state is '123450'.

  1. Converting to a String Representation: In this example, the initial state is converted to '123504'.

  2. Solvability Function (check): We count inversions. For our example, the inversions are (5, 4), which means it has only 1 inversion. As an odd number indicates an unsolvable puzzle, we can move forward as our example puzzle only has one inversion.

  3. Heuristic Function (f): Our initial heuristic function f(s) calculates the Manhattan distance for '5' as 1 (since it's one spot away from its target) and '4' also as 1. Our total heuristic cost is 2 for the initial state.

  4. Priority Queue: We insert the tuple (2, '123504') into our priority queue as the first entry.

  5. Exploring States: Dequeue the first state '123504' to explore. The '0' (empty space) has two options, switch with '5' (left) or '4' (right).

    If we swap '0' and '5', we get '120534'. The new Manhattan distance is 4, since '5' is now 2 steps away, and '4' is still 1 step away, with the cost to reach here being 1 (one move from the initial state), the total estimated cost is 5.

    If we swap '0' and '4', we get '123045', a step closer to our goal. The Manhattan distance is now 1, and with a move cost of 1, the total estimated cost is 2. This state is added to the priority queue.

  6. Checking for Goal State: We pull '123045' from the priority queue as it has the lowest cost, and check the goal state. It's not equal to '123450', so we continue.

  7. Updating Costs and States: From '123045', we can switch '0' with either '3' (up) or '5' (down).

    Swapping '0' and '3' gives us '103245', with a total estimated cost significantly higher, so we discard this option.

    Swapping '0' and '5' results in our goal state '123450'. We break out of the loop as we've reached the goal with a total cost of 2.

  8. Return -1 if Unsolved: As we found our goal state, we don't return -1. Instead, we return 2 as the minimum number of moves required to solve the puzzle.

And that’s how we use the A* algorithm to solve this sliding puzzle efficiently!

Not Sure What to Study? Take the 2-min Quiz:

What's the relationship between a tree and a graph?

Python Solution

1from heapq import heappop, heappush
2from typing import List
3
4class Solution:
5    def slidingPuzzle(self, board: List[List[int]]) -> int:
6        # Define board dimensions
7        rows, cols = 2, 3
8        sequence = [] # Sequence to create the start state
9        start_state, target_state = '', '123450'
10
11        # Convert the 2D board into a string representation
12        for i in range(rows):
13            for j in range(cols):
14                start_state += str(board[i][j])
15                if board[i][j] != 0:
16                    sequence.append(board[i][j])
17
18        def is_solvable(seq: List[int]) -> bool:
19            """ Check if the board configuration is solvable """
20            inv_count = sum(seq[i] > seq[j] for i in range(len(seq)) for j in range(i, len(seq)))
21            return inv_count % 2 == 0
22
23        def heuristic(s: str) -> int:
24            """ Calculate the heuristic value for A* using Manhattan distance """
25            total_distance = 0
26            for i, char in enumerate(s):
27                if char != '0':
28                    num = ord(char) - ord('1')
29                    total_distance += abs(i // cols - num // cols) + abs(i % cols - num % cols)
30            return total_distance
31
32        # Check if the puzzle is solvable
33        if not is_solvable(sequence):
34            return -1
35
36        # Priority queue for A* algorithm
37        queue = [(heuristic(start_state), start_state)]
38        distances = {start_state: 0}
39
40        # Begin A* algorithm
41        while queue:
42            _, state = heappop(queue)
43            if state == target_state:
44                return distances[state]  # Found solution
45
46            zero_position = state.index('0')  
47            i, j = divmod(zero_position, cols)
48            state_list = list(state)
49
50            # Check neighboring states by swapping the 0-tile
51            for delta_row, delta_col in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
52                x, y = i + delta_row, j + delta_col
53                if 0 <= x < rows and 0 <= y < cols:
54                    new_zero_pos = x * cols + y
55                    state_list[zero_position], state_list[new_zero_pos] = state_list[new_zero_pos], state_list[zero_position]
56                    next_state = ''.join(state_list)
57                    state_list[zero_position], state_list[new_zero_pos] = state_list[new_zero_pos], state_list[zero_position]
58                    if next_state not in distances or distances[next_state] > distances[state] + 1:
59                        distances[next_state] = distances[state] + 1
60                        heappush(queue, (distances[next_state] + heuristic(next_state), next_state))
61        return -1
62
63# Example usage:
64# solution = Solution()
65# result = solution.slidingPuzzle([[1, 2, 3], [4, 0, 5]])
66# print(result)  # Output would be the minimum number of moves required to solve the puzzle if solvable, -1 otherwise.
67

Java Solution

1class Solution {
2    private static final int ROWS = 2; // The number of rows in the puzzle
3    private static final int COLS = 3; // The number of columns in the puzzle
4
5    public int slidingPuzzle(int[][] board) {
6        String startState = ""; // Convert the initial 2D board state to a string
7        String targetState = "123450"; // The goal state we need to reach
8      
9        // Create a string without the empty tile to check puzzle solvability later
10        StringBuilder solvabilitySequence = new StringBuilder();
11      
12        // Convert the board into a startState string and solvabilitySequence string
13        for (int i = 0; i < ROWS; i++) {
14            for (int j = 0; j < COLS; j++) {
15                startState += board[i][j];
16                if (board[i][j] != 0) {
17                    solvabilitySequence.append(board[i][j]);
18                }
19            }
20        }
21      
22        // Check if the puzzle is solvable
23        if (!isPuzzleSolvable(solvabilitySequence.toString())) {
24            return -1;
25        }
26      
27        // Use a priority queue to perform A* search
28        PriorityQueue<Pair<Integer, String>> queue =
29                new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
30              
31        Map<String, Integer> distanceMap = new HashMap<>();
32        distanceMap.put(startState, 0);
33        queue.offer(new Pair<>(calculateHeuristic(startState), startState));
34      
35        int[] directions = {-1, 0, 1, 0, -1}; // Direction vectors for adjacent moves
36      
37        while (!queue.isEmpty()) {
38            Pair<Integer, String> pair = queue.poll();
39            String state = pair.getValue();
40            int steps = distanceMap.get(state);
41          
42            // If the final state is reached, return the number of steps taken
43            if (targetState.equals(state)) {
44                return steps;
45            }
46          
47            int zeroIndex = state.indexOf("0");
48            int row = zeroIndex / COLS, col = zeroIndex % COLS;
49          
50            char[] currentStateArray = state.toCharArray();
51          
52            // Try to slide an adjacent tile into the empty space
53            for (int k = 0; k < 4; k++) {
54                int newRow = row + directions[k], newCol = col + directions[k + 1];
55                if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS) {
56                    int newIndex = newRow * COLS + newCol;
57                  
58                    // Swap the empty space with the adjacent tile
59                    swap(currentStateArray, zeroIndex, newIndex);
60                    String nextState = String.valueOf(currentStateArray);
61                  
62                    // Update the minimum distance if we find a better path
63                    if (!distanceMap.containsKey(nextState) || distanceMap.get(nextState) > steps + 1) {
64                        distanceMap.put(nextState, steps + 1);
65                        queue.offer(new Pair<>(steps + 1 + calculateHeuristic(nextState), nextState));
66                    }
67                    // Swap back to the original state to try other moves
68                    swap(currentStateArray, zeroIndex, newIndex);
69                }
70            }
71        }
72        return -1; // If we reach this point, no solution has been found
73    }
74
75    // Method to swap two characters in a character array
76    private void swap(char[] array, int index1, int index2) {
77        char temp = array[index1];
78        array[index1] = array[index2];
79        array[index2] = temp;
80    }
81
82    // Heuristic function for A* search that counts Manhattan distance to the goal state
83    private int calculateHeuristic(String state) {
84        int heuristic = 0;
85        for (int i = 0; i < ROWS * COLS; i++) {
86            if (state.charAt(i) != '0') {
87                int num = state.charAt(i) - '1';
88                heuristic += Math.abs(i / COLS - num / COLS) + Math.abs(i % COLS - num % COLS);
89            }
90        }
91        return heuristic;
92    }
93
94    // Method to check if the puzzle is solvable by counting the number of inversions
95    private boolean isPuzzleSolvable(String s) {
96        int inversions = 0;
97        for (int i = 0; i < s.length(); i++) {
98            for (int j = i + 1; j < s.length(); j++) {
99                if (s.charAt(i) > s.charAt(j)) {
100                    inversions++;
101                }
102            }
103        }
104        // A state is solvable if the inversion count is even
105        return inversions % 2 == 0;
106    }
107}
108

C++ Solution

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <queue>
5#include <algorithm> // For swap function
6
7using namespace std;
8
9class Solution {
10public:
11    // Fixed dimensions of the puzzle: m x n (2 x 3)
12    const int m = 2;
13    const int n = 3;
14
15    // Function to solve the sliding puzzle
16    int slidingPuzzle(vector<vector<int>>& board) {
17        // Start and goal states as strings
18        string startState, tmpSequence;
19        const string goalState = "123450";
20
21        // Convert the board to starting string state and create a sequence for checking solvability
22        for (int i = 0; i < m; ++i) {
23            for (int j = 0; j < n; ++j) {
24                startState += char(board[i][j] + '0');
25                if (board[i][j] != 0) tmpSequence += char(board[i][j] + '0');
26            }
27        }
28
29        // Check if the board is solvable
30        if (!isSolvable(tmpSequence)) return -1;
31
32        // Use A* search algorithm
33        priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> searchQueue;
34        unordered_map<string, int> distances;
35        distances[startState] = 0;
36        searchQueue.push({heuristic(startState), startState});
37
38        // Directions for neighbours: up, right, down, left
39        vector<int> directions = {-1, 0, 1, 0, -1};
40
41        while (!searchQueue.empty()) {
42            auto currentNode = searchQueue.top();
43            searchQueue.pop();
44            string currentState = currentNode.second;
45            int currentSteps = distances[currentState];
46
47            // If goal state is reached, return the steps count
48            if (currentState == goalState) return currentSteps;
49
50            int zeroPosition = currentState.find('0');
51            int i = zeroPosition / n, j = zeroPosition % n;
52
53            // Explore all neighbouring states
54            for (int k = 0; k < 4; ++k) {
55                int newX = i + directions[k], newY = j + directions[k + 1];
56                if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;
57                int newPosition = newX * n + newY;
58                swap(currentState[zeroPosition], currentState[newPosition]);
59
60                // Update distance if not seen before or if a better path is found
61                if (!distances.count(currentState) || distances[currentState] > currentSteps + 1) {
62                    distances[currentState] = currentSteps + 1;
63                    searchQueue.push({currentSteps + 1 + heuristic(currentState), currentState});
64                }
65
66                // Swap back to restore state
67                swap(currentState[zeroPosition], currentState[newPosition]);
68            }
69        }
70
71        // If the goal state was never reached, return -1
72        return -1;
73    }
74
75    // Function to check if a given sequence is solvable
76    bool isSolvable(string sequence) {
77        int inversions = 0;
78        int size = sequence.size();
79        for (int i = 0; i < size; ++i) {
80            for (int j = i + 1; j < size; ++j) {
81                if (sequence[i] > sequence[j]) ++inversions;
82            }
83        }
84        // Puzzle is solvable if the number of inversions is even
85        return inversions % 2 == 0;
86    }
87
88    // Heuristic function for A* Search: calculates the manhattan distance for misplaced tiles
89    int heuristic(string state) {
90        int totalManhattanDistance = 0;
91        for (int i = 0; i < m * n; ++i) {
92            if (state[i] == '0') continue; // Skip the empty tile
93            int tileNumber = state[i] - '1'; // Convert character to number and adjust index
94            // Accumulate manhattan distance for each tile
95            totalManhattanDistance += abs(tileNumber / n - i / n) + abs(tileNumber % n - i % n);
96        }
97        return totalManhattanDistance;
98    }
99};
100

Typescript Solution

1// Import statements to use specific collections from a library analogous to C++ STL (if such a library exists)
2// Otherwise, these should be part of a custom implementation
3
4type Pair<T, U> = { first: number; second: string }; // Define a type for pairs
5
6// Define types for the data structures equivalent to C++ priority_queue and unordered_map
7let distances: { [key: string]: number } = {};
8
9// Fixed dimensions of the puzzle: m x n (2 x 3)
10const m: number = 2;
11const n: number = 3;
12const goalState: string = "123450";
13
14// Convert the board to a string representation
15function boardToString(board: number[][]): string {
16  return board.flat().join("");
17}
18
19// Function to solve the sliding puzzle
20function slidingPuzzle(board: number[][]): number {
21  // Start state as a string
22  let startState: string = boardToString(board);
23  // Create a sequence to check solvability (without the zero)
24  let tmpSequence: string = startState.replace("0", "");
25
26  // Check if the board is solvable
27  if (!isSolvable(tmpSequence)) return -1;
28
29  // Initialize search with A* algorithm variables
30  let searchQueue: Pair<number, string>[] = []; // This would be a priority queue in a full implementation
31  distances[startState] = 0;
32  searchQueue.push({ first: heuristic(startState), second: startState });
33
34  // Directions for neighbours: up, right, down, left
35  const directions: number[] = [-1, 0, 1, 0, -1];
36
37  while (searchQueue.length > 0) {
38    // Replace 'pop' with an appropriate priority queue pull method
39    let currentNode: Pair<number, string> = searchQueue.shift()!;
40    let currentState: string = currentNode.second;
41    let currentSteps: number = distances[currentState];
42
43    // If goal state is reached, return the steps count
44    if (currentState === goalState) return currentSteps;
45
46    let zeroPosition: number = currentState.indexOf("0");
47    let i: number = Math.floor(zeroPosition / n);
48    let j: number = zeroPosition % n;
49
50    // Explore all neighbouring states
51    for (let k: number = 0; k < 4; ++k) {
52      let newX: number = i + directions[k];
53      let newY: number = j + directions[k + 1];
54      if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;
55      let newPosition: number = newX * n + newY;
56      currentState = swapChars(currentState, zeroPosition, newPosition);
57
58      // Update distance if not seen before or if a better path is found
59      if (distances[currentState] === undefined || distances[currentState] > currentSteps + 1) {
60        distances[currentState] = currentSteps + 1;
61        searchQueue.push({ first: currentSteps + 1 + heuristic(currentState), second: currentState });
62      }
63
64      // Swap back to restore state for the next iteration
65      currentState = swapChars(currentState, zeroPosition, newPosition);
66    }
67  }
68
69  return -1; // If the goal state was never reached
70}
71
72// Function to check if a given sequence is solvable
73function isSolvable(sequence: string): boolean {
74  let inversions: number = 0;
75  for (let i: number = 0; i < sequence.length; ++i) {
76    for (let j: number = i + 1; j < sequence.length; ++j) {
77      if (sequence[i] > sequence[j]) ++inversions;
78    }
79  }
80  // Puzzle is solvable if the number of inversions is even
81  return inversions % 2 === 0;
82}
83
84// Heuristic function for A* Search: calculates the Manhattan distance for misplaced tiles
85function heuristic(state: string): number {
86  let totalManhattanDistance: number = 0;
87  for (let i: number = 0; i < m * n; ++i) {
88    if (state[i] === '0') continue; // Skip the empty tile
89    // Convert character to a number and adjust the index to be zero-based
90    let tileNumber: number = parseInt(state[i], 10) - 1;
91    // Accumulate Manhattan distance for each tile
92    totalManhattanDistance += Math.abs(Math.floor(tileNumber / n) - Math.floor(i / n)) + 
93                              Math.abs(tileNumber % n - i % n);
94  }
95  return totalManhattanDistance;
96}
97
98// Swaps characters in a string based on provided indices and returns a new string
99function swapChars(str: string, index1: number, index2: number): string {
100  let arr: string[] = str.split('');
101  let temp: string = arr[index1];
102  arr[index1] = arr[index2];
103  arr[index2] = temp;
104  return arr.join('');
105}
106
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The given Python code is for solving the sliding puzzle problem, which essentially can be framed as a shortest path problem in a graph where each state of the puzzle is a node and each valid move is an edge.

Time Complexity

The time complexity of this code mainly depends on three parts: the while loop that contains the BFS (Breadth-First Search) algorithm using a min-heap (priority queue), the check function, and the heuristic function f.

  • The check function has a time complexity of O(n^2), where n is the length of the sequence of the puzzle's rows concatenated, which is always 6 for a 2x3 board.

  • The heuristic function f is called for each state of the board. It has a time complexity of O(n), for calculating the estimated cost to reach the goal state.

  • The main while loop performs a BFS, where in the worst case, all possible permutations of the board are visited. Since we're using a min-heap to get the next state with the least cost, each insertion and removal operation takes O(log V) time, where V is the number of vertices in the graph (which corresponds to the number of possible board states). There can be up to 6! permutations (since the board can be described by a sequence of 6 numbers), so V = 6!.

For each state, up to 4 new states are considered based on possible moves (-1 and +1 horizontally, -n and +n vertically), and we insert these into the min-heap. So in the worst case, for each state we perform 4 insertions into the heap.

Therefore, the time complexity of the main while loop is O(4 * V * log V), which simplifies to O(V * log V).

Combining all of these, the overall time complexity is O(V * log V + n^2 + n), since V is constant (6!) for a 2x3 puzzle, we can simplify this time complexity further to O(V * log V).

Space Complexity

As for the space complexity:

  • The dist dictionary will store distances for up to V states, so it consumes O(V) space.

  • The priority queue (min-heap) can also have at most V states before a state is popped, resulting in a maximum space complexity of O(V).

  • Space is also used for the seq list, string manipulations, and other variables, but the majority of the space comes from the dist dictionary and the priority queue.

Thus, the overall space complexity is O(V), which again, due to the constant size of the board 2x3, simplifies to O(1).

In conclusion, the overall time complexity of this code is O(V * log V), and the space complexity is O(1), assuming a fixed-size puzzle board.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫