Sliding Puzzle

hard bfs graphs state-search

Problem

Solve a 2x3 sliding puzzle: tiles 1-5 plus a 0 (empty). Return the minimum number of moves to reach '123450', or -1 if unsolvable.

Inputboard=[[1,2,3],[4,0,5]]

Output1

Swap 0 and 5 once to reach the goal.

input

from collections import deque
def slidingPuzzle(board):
    target = "123450"
    start = "".join(str(c) for row in board for c in row)
    neigh = {0:[1,3], 1:[0,2,4], 2:[1,5], 3:[0,4], 4:[1,3,5], 5:[2,4]}
    seen = {start}
    q = deque([(start, 0)])
    while q:
        s, d = q.popleft()
        if s == target: return d
        i = s.index('0')
        for j in neigh[i]:
            lst = list(s); lst[i], lst[j] = lst[j], lst[i]
            t = "".join(lst)
            if t not in seen:
                seen.add(t); q.append((t, d+1))
    return -1

function slidingPuzzle(board) {
  const target = "123450";
  const start = board.flat().join("");
  const neigh = {0:[1,3],1:[0,2,4],2:[1,5],3:[0,4],4:[1,3,5],5:[2,4]};
  const seen = new Set([start]);
  const q = [[start, 0]];
  while (q.length) {
    const [s, d] = q.shift();
    if (s === target) return d;
    const i = s.indexOf('0');
    for (const j of neigh[i]) {
      const lst = s.split('');
      [lst[i], lst[j]] = [lst[j], lst[i]];
      const t = lst.join('');
      if (!seen.has(t)) { seen.add(t); q.push([t, d+1]); }
    }
  }
  return -1;
}

int slidingPuzzle(int[][] board) {
    String target = "123450";
    StringBuilder sb = new StringBuilder();
    for (int[] r : board) for (int v : r) sb.append(v);
    String start = sb.toString();
    int[][] neigh = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};
    Set<String> seen = new HashSet<>(); seen.add(start);
    Deque<int[]> q = new ArrayDeque<>();
    Map<Integer,String> idx = new HashMap<>(); idx.put(0, start);
    q.offer(new int[]{0, 0});
    while (!q.isEmpty()) {
        int[] cur = q.poll(); String s = idx.get(cur[0]); int d = cur[1];
        if (s.equals(target)) return d;
        int i = s.indexOf('0');
        for (int j : neigh[i]) {
            char[] a = s.toCharArray(); char tmp = a[i]; a[i]=a[j]; a[j]=tmp;
            String t = new String(a);
            if (seen.add(t)) { int k = idx.size(); idx.put(k, t); q.offer(new int[]{k, d+1}); }
        }
    }
    return -1;
}

int slidingPuzzle(vector<vector<int>>& board) {
    string target = "123450", start;
    for (auto& r : board) for (int v : r) start += char('0'+v);
    vector<vector<int>> neigh = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};
    unordered_set<string> seen{start};
    queue<pair<string,int>> q;
    q.push({start, 0});
    while (!q.empty()) {
        auto [s, d] = q.front(); q.pop();
        if (s == target) return d;
        int i = s.find('0');
        for (int j : neigh[i]) {
            string t = s; swap(t[i], t[j]);
            if (!seen.count(t)) { seen.insert(t); q.push({t, d+1}); }
        }
    }
    return -1;
}

Explanation

We need the fewest moves to reach the goal board 123450. Whenever you want the shortest number of steps between states, breadth-first search (BFS) is the right tool, because it explores states level by level and the first time it reaches the goal, that level count is the minimum.

The clever trick is to treat each board as a plain string. We flatten the 2x3 grid into 6 characters, so [[1,2,3],[4,0,5]] becomes "123405". The empty cell is the 0, and a move means swapping that 0 with one of its neighbors.

The neigh map lists which positions are adjacent on the 2x3 grid. For example position 1 (top middle) can swap with 0, 2, or 4. We find where 0 sits with s.index('0') and generate one new string per valid swap.

A seen set stops us from revisiting board states, and the queue stores each state together with its distance from the start. When we pop the target, we return that distance; if the queue empties first, the puzzle is unsolvable so we return -1.

Example: from "123405" the 0 is at index 4, whose neighbors include index 5 (the 5). Swapping gives "123450", the goal, in just 1 move.

Time: O(6!) Space: O(6!)