Sliding Puzzle

Depth-First Search — Diving Before Looking Around — The board at each call: indigo marks where the last tile slid, amber marks a call that stops because the board was already reached as quickly.

#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

class Solution {
    // The board is read row by row into 6 cells; NEIGHBORS[i] are the cells next to cell i.
    const vector<vector<int>> NEIGHBORS = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
    const string GOAL = "123450";
    unordered_map<string, int> best;  // the fewest moves found so far that reach each board

    void explore(string b, int moves) {
        auto it = best.find(b);
        if (it != best.end() && it->second <= moves) return;  // already reached at least as quickly
        best[b] = moves;
        if (b == GOAL) return;
        int z = b.find('0');
        for (int j : NEIGHBORS[z]) {
            string next = b;
            swap(next[z], next[j]);  // slide the tile at j into the empty square
            explore(next, moves + 1);
        }
    }

public:
    int slidingPuzzle(vector<vector<int>>& board) {
        string start;
        for (auto& row : board)
            for (int x : row) start += char('0' + x);
        best.clear();
        explore(start, 0);
        auto it = best.find(GOAL);
        return it == best.end() ? -1 : it->second;
    }
};

class Solution:
    # The board is read row by row into 6 cells; NEIGHBORS[i] are the cells next to cell i.
    NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
    GOAL = '123450'

    def slidingPuzzle(self, board: list[list[int]]) -> int:
        start = ''.join(str(x) for row in board for x in row)
        best = {}  # the fewest moves found so far that reach each board
        self.explore(start, 0, best)
        return best.get(self.GOAL, -1)

    def explore(self, b: str, moves: int, best: dict) -> None:
        if b in best and best[b] <= moves:
            return  # this board was already reached at least as quickly
        best[b] = moves
        if b == self.GOAL:
            return
        z = b.index('0')
        for j in self.NEIGHBORS[z]:
            s = list(b)
            s[z], s[j] = s[j], s[z]  # slide the tile at j into the empty square
            self.explore(''.join(s), moves + 1, best)

import java.util.HashMap;
import java.util.Map;

class Solution {
    // The board is read row by row into 6 cells; NEIGHBORS[i] are the cells next to cell i.
    private static final int[][] NEIGHBORS = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
    private static final String GOAL = "123450";
    private final Map<String, Integer> best = new HashMap<>();  // the fewest moves found so far that reach each board

    public int slidingPuzzle(int[][] board) {
        StringBuilder start = new StringBuilder();
        for (int[] row : board)
            for (int x : row) start.append(x);
        best.clear();
        explore(start.toString(), 0);
        return best.getOrDefault(GOAL, -1);
    }

    private void explore(String b, int moves) {
        Integer known = best.get(b);
        if (known != null && known <= moves) return;  // already reached at least as quickly
        best.put(b, moves);
        if (b.equals(GOAL)) return;
        int z = b.indexOf('0');
        for (int j : NEIGHBORS[z]) {
            char[] s = b.toCharArray();
            s[z] = s[j];  // slide the tile at j into the empty square
            s[j] = '0';
            explore(new String(s), moves + 1);
        }
    }
}

Breadth-First Search — One Ring at a Time — Boards join at the back of the queue and leave from the front, so they are handled in order of how many moves they are from the start.

#include <queue>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // The board is read row by row into 6 cells; neighbors[i] are the cells next to cell i.
        const vector<vector<int>> neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
        const string goal = "123450";
        string start;
        for (auto& row : board)
            for (int x : row) start += char('0' + x);
        unordered_set<string> seen{start};
        queue<pair<string, int>> q;
        q.push({start, 0});
        while (!q.empty()) {
            auto [b, moves] = q.front();
            q.pop();
            if (b == goal) return moves;  // boards leave the queue in order of distance, so this is the fewest
            int z = b.find('0');
            for (int j : neighbors[z]) {
                string next = b;
                swap(next[z], next[j]);  // slide the tile at j into the empty square
                if (seen.insert(next).second) q.push({next, moves + 1});
            }
        }
        return -1;
    }
};

from collections import deque


class Solution:
    def slidingPuzzle(self, board: list[list[int]]) -> int:
        # The board is read row by row into 6 cells; neighbors[i] are the cells next to cell i.
        neighbors = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
        goal = '123450'
        start = ''.join(str(x) for row in board for x in row)
        seen = {start}
        queue = deque([(start, 0)])
        while queue:
            b, moves = queue.popleft()
            if b == goal:
                return moves  # boards leave the queue in order of distance, so this is the fewest
            z = b.index('0')
            for j in neighbors[z]:
                s = list(b)
                s[z], s[j] = s[j], s[z]  # slide the tile at j into the empty square
                nxt = ''.join(s)
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, moves + 1))
        return -1

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int slidingPuzzle(int[][] board) {
        // The board is read row by row into 6 cells; neighbors[i] are the cells next to cell i.
        int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
        String goal = "123450";
        StringBuilder sb = new StringBuilder();
        for (int[] row : board)
            for (int x : row) sb.append(x);
        String start = sb.toString();
        Set<String> seen = new HashSet<>();
        seen.add(start);
        ArrayDeque<String> queue = new ArrayDeque<>();
        ArrayDeque<Integer> dist = new ArrayDeque<>();
        queue.add(start);
        dist.add(0);
        while (!queue.isEmpty()) {
            String b = queue.poll();
            int moves = dist.poll();
            if (b.equals(goal)) return moves;  // boards leave the queue in order of distance, so this is the fewest
            int z = b.indexOf('0');
            for (int j : neighbors[z]) {
                char[] s = b.toCharArray();
                s[z] = s[j];  // slide the tile at j into the empty square
                s[j] = '0';
                String next = new String(s);
                if (seen.add(next)) {
                    queue.add(next);
                    dist.add(moves + 1);
                }
            }
        }
        return -1;
    }
}

