康托展开就是求出a[1],a[2],…,a[n]是1到n排列的第几个（当然还有逆运算），这个东西其实就是数位dp。这里不想写了。
求出开头和结尾，然后跑一遍bfs就行了，时间O(9!)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

const int N = 400000;

int d[N], last[N], jc[11]; char pre[N];
struct node { int p, statu; };
queue<node> q;


int get(int a[11]) {
    bool v[11]; 
    memset(v, 0, sizeof(v));
    int ans = 1;
    for (int i = 1; i < 9; i++) {
        int s = 0;
        for (int j = 1; j < a[i]; j++)
            if (!v[j]) s++;
        v[a[i]] = 1;
        ans += s * jc[9 - i];
    }
    return ans;
}

void ha(int a[], int statu) {
    bool v[11];
    memset(v, 0, sizeof(v));
    for (int i = 1; i < 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (v[j]) continue;
            if (jc[9 - i] < statu) statu -= jc[9 - i];
            else { a[i] = j; break; }
        }
        v[a[i]] = 1;
    }
    for (int j = 1; j <= 9; j++) if (!v[j]) { a[9] = j; return; }
}

int st; 
void print(int i) {
    if (st == i) return;
    print(last[i]);
    putchar(pre[i]);
}

int main() {
    jc[0] = 1;
    for (int i = 1; i <= 9; i++) jc[i] = jc[i - 1] * i;
    int s[11], t[11], a[11], p;
    char ch[3];
    for (int i = 1; i <= 9; i++) {
        scanf("%s", ch);
        if (ch[0] == 'x') s[i] = 9, p = i;
        else s[i] = ch[0] - '0';
        t[i] = i;
    }
    int now = get(s), ed = get(t); st = now;
    q.push((node){p, now});
    memset(d, 0x3f, sizeof(d)); d[now] = 0;
    while (q.size()) {
        p = q.front().p;
        now = q.front().statu;
        if (now == ed) break;
        ha(a, now);
        q.pop();
        if ((p - 1) % 3 != 2) {
            swap(a[p], a[p + 1]);
            int o = get(a);
            if (d[o] > d[now] + 1) d[o] = d[now] + 1, last[o] = now, pre[o] = 'r', q.push((node){p + 1, o});
            swap(a[p], a[p + 1]);
        }
        if ((p - 1) % 3 != 0) {
            swap(a[p], a[p - 1]);
            int o = get(a);
            if (d[o] > d[now] + 1) d[o] = d[now] + 1, last[o] = now, pre[o] = 'l', q.push((node){p - 1, o});
            swap(a[p], a[p - 1]);
        }
        if ((p - 1) / 3 > 0) {
            swap(a[p], a[p - 3]);
            int o = get(a);
            if (d[o] > d[now] + 1) d[o] = d[now] + 1, last[o] = now, pre[o] = 'u', q.push((node){p - 3, o});
            swap(a[p], a[p - 3]);
        }
        if ((p - 1) / 3 < 2) {
            swap(a[p], a[p + 3]);
            int o = get(a);
            if (d[o] > d[now] + 1) d[o] = d[now] + 1, last[o] = now, pre[o] = 'd', q.push((node){p + 3, o});
            swap(a[p], a[p + 3]);
        }
    }
    if (d[ed] == 0x3f3f3f3f) puts("unsolvable");
    else print(ed);
    return 0;
}