$$\color{Red}{八数码【解析】——Astar【代码简短优化版】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

这道题是八数码普通版的升级版：我的八数码基础版题解 bfs和堆优化bfs

思路

一维和二维坐标变换想必大家应该不会不知道。【不知道就看上面的题解】

那么首先讲一下 A star 算法和这道题的一些细节需要更改的地方

A star 算法需要有一个估值函数

这个估值函数很多时候会极大的影响我们搜索的效率，而导航中常用的，在二维坐标中，就是以实际距离 + 当前距离和终点的曼哈顿距离为启发值

这道题显然，可以使用如上的估值方法。

因此做法就是在本身八数码的基础上，我们给每个节点类【每个状态视为一个节点】加入一个字符串属性作为变成现在的样子的操作，然后之前做法的节点的操作数在堆排序换为【启发值】

而是否要入堆的依据则是——> 操作数的哈希表，如果当前变化出来的字符串，已经在哈希表存在对应的操作数，显然，它不应该入堆，因为它已经入堆一次，它能变换到的字符串，显然应该早就入堆了，应当排除。

最后这道题有一个开局的优化操作：

八数码问题的有无解判断

当数字序列的逆序对个数为偶数： 有解

反之无解

java A star

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main {

    static String start = "";
    static String end = "12345678x";
    static HashMap<String, Integer> d = new HashMap<>();

    static void swap(char[] a, int x, int y) {
        char temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    static int f(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'x') continue;
            int x1 = i / 3, y1 = i % 3;
            int x2 = (s.charAt(i) - '1') / 3, y2 = (s.charAt(i) - '1') % 3;
            res += Math.abs(x1 - x2) + Math.abs(y1 - y2);
        }
        return res;
    }

    static class Node {
        String str, op;
        Integer cnt;

        public Node(String str, String op, Integer cnt) {
            this.str = str;
            this.op = op;
            this.cnt = cnt;
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static String bfs() {
        PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> o1.cnt - o2.cnt);
        heap.add(new Node(start, "", f(start)));
        d.put(start, 0);
        int[] dx = new int[]{-1, 0, 1, 0}, dy = new int[]{0, 1, 0, -1};
        String[] op = new String[]{"u", "r", "d", "l"};
        while (!heap.isEmpty()) {
            Node peek = heap.poll();
            if (peek.str.equals(end)) return peek.op;

            int index = peek.str.indexOf("x");
            int x = index / 3, y = index % 3;

            for (int i = 0; i < 4; i++) {
                char[] c = peek.str.toCharArray();
                int a = x + dx[i], b = y + dy[i];
                String operate = op[i];
                if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;
                swap(c, index, a * 3 + b);
                String str = new String(c);
                if (!d.containsKey(str)){
                    heap.add(new Node(str, peek.op + operate, d.get(peek.str) + 1 + f(str)));
                    d.put(str, d.get(peek.str) + 1);
                }
            }
        }
        return null;
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        String seq = "";
        for (int i = 0; i < s1.length; i++) {
            start += s1[i];
            if (!s1[i].equals("x")) seq += s1[i];
        }
        int cnt = 0;
        for (int i = 0; i < seq.length(); i++)
            for (int j = i + 1; j < seq.length(); j++)
                if ((int) seq.charAt(i) > (int) seq.charAt(j)) cnt++;
        if (cnt % 2 != 0) System.out.println("unsolvable");
        else System.out.println(bfs());
    }
}