Sliding Puzzle solution and explanation

from collections import deque

def sliding_puzzle(board):
    start = ''.join(str(num) for row in board for num in row)
    target = '123450'
    neighbors = {
        0: [1, 3],
        1: [0, 2, 4],
        2: [1, 5],
        3: [0, 4],
        4: [3, 1, 5],
        5: [2, 4]
    }
    queue = deque([(start, start.index('0'), 0)]) # (board_str, zero_index, depth)
    visited = {start}
    while queue:
        board_str, zero_index, depth = queue.popleft()
        if board_str == target:
            return depth
        for adj in neighbors[zero_index]:
            new_board = list(board_str)
            new_board[zero_index], new_board[adj] = new_board[adj], new_board[zero_index]
            new_board_str = ''.join(new_board)
            if new_board_str not in visited:
                visited.add(new_board_str)
                queue.append((new_board_str, adj, depth + 1))
    return -1

using System;
using System.Collections.Generic;

public class Solution {
    public int SlidingPuzzle(int[][] board) {
        string start = string.Join("", board[0]) + string.Join("", board[1]);
        string target = "123450";
        int[][] neighbors = {
            new int[] {1, 3},
            new int[] {0, 2, 4},
            new int[] {1, 5},
            new int[] {0, 4},
            new int[] {3, 1, 5},
            new int[] {2, 4}
        };
        Queue<(string, int)> queue = new Queue<(string, int)>();
        queue.Enqueue((start, 0));
        HashSet<string> visited = new HashSet<string> { start };
        while (queue.Count > 0) {
            (string status, int steps) = queue.Dequeue();
            if (status == target) return steps;
            int zeroIndex = status.IndexOf('0');
            foreach (int adj in neighbors[zeroIndex]) {
                char[] newStatus = status.ToCharArray();
                (newStatus[zeroIndex], newStatus[adj]) = (newStatus[adj], newStatus[zeroIndex]);
                string newBoard = new string(newStatus);
                if (!visited.Contains(newBoard)) {
                    visited.Add(newBoard);
                    queue.Enqueue((newBoard, steps + 1));
                }
            }
        }
        return -1;
    }
}

import java.util.*;

public class Solution {
    public int slidingPuzzle(int[][] board) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        String start = Arrays.deepToString(board).replaceAll("[^\d]", "");
        String target = "123450";
        int[][] neighbor = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {3, 1, 5}, {2, 4}};
        pq.add(new Node(start, 0, heuristic(start, target)));
        Set<String> visited = new HashSet<>();

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            if (current.value.equals(target)) {
                return current.depth;
            }
            int zeroIndex = current.value.indexOf('0');
            visited.add(current.value);

            for (int adj : neighbor[zeroIndex]) {
                char[] newBoardArray = current.value.toCharArray();
                char temp = newBoardArray[adj];
                newBoardArray[adj] = newBoardArray[zeroIndex];
                newBoardArray[zeroIndex] = temp;
                String newBoard = new String(newBoardArray);

                if (!visited.contains(newBoard)) {
                    pq.offer(new Node(newBoard, current.depth + 1, heuristic(newBoard, target)));
                }
            }
        }
        return -1;
    }

    private int heuristic(String state, String goal) {
        int dist = 0;
        for (int i = 0; i < state.length(); i++) {
            if (state.charAt(i) != '0') {
                int targetPosition = goal.indexOf(state.charAt(i));
                dist += Math.abs(targetPosition / 3 - i / 3) + Math.abs(targetPosition % 3 - i % 3);
            }
        }
        return dist;
    }

    class Node implements Comparable<Node> {
        String value;
        int depth;
        int cost;

        Node(String v, int d, int c) {
            value = v;
            depth = d;
            cost = d + c;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.cost, other.cost);
        }
    }
}

#include <iostream>
#include <unordered_set>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

struct Node {
    string board;
    int depth;
    int cost;
    bool operator<(const Node& other) const {
        return cost > other.cost;
    }
};

int slidingPuzzle(vector<vector<int>>& board) {
    string start;
    for (auto &row : board)
        for (auto &num : row)
            start += to_string(num);
    string target = "123450";
    vector<vector<int>> neighbor = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {3, 1, 5}, {2, 4}};
    priority_queue<Node> pq;
    unordered_set<string> visited;
    pq.push({start, 0, heuristic(start, target)});

    while (!pq.empty()) {
        Node current = pq.top(); pq.pop();
        if (current.board == target) {
            return current.depth;
        }
        visited.insert(current.board);

        int zeroIndex = current.board.find('0');
        for (int adj : neighbor[zeroIndex]) {
            string newBoard = current.board;
            swap(newBoard[zeroIndex], newBoard[adj]);
            if (visited.find(newBoard) == visited.end()) {
                pq.push({newBoard, current.depth + 1, current.depth + 1 + heuristic(newBoard, target)});
            }
        }
    }
    return -1;
}

int heuristic(const string& state, const string& goal) {
    int dist = 0;
    for (int i = 0; i < state.length(); i++) {
        if (state[i] != '0') {
            int targetPosition = goal.find(state[i]);
            dist += abs(targetPosition / 3 - i / 3) + abs(targetPosition % 3 - i % 3);
        }
    }
    return dist;
}