Sliding Puzzle - Practice Coding Problems

Sliding Puzzle - Problem

Array Dynamic Programming Backtracking Breadth-First Search Memoization Matrix Hard

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, 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.

Input & Output

Example 1 — Basic Case

$ Input: board = [[1,2,3],[4,0,5]]

› Output: 1

💡 Note: Swap the 0 and the 5 in one move: [[1,2,3],[4,0,5]] → [[1,2,3],[4,5,0]]

Example 2 — Multiple Moves

$ Input: board = [[1,2,3],[5,4,0]]

› Output: -1

💡 Note: No number of moves will make the board solved. The puzzle is unsolvable.

Example 3 — Already Solved

$ Input: board = [[1,2,3],[4,5,0]]

› Output: 0

💡 Note: The board is already in the solved state, so 0 moves are needed.

Constraints

board.length == 2
board[i].length == 3
0 ≤ board[i][j] ≤ 5
Each value board[i][j] is unique

Visualization

Tap to expand

Understanding the Visualization

Input

2x3 board with tiles 1-5 and empty space 0

Process

Move empty space to adjacent positions

Output

Minimum moves to reach [[1,2,3],[4,5,0]]

Key Takeaway

🎯 Key Insight: Model as graph problem where each board state is a node and find shortest path using BFS

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to treat each board state as a node in a graph and find the shortest path to the target state. The best approach is BFS which guarantees minimum moves. Time: O(6!), Space: O(6!)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(6!)	O(6!)	Try all possible move sequences using depth-first search
BFS - Shortest Path	O(6!)	O(6!)	Use BFS to find minimum moves by exploring states level by level

Brute Force DFS — Algorithm Steps

Find position of 0 (empty space)
Try moving 0 in all 4 directions
Recursively explore each valid move
Return when target state is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with given board configuration

Try Moves

Recursively try all 4 directions for empty space

Backtrack

Explore all paths until solution found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char state[7];
} State;

void getNeighbors(const char* state, char neighbors[][7], int* count) {
    *count = 0;
    int zeroIdx = strchr(state, '0') - state;
    int row = zeroIdx / 3;
    int col = zeroIdx % 3;
    
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    for (int i = 0; i < 4; i++) {
        int newRow = row + directions[i][0];
        int newCol = col + directions[i][1];
        if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
            int newIdx = newRow * 3 + newCol;
            strcpy(neighbors[*count], state);
            char temp = neighbors[*count][zeroIdx];
            neighbors[*count][zeroIdx] = neighbors[*count][newIdx];
            neighbors[*count][newIdx] = temp;
            (*count)++;
        }
    }
}

int dfs(const char* state, const char* target, int moves) {
    if (strcmp(state, target) == 0) return moves;
    if (moves > 10) return 1000000;
    
    char neighbors[4][7];
    int count;
    getNeighbors(state, neighbors, &count);
    
    int minMoves = 1000000;
    for (int i = 0; i < count; i++) {
        int result = dfs(neighbors[i], target, moves + 1);
        if (result < minMoves) {
            minMoves = result;
        }
    }
    
    return minMoves;
}

int solution(int board[2][3]) {
    char target[] = "123450";
    char start[7] = {0};
    
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) {
            start[i * 3 + j] = '0' + board[i][j];
        }
    }
    
    if (strcmp(start, target) == 0) return 0;
    
    int result = dfs(start, target, 0);
    return result == 1000000 ? -1 : result;
}

int main() {
    int board[2][3];
    char line[100];
    fgets(line, sizeof(line), stdin);
    
    // Parse [[1,2,3],[4,0,5]] format
    sscanf(line, "[[%d,%d,%d],[%d,%d,%d]]", 
           &board[0][0], &board[0][1], &board[0][2],
           &board[1][0], &board[1][1], &board[1][2]);
    
    printf("%d\n", solution(board));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(6!)

At most 6! = 720 possible board configurations, but explores exponentially

✓ Linear Growth

Space Complexity

O(6!)

Recursion stack depth and visited states storage

✓ Linear Space

89.0K Views

Medium Frequency

~25 min Avg. Time

2.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler