We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sliding Puzzle

Number: 787

Difficulty: Hard

Paid? No

Companies: Meta, Google, Uber, Nvidia, Airbnb, TikTok

Problem Description

Given a 2x3 board with tiles labeled 1 through 5 and an empty square represented by 0, the goal is to move the board from its initial state to the solved state [[1,2,3],[4,5,0]] by sliding the 0 tile with one of its 4-directionally adjacent numbers. Return the minimum number of moves required to solve the board. If the board is unsolvable, return -1.

Key Insights

  • Represent the board as a string (e.g. "123450") to simplify state comparison and manipulation.
  • Use Breadth First Search (BFS) to explore all possible moves since the puzzle has a small fixed state space (6! = 720 possible states).
  • Precompute the valid neighbor indices for each board position to efficiently generate new states.
  • Track visited states to avoid loops and redundant work.

Space and Time Complexity

Time Complexity: O(1) in practice, since there are at most 720 states (6! permutations). Space Complexity: O(1) for the same reason, as the state space is fixed and limited.

Solution

We solve the problem using a Breadth First Search (BFS) approach. The board configuration is flattened into a string to represent states. A mapping from each index to its possible neighbors (i.e., positions to which 0 can move) is precomputed. BFS is then used to explore every valid move from the initial state while marking states as visited to avoid cycles. When the goal state ("123450") is reached, we return the number of moves taken. If BFS completes without reaching the goal, the puzzle is unsolvable and we return -1.

Code Solutions

import collections

def slidingPuzzle(board):
    # Flatten board into a string representation.
    start = ''.join(str(num) for row in board for num in row)
    goal = "123450"
    # Mapping of indices to their neighbors in a 2x3 board.
    neighbors = {0: [1, 3], 1: [0,2,4], 2: [1,5],
                 3: [0,4], 4: [1,3,5], 5: [2,4]}
    
    # Initialize BFS with the starting state and move count 0.
    q = collections.deque([(start, 0)])
    visited = set([start])
    
    # Process states in the queue.
    while q:
        state, moves = q.popleft()
        if state == goal:
            return moves
        zero_index = state.index('0')
        # Try all valid moves by swapping 0 with its neighbours.
        for neighbor in neighbors[zero_index]:
            new_state = list(state)
            new_state[zero_index], new_state[neighbor] = new_state[neighbor], new_state[zero_index]
            new_state_str = ''.join(new_state)
            if new_state_str not in visited:
                visited.add(new_state_str)
                q.append((new_state_str, moves + 1))
    return -1

# Example usage:
print(slidingPuzzle([[1,2,3],[4,0,5]]))
← Back to All Questions