Even/Odd Check, Then Two Searches That Meet — First the out-of-order pairs are counted; then each cell is a board in one search's current ring, labelled by side and distance, until the two searches touch.

#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // The board is read row by row into 6 cells; neighbors[i] are the cells next to cell i.
        const vector<vector<int>> neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
        const string goal = "123450";
        string start;
        for (auto& row : board)
            for (int x : row) start += char('0' + x);

        // No move changes whether the count of out-of-order tile pairs is even or odd,
        // and the goal has none, so an odd count can never be solved.
        string tiles;
        for (char c : start)
            if (c != '0') tiles += c;
        int outOfOrder = 0;
        for (int i = 0; i < 5; i++)
            for (int j = i + 1; j < 5; j++)
                if (tiles[i] > tiles[j]) outOfOrder++;
        if (outOfOrder % 2 == 1) return -1;
        if (start == goal) return 0;

        // Search from both ends, one whole layer at a time, always growing the smaller layer.
        unordered_map<string, int> distA{{start, 0}}, distB{{goal, 0}};
        vector<string> layerA{start}, layerB{goal};
        while (!layerA.empty() && !layerB.empty()) {
            if (layerA.size() > layerB.size()) {
                swap(distA, distB);
                swap(layerA, layerB);
            }
            vector<string> nextLayer;
            for (const string& b : layerA) {
                int z = b.find('0');
                for (int j : neighbors[z]) {
                    string next = b;
                    swap(next[z], next[j]);  // slide the tile at j into the empty square
                    auto meet = distB.find(next);
                    if (meet != distB.end()) return distA[b] + 1 + meet->second;  // the two searches meet here
                    if (!distA.count(next)) {
                        distA[next] = distA[b] + 1;
                        nextLayer.push_back(next);
                    }
                }
            }
            layerA = nextLayer;
        }
        return -1;
    }
};

class Solution:
    def slidingPuzzle(self, board: list[list[int]]) -> int:
        # The board is read row by row into 6 cells; neighbors[i] are the cells next to cell i.
        neighbors = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
        goal = '123450'
        start = ''.join(str(x) for row in board for x in row)

        # No move changes whether the count of out-of-order tile pairs is even or odd,
        # and the goal has none, so an odd count can never be solved.
        tiles = [c for c in start if c != '0']
        out_of_order = sum(1 for i in range(5) for j in range(i + 1, 5) if tiles[i] > tiles[j])
        if out_of_order % 2 == 1:
            return -1
        if start == goal:
            return 0

        # Search from both ends, one whole layer at a time, always growing the smaller layer.
        dist_a, dist_b = {start: 0}, {goal: 0}
        layer_a, layer_b = [start], [goal]
        while layer_a and layer_b:
            if len(layer_a) > len(layer_b):
                dist_a, dist_b, layer_a, layer_b = dist_b, dist_a, layer_b, layer_a
            next_layer = []
            for b in layer_a:
                z = b.index('0')
                for j in neighbors[z]:
                    s = list(b)
                    s[z], s[j] = s[j], s[z]  # slide the tile at j into the empty square
                    nxt = ''.join(s)
                    if nxt in dist_b:
                        return dist_a[b] + 1 + dist_b[nxt]  # the two searches meet here
                    if nxt not in dist_a:
                        dist_a[nxt] = dist_a[b] + 1
                        next_layer.append(nxt)
            layer_a = next_layer
        return -1

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int slidingPuzzle(int[][] board) {
        // The board is read row by row into 6 cells; neighbors[i] are the cells next to cell i.
        int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
        String goal = "123450";
        StringBuilder sb = new StringBuilder();
        for (int[] row : board)
            for (int x : row) sb.append(x);
        String start = sb.toString();

        // No move changes whether the count of out-of-order tile pairs is even or odd,
        // and the goal has none, so an odd count can never be solved.
        String tiles = start.replace("0", "");
        int outOfOrder = 0;
        for (int i = 0; i < 5; i++)
            for (int j = i + 1; j < 5; j++)
                if (tiles.charAt(i) > tiles.charAt(j)) outOfOrder++;
        if (outOfOrder % 2 == 1) return -1;
        if (start.equals(goal)) return 0;

        // Search from both ends, one whole layer at a time, always growing the smaller layer.
        Map<String, Integer> distA = new HashMap<>(), distB = new HashMap<>();
        distA.put(start, 0);
        distB.put(goal, 0);
        List<String> layerA = new ArrayList<>(List.of(start)), layerB = new ArrayList<>(List.of(goal));
        while (!layerA.isEmpty() && !layerB.isEmpty()) {
            if (layerA.size() > layerB.size()) {
                Map<String, Integer> d = distA; distA = distB; distB = d;
                List<String> l = layerA; layerA = layerB; layerB = l;
            }
            List<String> nextLayer = new ArrayList<>();
            for (String b : layerA) {
                int z = b.indexOf('0');
                for (int j : neighbors[z]) {
                    char[] s = b.toCharArray();
                    s[z] = s[j];  // slide the tile at j into the empty square
                    s[j] = '0';
                    String next = new String(s);
                    Integer meet = distB.get(next);
                    if (meet != null) return distA.get(b) + 1 + meet;  // the two searches meet here
                    if (!distA.containsKey(next)) {
                        distA.put(next, distA.get(b) + 1);
                        nextLayer.add(next);
                    }
                }
            }
            layerA = nextLayer;
        }
        return -1;
    }
}