Sliding Puzzle

Hard

Nvidia

2 views

Topics:

Graphs

On a 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]]

Write a function to efficiently solve this problem.

Sliding Puzzle

Hard

Nvidia

2 views

Topics:

Graphs

On a 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]]

Write a function to efficiently solve this problem.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the board? Can I assume it's always a 2x3 board?
What integer values will be on the tiles, and are they guaranteed to be distinct?
What should I return if the puzzle is unsolvable?
Is the initial state of the puzzle guaranteed to be a valid permutation of the integers?
By 'sliding' do you mean that tiles can only be moved into the empty space directly adjacent to it, and not by, for example, swapping tiles?

Brute Force Solution

Approach

The brute force approach to solving the sliding puzzle involves exploring every single possible sequence of moves. Think of it like physically trying out every combination until you stumble upon the solution. We keep trying things until we find the way to solve the puzzle, no matter how long it takes.

Here's how the algorithm would work step-by-step:

Start with the initial state of the puzzle.
Find the empty space and identify all the possible moves (up, down, left, right) that can be made by sliding a tile into it.
For each possible move, make the move and create a new puzzle state.
Repeat the process of finding possible moves and creating new states from each of these new puzzle states.
Keep track of every puzzle state you've already seen to avoid repeating the same moves over and over (getting stuck in loops).
Continue exploring new states until you find the solved puzzle state, or until you've exhausted all possible moves within a reasonable limit.
If the solved state is found, you've found a solution sequence of moves. If you run out of moves or reach a set limit, it's possible the puzzle is unsolvable from the starting state, or that you need to allow for more steps.

Code Implementation

def solve_sliding_puzzle_brute_force(initial_state):
    visited_states = set()
    queue = [(initial_state, [])]

    while queue:
        current_state, moves = queue.pop(0)

        state_tuple = tuple(current_state)

        if state_tuple in visited_states:
            continue

        visited_states.add(state_tuple)

        if current_state == [1, 2, 3, 4, 5, 0]:
            return moves

        empty_index = current_state.index(0)

        possible_moves = []

        if empty_index % 3 > 0:
            possible_moves.append('left')
        if empty_index % 3 < 2:
            possible_moves.append('right')
        if empty_index // 3 > 0:
            possible_moves.append('up')
        if empty_index // 3 < 1:
            possible_moves.append('down')

        for move in possible_moves:
            new_state = current_state[:]

            if move == 'left':
                new_index = empty_index - 1
            elif move == 'right':
                new_index = empty_index + 1
            elif move == 'up':
                new_index = empty_index - 3
            elif move == 'down':
                new_index = empty_index + 3

            new_state[empty_index], new_state[new_index] = new_state[new_index], new_state[empty_index]
            new_moves = moves + [move]

            # Add valid new state to the queue
            queue.append((new_state, new_moves))

    # No solution found
    return None

Big(O) Analysis

Time Complexity

O(b^d) – The brute force approach explores all possible moves to solve the sliding puzzle. The branching factor, 'b', represents the number of possible moves from each state (typically 2-4). The depth, 'd', represents the number of moves required to reach the solution or the maximum search depth. In the worst-case scenario, we might need to explore all possible move sequences up to depth 'd', resulting in b * b * ... * b (d times) or b^d operations. Therefore, the time complexity is O(b^d), where 'b' is the branching factor and 'd' is the depth of the search.

Space Complexity

O(N!) – The brute force approach explores all possible states of the sliding puzzle. The number of possible states for a sliding puzzle is related to the number of permutations of the tiles. Since we are keeping track of every puzzle state we've already seen to avoid cycles, we are using a data structure, like a set, to store these visited states. In the worst-case scenario, we might need to store all possible states. For a sliding puzzle with N tiles, the number of possible states can grow factorially, leading to an auxiliary space complexity of O(N!).

Optimal Solution

Approach

The sliding puzzle problem can be solved efficiently using a technique that explores the possible moves in a way that prioritizes the most promising ones. We can imagine each puzzle state as a point and the possible moves as connections between these points, and then use a search algorithm to find the shortest path to the solved state.

Here's how the algorithm would work step-by-step:

