773. Sliding Puzzle

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

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

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