Sliding Puzzle Solution in Java

Explore Solutions in Other Languages

Problem Description

Ah, the Sliding Puzzle! A delightful little game that makes you question your sanity while trying to arrange numbers in a specific order. Imagine you’re at a party, and everyone is dancing chaotically. Your job? Get them to line up in a neat row! The Sliding Puzzle is just like that, but instead of party-goers, you have numbers on a 2×3 board, and one of those spots is empty (the “0”). Your goal is to slide the numbers around until they are in the order of “123450”.

In simpler terms, you have a board that looks like this:

1 2 3
4 5 0

And you can slide the numbers into the empty space. Sounds easy, right? Well, it can be a real brain teaser, especially when you realize that not every configuration can lead to the goal. So, buckle up and let’s dive into the code!

Java Code Solution


class Solution {
  public int slidingPuzzle(int[][] board) {
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = 2;
    final int n = 3;
    final String goal = "123450";
    StringBuilder startSb = new StringBuilder();

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        startSb.append((char) ('0' + board[i][j]));

    final String start = startSb.toString();
    if (start.equals(goal))
      return 0;

    Queue q = new ArrayDeque<>(List.of(start));
    Set seen = new HashSet<>(Arrays.asList(start));

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final String s = q.poll();
        final int zeroIndex = s.indexOf("0");
        final int i = zeroIndex / n;
        final int j = zeroIndex % n;
        for (int[] dir : dirs) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          final int swappedIndex = x * n + y;
          StringBuilder sb = new StringBuilder(s);
          sb.setCharAt(zeroIndex, s.charAt(swappedIndex));
          sb.setCharAt(swappedIndex, s.charAt(zeroIndex));
          final String t = sb.toString();
          if (t.equals(goal))
            return step;
          if (!seen.contains(t)) {
            q.offer(t);
            seen.add(t);
          }
        }
      }

    return -1;
  }
}

Approach Explanation

The code uses a breadth-first search (BFS) approach to explore all possible configurations of the board. It starts from the initial configuration and explores all possible moves by sliding adjacent numbers into the empty space. Each configuration is stored in a queue, and the algorithm checks if it matches the goal configuration. If it does, the number of steps taken to reach that configuration is returned. If all configurations are explored and the goal is not reached, it returns -1.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the number of possible configurations of the board.
Space Complexity	O(N) due to the storage of configurations in the queue and the set.

Real-World Example

Think of the Sliding Puzzle as a metaphor for organizing your closet. You have a limited space (the empty slot) and a bunch of clothes (the numbers) that need to be arranged in a specific order. You can only move one piece at a time into the empty space. Just like in the puzzle, some arrangements may seem impossible to achieve, but with the right strategy (and a bit of patience), you can get everything in order!