Sliding Puzzle

class BoardSolver {
public:
    int solvePuzzle(vector<vector<int>>& board) {
        vector<vector<int>> movesMap = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

        string goal = "123450";
        string start;

        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                start += to_string(board[i][j]);
            }
        }

        unordered_set<string> seen;
        queue<string> bfsQueue;
        bfsQueue.push(start);
        seen.insert(start);

        int steps = 0;

        while (!bfsQueue.empty()) {
            int levelCount = bfsQueue.size();
            while (levelCount-- > 0) {
                string current = bfsQueue.front();
                bfsQueue.pop();

                if (current == goal) {
                    return steps;
                }

                int zeroIndex = current.find('0');
                for (int move : movesMap[zeroIndex]) {
                    string newConfig = current;
                    swap(newConfig[zeroIndex], newConfig[move]);

                    if (seen.count(newConfig)) continue;

                    seen.insert(newConfig);
                    bfsQueue.push(newConfig);
                }
            }
            steps++;
        }
        return -1;
    }
};

This solution uses a Breadth First Search (BFS) algorithm to solve the "Sliding Puzzle" problem. Here's how the solution is structured and how it works:

• Define the target goal ("123450") that represents a solved puzzle with tiles in sequential order followed by the empty space.
• Extract the starting configuration of the puzzle from a 2D vector and convert it into a single string, start, for easier manipulation.
• Initialize a queue (bfsQueue) and an unordered set (seen) for BFS traversal. The start configuration is added to both the queue and the set.
• Use a movesMap that correlates each tile's index with possible moves based on the empty space (0) in the puzzle.
• Implement BFS to expand nodes level-by-level. For each level:
  1. Dequeue the current configuration and check if it matches the goal.
  2. If it matches, return the current number of steps as the solution.
  3. Otherwise, identify the position of the empty space ('0') and explore all potential moves by swapping the empty space with its possible adjacent tiles.
  4. For each new configuration generated by these moves, check if it has been seen before to avoid cycles.
  5. If the new configuration is new, add it to the seen set and enqueue it for further exploration.
  6. After exploring all possibilities at the current depth, increment the step counter.

The function returns the number of steps required to solve the puzzle or -1 if it's unsolvable. This approach efficiently handles permutations of the board's tiles and systematically works through them to find the shortest path (minimum steps) to the solution.

class Solution {

    public int solvePuzzle(int[][] initialBoard) {
        // Possible positions to move the zero in the board
        int[][] shiftOptions = new int[][] {
            { 1, 3 },
            { 0, 2, 4 },
            { 1, 5 },
            { 0, 4 },
            { 1, 3, 5 },
            { 2, 4 },
        };

        String goalState = "123450";
        StringBuilder initialState = new StringBuilder();

        // Convert board from 2D array to string format
        for (int row = 0; row < initialBoard.length; row++) {
            for (int col = 0; col < initialBoard[0].length; col++) {
                initialState.append(initialBoard[row][col]);
            }
        }

        Set<String> seenStates = new HashSet<>(); // Track seen configurations
        Queue<String> stateQueue = new LinkedList<>();
        stateQueue.add(initialState.toString());
        seenStates.add(initialState.toString());

        int steps = 0;

        // Breadth-first search to find the minimum steps to solve
        while (!stateQueue.isEmpty()) {
            int levelCount = stateQueue.size();
            while (levelCount-- > 0) {
                String currState = stateQueue.poll();

                // If the target configuration is reached
                if (currState.equals(goalState)) {
                    return steps;
                }

                int zeroIndex = currState.indexOf('0');
                for (int nextPos : shiftOptions[zeroIndex]) {
                    String newState = exchangeCharacters(currState, zeroIndex, nextPos);

                    // Avoid revisiting the same state
                    if (seenStates.contains(newState)) continue;

                    // Process the new state
                    seenStates.add(newState);
                    stateQueue.add(newState);
                }
            }
            steps++;
        }
        return -1;
    }

    // Method to swap characters within a string at positions idx1 and idx2
    private String exchangeCharacters(String str, int idx1, int idx2) {
        StringBuilder modified = new StringBuilder(str);
        modified.setCharAt(idx1, str.charAt(idx2));
        modified.setCharAt(idx2, str.charAt(idx1));
        return modified.toString();
    }
}