Represent the puzzle's current arrangement as a single thing that we can compare to others.
Create a list of puzzles that we need to explore, starting with the initial puzzle.
Repeat the following process until we find the solved puzzle:
Take the first puzzle from our list of puzzles to explore.
If this puzzle is the solved puzzle, then we are done and can trace back the solution.
Find all the possible next arrangements by sliding the blank space.
For each of those next arrangements, check if we have already seen it before.
If we haven't seen it, add it to the end of our list of puzzles to explore and mark down where it came from.
Keep track of how many moves it takes to reach each arrangement.
When we find the solved puzzle, trace back from the solved puzzle to the initial puzzle, using the 'where it came from' information, to find the sequence of moves.

Code Implementation

def solve_sliding_puzzle(initial_board):
    target_board = (1, 2, 3, 4, 5, 0)
    initial_state = tuple(initial_board)

    if initial_state == target_board:
        return []

    queue = [(initial_state, [])]
    visited_states = {initial_state}
    zero_index_map = {0: (0, 0), 1: (0, 1), 2: (0, 2), 3: (1, 0), 4: (1, 1), 5: (1, 2)}
    
    def get_neighbors(board_state):
        zero_index = board_state.index(0)
        row, col = zero_index_map[zero_index]
        possible_moves = []
        if row > 0:
            possible_moves.append((row - 1, col))
        if row < 1:
            possible_moves.append((row + 1, col))
        if col > 0:
            possible_moves.append((row, col - 1))
        if col < 2:
            possible_moves.append((row, col + 1))

        neighbor_states = []
        for neighbor_row, neighbor_col in possible_moves:
            neighbor_index = neighbor_row * 3 + neighbor_col
            new_board = list(board_state)
            new_board[zero_index], new_board[neighbor_index] = new_board[neighbor_index], new_board[zero_index]
            neighbor_states.append(tuple(new_board))
        return neighbor_states

    while queue:
        current_state, path = queue.pop(0)

        if current_state == target_board:
            return path

        # Explore possible next states
        for next_state in get_neighbors(current_state):
            if next_state not in visited_states:
                # Avoid re-visiting already explored states.
                visited_states.add(next_state)
                queue.append((next_state, path + [next_state]))
    # If the target cannot be reached.
    return None

Big(O) Analysis

Time Complexity

O(b^m) – The time complexity of the sliding puzzle solution is dominated by the breadth-first search (BFS) algorithm. The algorithm explores the puzzle states level by level, branching out at each state to consider all possible moves (sliding the blank space). 'b' represents the branching factor, which is the average number of possible moves from each state (typically 2-4 in the sliding puzzle). 'm' is the depth of the search, representing the number of moves required to reach the solved state from the initial state. In the worst case, the algorithm may explore all possible states up to depth 'm', leading to a time complexity that is exponential in the number of moves, approximated as O(b^m).

Space Complexity

O(K) – The auxiliary space is dominated by the queue of puzzles to explore and the set of seen puzzles. In the worst case, we might explore almost all possible puzzle states before finding the solution. Since the sliding puzzle has a limited number of configurations (K), where K is the number of possible arrangements of the puzzle tiles, both the queue and the set of seen puzzles could grow up to a size proportional to K. Therefore, the space complexity is O(K), where K is the number of possible puzzle states.

Edge Cases

Case	How to Handle
Null or Empty initial board	Return -1 immediately as no moves are possible from an invalid board state.
Initial board already in solved state	Return 0 as no moves are needed.
Unsolvable puzzle configuration (e.g., odd number of inversions)	Return -1 after exploring the entire reachable state space if the solved state isn't found, indicating no solution.
Large puzzle dimensions (e.g., exceeding memory limits during BFS)	Implement iterative deepening A* or a similar memory-efficient search algorithm if memory becomes a constraint.
Integer overflow when calculating board hash or coordinates	Use appropriate data types (e.g., long) for hash calculations or coordinate transformations to prevent overflow.
Board with invalid numbers (outside of valid range)	Throw an IllegalArgumentException or return -1 after validating board input and number range.
Maximum search depth (preventing infinite loops in unsolvable cases)	Implement a depth limit in the search algorithm and return -1 if the limit is reached without finding a solution.
Very large number of possible moves from a given state	Prioritize moves based on a heuristic function (like Manhattan distance) to guide the search towards the goal state more efficiently using A*.