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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sliding Puzzle

Difficulty: Hard

Problem Description

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.

Key Insights

  • The board can be represented as a string for easy state manipulation.
  • The target state is a predefined string "123450".
  • The problem can be solved using Breadth-First Search (BFS) to explore all possible board configurations.
  • Each configuration can lead to multiple next configurations based on the possible moves.
  • A check for solvability based on the number of inversions is necessary to determine if the puzzle can be solved.

Space and Time Complexity

Time Complexity: O(1), since the maximum number of states is fixed (only 6! = 720 possible configurations). Space Complexity: O(1), as we are storing a fixed number of states regardless of input size.

Solution

To solve the Sliding Puzzle problem, we will use a Breadth-First Search (BFS) approach to explore all possible states of the board. We will represent each state as a string for easy manipulation and store visited states in a set to avoid cycles. The BFS will explore all adjacent moves until we reach the target state or exhaust all possibilities. Additionally, a pre-check for solvability based on the number of inversions will filter out impossible configurations.

Code Solutions

from collections import deque

def slidingPuzzle(board):
    start = ''.join(str(num) for row in board for num in row)
    target = "123450"
    
    # Function to check if the board is solvable
    def is_solvable(board):
        flat_board = [num for row in board for num in row]
        inversions = 0
        for i in range(len(flat_board)):
            for j in range(i + 1, len(flat_board)):
                if flat_board[i] != 0 and flat_board[j] != 0 and flat_board[i] > flat_board[j]:
                    inversions += 1
        return inversions % 2 == 0
    
    if not is_solvable(board):
        return -1
    
    # BFS initialization
    queue = deque([start])
    visited = {start}
    moves = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    zero_pos = start.index('0')
    
    while queue:
        for _ in range(len(queue)):
            state = queue.popleft()
            if state == target:
                return moves
            
            zero_row, zero_col = divmod(zero_pos, 3)
            for dr, dc in directions:
                new_row, new_col = zero_row + dr, zero_col + dc
                if 0 <= new_row < 2 and 0 <= new_col < 3:
                    new_zero_pos = new_row * 3 + new_col
                    new_state = list(state)
                    new_state[zero_pos], new_state[new_zero_pos] = new_state[new_zero_pos], new_state[zero_pos]
                    new_state_str = ''.join(new_state)
                    if new_state_str not in visited:
                        visited.add(new_state_str)
                        queue.append(new_state_str)
        
        moves += 1
    
    return -1
← Back to All Questions