This Java solution employs a breadth-first search (BFS) algorithm to solve the Sliding Puzzle problem.

Here’s a breakdown of how the solution works:

• Initial Setup: The function solvePuzzle takes a 2D array representation of the initial board state. The board positions are stored in a string after conversion from the 2D array format, facilitating easier manipulation.

• Shift Options Mapping: An array shiftOptions maps each position on the board to other positions it can directly swap with. This is essential for determining valid moves without going out of the puzzle's boundaries.

• State Tracking: A Set named seenStates tracks all visited states to avoid processing the same state multiple times, enhancing efficiency. A Queue helps manage states at each level of exploration during BFS.

• Breadth-First Search Implementation: The algorithm explores all possible states level by level:

  • At each level, each current state is processed to generate new states by swapping the zero (empty space) with its neighboring positions.
  • Whenever a new valid state is found (not previously seen), it's added to both the queue and the seen set.
  • The process repeats until the goal state ("123450") is found, returning the count of steps required to reach this state.

• Helper Function: The exchangeCharacters function aids in swapping characters in the state string, simulating the movement of tiles on the board.

If the function exhausts all possibilities without finding the goal state, it returns -1, indicating that the puzzle is unsolvable from the given initial state. Each layer of BFS corresponds to a single move, so steps counts the minimum moves required to solve the puzzle.

Overall, this Java solution efficiently manages state tracking and exploration using BFS, appropriate data structures, and helper functions to solve the Sliding Puzzle efficiently.

class Solution:
    def solveSlidingPuzzle(self, grid):
        # Possible moves in the 1D form of the 2x3 grid based on index of zero
        moves_map = [
            [1, 3],
            [0, 2, 4],
            [1, 5],
            [0, 4],
            [3, 1, 5],
            [4, 2]
        ]

        # Function to swap two elements by index in a string representation
        def swap_elements(state, idx1, idx2):
            s_list = list(state)
            s_list[idx1], s_list[idx2] = s_list[idx2], s_list[idx1]
            return "".join(s_list)

        final_state = "123450"
        initial_state = "".join(str(item) for row in grid for item in row)

        seen_states = set()  # Tracks all visited states
        queue = deque([initial_state])
        seen_states.add(initial_state)

        move_count = 0

        # Breadth-first search for shortest solution path
        while queue:
            for _ in range(len(queue)):
                current = queue.popleft()

                # If solution state is found
                if current == final_state:
                    return move_count

                space_index = current.index("0")
                for move in moves_map[space_index]:
                    new_state = swap_elements(current, space_index, move)

                    if new_state not in seen_states:
                        seen_states.add(new_state)
                        queue.append(new_state)
            move_count += 1

        return -1  # Returns -1 if no solution is found

The provided Python solution addresses the Sliding Puzzle problem by using a breadth-first search (BFS) approach to identify the minimum number of moves required to reach a final desired state from a given initial state. The primary mechanism for simulation and transformation of states within the 2x3 puzzle utilizes string manipulation and a queue to keep track of the states to be explored.

Here's a detailed explanation of the approach:

• Initial and Final States Representation: The 2x3 grid is converted into a string for easier manipulation and comparison. The goal is to transform the initial grid string into the string "123450", representing the final solved state.
• State Transitions Using Moves Map: A mapping of possible moves for the zero (or empty space) within the grid is defined. This specifies which indices the zero can move to from any given position in the 1D string representation of the grid.
• Tracking Visited States: A set is used to track states that have already been visited to prevent cyclic processing and redundant work.
• Breadth-first Search Implementation: A queue initiates with the initial state of the puzzle. The algorithm explores each state by dequeuing and generating all possible resultant states by moving the zero in allowable directions. Each newly generated state is checked against the set of visited states.
• Distance Measurement and Completion Check: Every loop at the current level of the BFS corresponds to a single move. If the final state ("123450") is achieved, the function returns the number of moves taken. If the queue is exhausted without reaching the final state, indicating no possible solution, the function returns -1.

This BFS-based algorithm efficiently explores the shortest path, leveraging state transitions based on allowable moves and ensuring that previously visited configurations are not revisited. The BFS ensures that the shortest path solution, if it exists, will be found in an optimal manner.