Sliding Puzzle

Hard Graphs BFS for shortest path Original on LeetCode

Reported atAirbnb

Sliding Puzzle is a hard graphs problem solved with the bfs for shortest path pattern. The best approach, optimal (bfs on string states with a neighbor table), runs in O(S · k) time and O(S · k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs over copied boards up.

Problem

You are given a 2 x 3 board holding five numbered tiles 1 to 5 and one empty cell, shown as 0. In one move you may slide a tile that is directly above, below, left or right of the empty cell into it, which is the same as swapping the 0 with one of its up to four neighbors.

The board is solved when it reads [[1, 2, 3], [4, 5, 0]]. Return the smallest number of moves needed to solve the given board, or -1 if no sequence of moves can solve it.

Examples

Example 1

Input
board = [[1, 2, 3], [0, 4, 5]]
Output
2
Why
Slide 4 left into the gap, then slide 5 left; the gap ends in the bottom-right corner.

Example 2

Input
board = [[2, 1, 3], [4, 5, 0]]
Output
-1
Why
Only tiles 1 and 2 are out of place, and a single swap of two tiles can never be produced by sliding moves.

Example 3

Input
board = [[3, 2, 4], [1, 5, 0]]
Output
14
Why
A breadth-first search over board layouts first reaches the solved layout after 14 moves.

Constraints

  • board.length == 2 and board[i].length == 3
  • board contains each of the numbers 0 to 5 exactly once.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
BFS over copied boardsO(S · R · C)O(S · R · C)
Optimal (BFS on string states with a neighbor table)O(S · k)O(S · k)

1BFS over copied boards

TimeO(S · R · C)Each of the S reachable layouts (at most 360 of the 720) is expanded once, and each expansion copies and serializes the R x C board several times.
SpaceO(S · R · C)The queue and the visited set hold up to S boards of R x C cells.

Run a breadth-first search where each state is a full 2 x 3 board. For each state, find the empty cell by scanning, try the up to four directions, build a new board for each legal slide, and use a text form of the board as the visited key.

  1. Start the queue with the input board at distance 0 and mark its key as seen.
  2. Pop a board; if its key equals the solved key, return its distance.
  3. Locate the 0, and for each of the four directions that stays on the grid, copy the board, swap the 0 with that neighbor and enqueue the copy if its key is new.
  4. If the queue empties, return -1.
class Solution {
    public int slidingPuzzle(int[][] board) {
        String goal = Arrays.deepToString(new int[][] { { 1, 2, 3 }, { 4, 5, 0 } });
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        Deque<int[][]> queue = new ArrayDeque<>();
        Set<String> seen = new HashSet<>();
        queue.add(board);
        seen.add(Arrays.deepToString(board));
        int moves = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                int[][] cur = queue.poll();
                if (Arrays.deepToString(cur).equals(goal)) return moves;
                int zr = 0, zc = 0;
                for (int r = 0; r < 2; r++)
                    for (int c = 0; c < 3; c++)
                        if (cur[r][c] == 0) { zr = r; zc = c; }
                for (int[] d : dirs) {
                    int nr = zr + d[0], nc = zc + d[1];
                    if (nr < 0 || nr >= 2 || nc < 0 || nc >= 3) continue;
                    int[][] next = new int[2][];
                    for (int r = 0; r < 2; r++) next[r] = cur[r].clone();
                    next[zr][zc] = next[nr][nc];
                    next[nr][nc] = 0;
                    if (seen.add(Arrays.deepToString(next))) queue.add(next);
                }
            }
            moves++;
        }
        return -1;
    }
}

2Optimal (BFS on string states with a neighbor table)

TimeO(S · k)Each of the S = 6!/2 = 360 reachable strings is processed once, with at most 3 swaps of a k = 6 character string.
SpaceO(S · k)The queue and the seen set store up to S strings of length k.

Flatten the board into a 6-character string, reading row by row. In that string, index i is cell (i / 3, i % 3), so the cells next to each index never change and can be written down once. A breadth-first search from the start string then only swaps characters, and the first time it pops the goal string the level count is the answer.

  1. Precompute adj = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]]: the indices next to each index.
  2. Build the start string from the board; enqueue it with distance 0 and add it to seen.
  3. Process the queue level by level. For each string, return the level if it equals "123450".
  4. Otherwise find the '0', and for each j in adj[zero] swap the two characters; enqueue the result if it is new.
  5. If the queue runs out, return -1.
class Solution {
    public int slidingPuzzle(int[][] board) {
        int[][] adj = { { 1, 3 }, { 0, 2, 4 }, { 1, 5 }, { 0, 4 }, { 1, 3, 5 }, { 2, 4 } };
        StringBuilder sb = new StringBuilder();
        for (int[] row : board)
            for (int x : row) sb.append(x);
        String start = sb.toString(), goal = "123450";
        Deque<String> queue = new ArrayDeque<>();
        Set<String> seen = new HashSet<>();
        queue.add(start);
        seen.add(start);
        int moves = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                String cur = queue.poll();
                if (cur.equals(goal)) return moves;
                int zero = cur.indexOf('0');
                for (int j : adj[zero]) {
                    char[] chars = cur.toCharArray();
                    chars[zero] = chars[j];
                    chars[j] = '0';
                    String next = new String(chars);
                    if (seen.add(next)) queue.add(next);
                }
            }
            moves++;
        }
        return -1;
    }
}

Edge cases to test

  • The board is already solved (answer 0)
  • Unsolvable layouts, which are exactly half of all 720 layouts
  • The farthest solvable layouts, which need 21 moves

Hints

Hint 1

Treat every arrangement of the six cells as a node in a graph; one move connects two arrangements. The question asks for a shortest path.

Hint 2

There are only 6! = 720 arrangements, so a breadth-first search with a visited set is cheap. If the search ends without reaching the goal, the answer is -1.

Hint 3

Encode a board as a 6-character string and precompute, for each position of the 0, which positions it can swap with.

FAQ

What is the best time complexity for Sliding Puzzle?

Optimal (BFS on string states with a neighbor table) runs in O(S · k) time and O(S · k) extra space. Each of the S = 6!/2 = 360 reachable strings is processed once, with at most 3 swaps of a k = 6 character string.

Which pattern does Sliding Puzzle use?

It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.

Is there a brute force solution for Sliding Puzzle?

Yes. BFS over copied boards takes O(S · R · C) time and O(S · R · C) space. Run a breadth-first search where each state is a full 2 x 3 board.

Which edge cases should I test for Sliding Puzzle?

The board is already solved (answer 0); Unsolvable layouts, which are exactly half of all 720 layouts; The farthest solvable layouts, which need 21 moves.