算法搜索

滑动谜题和八数码

字数统计: 4.4k字   |   阅读时长: 23分
, ,

$0 置换群理论判定可行性

原理

算法基于置换群的理论，Ref : 组合数学5-群论

涉及到奇置换，偶置换，循环，对换的概念

  • 奇置换：一个置换拆成的对换个数是奇数
  • 偶置换：一个置换拆成的对换个数是偶数

算法

  • 首先将初始状态和目标状态 0 归位到右下角，通过与相邻元素交换的方式移动 0 ，按照先往右走再往下走的顺序回到右下角
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    void change_zero(vector<vector<int>>& s)
    {
        // 将 s 中的 0 交换至右下角
        int N = s.size();
        int M = s.size();
        int x = -1,y = -1;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < M; ++j)
            {
                if(s[i][j] == 0)
                {
                    x = i;
                    y = j;
                    break;
                }
            }
        while(x < M - 1)
        {
            swap(s[x][y], s[x + 1][y]);
            ++x;
        }
        while(y < N - 1)
        {
            swap(s[x][y], s[x][y + 1]);
            ++y;
        }
    }

将 0 归位后，棋盘的状态与 组合数学5-群论 中的例题是一个形式了。以下算法与例题中使用的是一致的。

  • 记录棋盘初始状态上各个数字的位置

    1
    2
    3
    4
    5
    6
    7
    8
    vector<int> idx_i(N * N, -1);
    vector<int> idx_j(N * N, -1);
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            idx_i[s[i][j]] = i;
            idx_j[s[i][j]] = j;
        }

  • 考察剩余位置，对于每个 (i, j) 若 s[i][j] != t[i][j] 则进行响应交换，计一次对换

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int swap_cnt = 0;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            if(s[i][j] == t[i][j])
                continue;
            int a = s[i][j];
            int x = idx_i[t[i][j]];
            int y = idx_j[t[i][j]];
            swap(s[i][j], s[idx_i[t[i][j]]][idx_j[t[i][j]]]);
            idx_i[a] = x;
            idx_j[a] = y;
            ++swap_cnt;
        }

判定：
由于只能 0 与相邻数交换，因此对于已经将 0 归位后的 s 和 t

  • s 到 t 记录的对换次数是偶数，则有解，否则无解

数字华容道可行性: 108. 奇数码问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void change_zero(vector<vector<int>>& s)
{
    // 将 s 中的 0 交换至右下角
    int N = s.size();
    int x = -1,y = -1;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            if(s[i][j] == 0)
            {
                x = i;
                y = j;
                break;
            }
        }
    while(x < N - 1)
    {
        swap(s[x][y], s[x + 1][y]);
        ++x;
    }
    while(y < N - 1)
    {
        swap(s[x][y], s[x][y + 1]);
        ++y;
    }
}

bool check(vector<vector<int>>& s, vector<vector<int>>& t)
{
    int N = s.size();
    change_zero(s);
    change_zero(t);
    vector<int> idx_i(N * N, -1);
    vector<int> idx_j(N * N, -1);
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            idx_i[s[i][j]] = i;
            idx_j[s[i][j]] = j;
        }
    int swap_cnt = 0;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            if(s[i][j] == t[i][j])
                continue;
            int a = s[i][j];
            int x = idx_i[t[i][j]];
            int y = idx_j[t[i][j]];
            swap(s[i][j], s[idx_i[t[i][j]]][idx_j[t[i][j]]]);
            idx_i[a] = x;
            idx_j[a] = y;
            ++swap_cnt;
        }
    return (swap_cnt & 1) == 0;
}

int main()
{
    int N;
    while(cin >> N)
    {
        vector<vector<int>> s(N, vector<int>(N, -1));
        vector<vector<int>> t(N, vector<int>(N, -1));
        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < N; ++j)
                cin >> s[i][j];
        }
        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < N; ++j)
                cin >> t[i][j];
        }
        if(check(s, t))
            cout << "TAK" << endl;
        else
            cout << "NIE" << endl;
    }
}

另：可以考察将 0 去掉后构成的排列的逆序对个数。如果 s 和 t 将 0 去掉后的逆序对个数的奇偶性相同，则有解，否则无解。

$1 773. 滑动谜题

算法0: 可行性判定: 置换群理论

与第 0 小节的理论和算法相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void change_zero(vector<int>& s)
{
    // 将 s 中的 0 交换至右下角
    int zero_idx = -1;
    for(int i = 0; i < N * M; ++i)
    {
        if(s[i] == 0)
        {
            zero_idx = i;
            break;
        }
    }
    while((zero_idx % M) < M - 1)
    {

        swap(s[zero_idx + 1], s[zero_idx]);
        ++zero_idx;
    }
    while(zero_idx / M < N - 1)
    {
        swap(s[zero_idx + M], s[zero_idx]);
        zero_idx += M;
    }
}

bool check(vector<int> s, vector<int> t)
{
    change_zero(s);
    vector<int> idx(6, 0);
    for(int i = 0; i < 6; ++i)
        idx[s[i]] = i;
    int swap_cnt = 0;
    for(int i = 0; i < 5; ++i)
    {
        if(s[i] == t[i])
            continue;
        int a = s[i];
        int p = idx[t[i]];
        swap(s[i], s[idx[t[i]]]);
        idx[t[i]] = i;
        idx[a] = p;
        ++swap_cnt;
    }
    return (swap_cnt & 1) == 0;
}

算法1: 基础DFS

状态设计和状态压缩

谜题共 6 个位置，因此总的谜题状态有 $6!$ 种。因为位置只有 6 个，可以将状态压缩后表示成一个整数。

例如下面的状态可以表示为 423150

1
2
4 2 3 
1 5 0

对应的求状态压缩的过程

1
2
3
4
5
6
7
8
9
int s = 0;
for(int i = 0; i < N; ++i)
    for(int j = 0; j < M; ++j)
    {
        s *= 10;
        s += board[i][j];
        if(board[i][j] == 0)
            zero_idx = _idx(i, j);
    }

状态转移

状态转移时共有 4 个方向：

1
2
// 右，左，下，上
int d[4] = {1, -1, M, -M};

step1： 找到当前状态 0 的位置 (可以通过函数参数带着)

step2： 枚举 4 个方向，求出下一个 0 的位置

二维转一维后，获得新位置并判断是否出界的写法

1
2
3
4
5
6
7
for(int i = 0; i < 4; ++i)
{
    int nxt_zero_idx = zero_idx + d[i];
    if(nxt_zero_idx >= M * N || nxt_zero_idx < 0 || (nxt_zero_idx / M != zero_idx / M && nxt_zero_idx % M != zero_idx % M))
        continue;
    ...
}

step3: 交换当前状态 0 的位置和新位置对应的数字

1
2
3
4
5
6
7
int _swap(int s, int zero_idx, int nxt_zero_idx)
{
    int digit = (s / (int)pow(10, N * M - nxt_zero_idx)) % 10;
    int ans = s - digit * pow(10, N * M - nxt_zero_idx);
    ans += digit * pow(10, N * M - zero_idx);
    return ans;
}

基础 DFS

1
void dfs(int s, const int t, int zero_idx, int deep, int& ans)

基础剪枝

虽然 $2 \times 3$ 情况下状态只有 720 个，但状态间的边数很大，不减枝不可以。

1
2
if(deep >= ans)
    return;

公用代码

以下代码在各个算法中是公用的，统一贴在这里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int N = 2, M = 3;

void change_zero(vector<int>& s)
{
    // 将 s 中的 0 交换至右下角
    int zero_idx = -1;
    for(int i = 0; i < N * M; ++i)
    {
        if(s[i] == 0)
        {
            zero_idx = i;
            break;
        }
    }
    while((zero_idx % M) < M - 1)
    {

        swap(s[zero_idx + 1], s[zero_idx]);
        ++zero_idx;
    }
    while(zero_idx / M < N - 1)
    {
        swap(s[zero_idx + M], s[zero_idx]);
        zero_idx += M;
    }
}

bool check(vector<int> s, vector<int> t)
{
    change_zero(s);
    vector<int> idx(6, 0);
    for(int i = 0; i < 6; ++i)
        idx[s[i]] = i;
    int swap_cnt = 0;
    for(int i = 0; i < 5; ++i)
    {
        if(s[i] == t[i])
            continue;
        int a = s[i];
        int p = idx[t[i]];
        swap(s[i], s[idx[t[i]]]);
        idx[t[i]] = i;
        idx[a] = p;
        ++swap_cnt;
    }
    return (swap_cnt & 1) == 0;
}

int fac(int N)
{
    int ans = 1;
    for(int i = 2; i <= N; ++i)
        ans *= i;
    return ans;
}

int _idx(int x, int y)
{
    return x * M + y;
}

代码

1
2
当谜题有解时速度很快(但是根基础BFS比还是弱)，基础剪枝还是有作用的
但是当谜题无解的时候，基础剪枝相当于没有，超时

增加可行性判定后，在保证有解后 DFS 算法可行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int start = 0;
        vector<int> start_vec(6, -1);
        int zero_idx = -1;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < M; ++j)
            {
                start *= 10;
                start += board[i][j];
                start_vec[_idx(i, j)] = board[i][j];
                if(board[i][j] == 0)
                    zero_idx = _idx(i, j);
            }
        if(!check(start_vec, vector<int>{1,2,3,4,5,0}))
            return -1;
        const int n_states = fac(N * M); // 6! 种状态
        int ans = n_states;
        int end = 123450;
        visited = vector<bool>(543211, false);
        visited[start] = true;
        dfs(start, end, zero_idx, 0, ans);
        if(ans == n_states)
            return -1;
        return ans;
    }

private:
    // 右，左，下，上
    int d[4] = {1, -1, M, -M};
    vector<bool> visited;

    int _swap(int s, int zero_idx, int nxt_zero_idx)
    {
        int digit = (s / (int)pow(10, 5 - nxt_zero_idx)) % 10;
        int ans = s - digit * pow(10, 5 - nxt_zero_idx);
        ans += digit * pow(10, 5 - zero_idx);
        return ans;
    }

    void dfs(int s, const int t, int zero_idx, int deep, int& ans)
    {
        if(deep >= ans)
            return;
        if(s == t)
        {
            ans = min(ans, deep);
            return;
        }
        for(int i = 0; i < 4; ++i)
        {
            int nxt_zero_idx = zero_idx + d[i];
            if(nxt_zero_idx >= M * N || nxt_zero_idx < 0 || (nxt_zero_idx / M != zero_idx / M && nxt_zero_idx % M != zero_idx % M))
                continue;
            // s -> 交换 nxt_zero_idx 和 zero_idx 位置的数字 -> s'
            int nxt = _swap(s, zero_idx, nxt_zero_idx);
            if(visited[nxt])
                continue;
            visited[nxt] = true;
            dfs(nxt, t, nxt_zero_idx, deep + 1, ans);
            visited[nxt] = false;
        }
    }
};

算法2: 基础BFS

状态设计

状态设计与基础 DFS 中基本一样，至是将一些通过函数参数传递的数据放到状态结构体中，便于压队。

1
2
3
4
5
6
7
struct State
{
    int s;
    int d;
    int zero_idx;
    State(int s, int d, int i):s(s), d(d),zero_idx(i){}
};

状态转移

状态转移与基础 DFS 中的做法一致。

代码

BFS 比 DFS 快很多，原因：

  • BFS 中每个状态最多访问一次(一次入队一次出队)。
  • DFS 中每个状态只是在当前搜索路径中最多访问一次。当发生回溯，搜索路径变了，则以前访问过的状态可能会被再次访问。仅仅一个基础剪枝 if(deep >= min_deep) return; 作用有限。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int start = 0;
        vector<int> start_vec(6, -1);
        int zero_idx = -1;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < M; ++j)
            {
                start *= 10;
                start += board[i][j];
                start_vec[_idx(i, j)] = board[i][j];
                if(board[i][j] == 0)
                    zero_idx = _idx(i, j);
            }
        if(!check(start_vec, vector<int>{1,2,3,4,5,0}))
            return -1;
        int end = 123450;
        State s(start, 0, zero_idx);
        return bfs(s, end);
    }

private:
    // 右，左，下，上
    int d[4] = {1, -1, M, -M};

    struct State
    {
        int s;
        int d;
        int zero_idx;
        State(int s, int d, int i):s(s), d(d),zero_idx(i){}
    };

    int bfs(State s, int t)
    {
        queue<State> q;
        q.push(s);
        vector<bool> visited(543211, false);
        visited[s.s] = true;
        while(!q.empty())
        {
            State cur = q.front();
            q.pop();
            if(cur.s == t)
                return cur.d;
            for(int i = 0; i < 4; ++i)
            {
                int nxt_zero_idx = cur.zero_idx + d[i];
                if(nxt_zero_idx >= M * N || nxt_zero_idx < 0 || (nxt_zero_idx / M != cur.zero_idx / M && nxt_zero_idx % M != cur.zero_idx % M))
                    continue;
                int nxt_s = _swap(cur.s, cur.zero_idx, nxt_zero_idx);
                if(visited[nxt_s])
                    continue;
                visited[nxt_s] = true;
                State nxt(nxt_s, cur.d + 1, nxt_zero_idx);
                q.push(nxt);
            }
        }
        return -1;
    }

    int _swap(int s, int zero_idx, int nxt_zero_idx)
    {
        int digit = (s / (int)pow(10, 5 - nxt_zero_idx)) % 10;
        int ans = s - digit * pow(10, 5 - nxt_zero_idx);
        ans += digit * pow(10, 5 - zero_idx);
        return ans;
    }
};

算法3: Astar

3.1 优先级队列 BFS

因为状态转移的边权都是 1. 单纯用优先级队列 BFS 必然不好。但是如果有启发函数的话，可以考虑尝试。

3.2 启发函数

1
2
1 2 3   3 5 4
4 5 0   0 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int h(int s, int t)
{
    int ans = 0;
    for(int i = 0; i < 6; ++i)
    {
        int digit = (s / (int)pow(10, i)) % 10;
        if(digit == 0)
            continue;
        // i 要移动到 v
        int v = -1;
        for(int j = 0; j < 6; ++j)
        {
            int digit2 = (t / (int)pow(10, j)) % 10;
            if(digit2 == digit)
            {
                v = j;
                break;
            }
        }
        ans += (abs(v / 3 - i / 3) + abs(v % 3 - i % 3));
    }
    return ans;
}

3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int start = 0;
        vector<int> start_vec(6, -1);
        int zero_idx = -1;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < M; ++j)
            {
                start *= 10;
                start += board[i][j];
                start_vec[_idx(i, j)] = board[i][j];
                if(board[i][j] == 0)
                    zero_idx = _idx(i, j);
            }
        if(!check(start_vec, vector<int>{1,2,3,4,5,0}))
            return -1;
        int end = 123450;
        State s(start, 0, zero_idx, h(start, end));
        return bfs(s, end);
    }

private:
    // 右，左，下，上
    int d[4] = {1, -1, M, -M};

    struct State
    {
        int s;
        int d;
        int zero_idx;
        int h;
        State(int s, int d, int i, int h):s(s), d(d),zero_idx(i),h(h){}
    };

    struct Cmp
    {
        bool operator()(const State& s1, const State& s2) const
        {
            return s1.d + s1.h > s2.d + s2.h;
        }
    };

    int bfs(State s, int t)
    {
        priority_queue<State, vector<State>, Cmp> q;
        q.push(s);
        vector<bool> visited(543211, false);
        while(!q.empty())
        {
            State cur = q.top();
            q.pop();
            if(cur.s == t)
                return cur.d;
            if(visited[cur.s])
                continue;
            visited[cur.s] = true;
            for(int i = 0; i < 4; ++i)
            {
                int nxt_zero_idx = cur.zero_idx + d[i];
                if(nxt_zero_idx >= M * N || nxt_zero_idx < 0 || (nxt_zero_idx / M != cur.zero_idx / M && nxt_zero_idx % M != cur.zero_idx % M))
                    continue;
                int nxt_s = _swap(cur.s, cur.zero_idx, nxt_zero_idx);
                if(visited[nxt_s])
                    continue;
                State nxt(nxt_s, cur.d + 1, nxt_zero_idx, h(nxt_s, t));
                q.push(nxt);
            }
        }
        return -1;
    }

    int h(int s, int t)
    {
        int ans = 0;
        for(int i = 0; i < 6; ++i)
        {
            int digit = (s / (int)pow(10, i)) % 10;
            if(digit == 0)
                continue;
            // i 要移动到 v
            int v = -1;
            for(int j = 0; j < 6; ++j)
            {
                int digit2 = (t / (int)pow(10, j)) % 10;
                if(digit2 == digit)
                {
                    v = j;
                    break;
                }
            }
            ans += (abs(v / 3 - i / 3) + abs(v % 3 - i % 3));
        }
        return ans;
    }

    int _swap(int s, int zero_idx, int nxt_zero_idx)
    {
        int digit = (s / (int)pow(10, 5 - nxt_zero_idx)) % 10;
        int ans = s - digit * pow(10, 5 - nxt_zero_idx);
        ans += digit * pow(10, 5 - zero_idx);
        return ans;
    }
};

算法4: IDAstar

4.1 迭代加深

基础 DFS 性能相比 BFS 较弱，可能是因为答案一般会出现在浅层。因此可以考虑将基础 DFS 改成迭代加深尝试。

1
2
当确定有解的时候。迭代加深可以很快出解，说明答案确实都出现在浅层。
但是迭代加深还是基于 DFS 的，发生回溯后状态还是可能会重复访问的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int start = 0;
        vector<int> start_vec(6, -1);
        int zero_idx = -1;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < M; ++j)
            {
                start *= 10;
                start += board[i][j];
                start_vec[_idx(i, j)] = board[i][j];
                if(board[i][j] == 0)
                    zero_idx = _idx(i, j);
            }
        if(!check(start_vec, vector<int>{1,2,3,4,5,0}))
            return -1;
        // 确定有解
        int end = 123450;
        visited = vector<bool>(543211, false);
        visited[start] = true;
        int depth = 0;
        while(!dfs(start, end, zero_idx, 0, depth))
        {
            ++depth;
            visited.assign(543211, false);
            visited[start] = true;
        }
        return depth;
    }

private:
    // 右，左，下，上
    int d[4] = {1, -1, M, -M};
    vector<bool> visited;

    int _swap(int s, int zero_idx, int nxt_zero_idx)
    {
        int digit = (s / (int)pow(10, 5 - nxt_zero_idx)) % 10;
        int ans = s - digit * pow(10, 5 - nxt_zero_idx);
        ans += digit * pow(10, 5 - zero_idx);
        return ans;
    }

    bool dfs(int s, const int t, int zero_idx, int deep, const int max_deep)
    {
        if(deep > max_deep)
            return false;
        if(s == t)
        {
            return true;
        }
        for(int i = 0; i < 4; ++i)
        {
            int nxt_zero_idx = zero_idx + d[i];
            if(nxt_zero_idx >= M * N || nxt_zero_idx < 0 || (nxt_zero_idx / M != zero_idx / M && nxt_zero_idx % M != zero_idx % M))
                continue;
            // s -> 交换 nxt_zero_idx 和 zero_idx 位置的数字 -> s'
            int nxt = _swap(s, zero_idx, nxt_zero_idx);
            if(visited[nxt])
                continue;
            visited[nxt] = true;
            if(dfs(nxt, t, nxt_zero_idx, deep + 1, max_deep))
                return true;
            visited[nxt] = false;
        }
        return false;
    }
};

4.2 IDAstar

在迭代加深的基础上只做下面这一处修改

1
2
if(deep + h(s, t) > max_deep)
    return false;
1
2
IDAstar 依然是要保证有解的，不然无法返回(基础 DFS 和基于基础DFS的迭代加深当然也要保证有解)
BFS 和 Astar 在无解的时候也可以正确返回

$2 179. 八数码

基于滑动谜题的各种分析和尝试，直接写终极解法:

  • 置换群理论判断有解
  • 状态压缩: 用 ll 表示 $3 \times 3$ 共 9 位的状态, unordered_set<ll> visited;
  • IDAstar
  • 曼哈顿距离估价函数 h(s) := s 中各个数字到终态的对应数字的曼哈顿距离之和，不算0
  • 曼哈顿距离预处理: dist[i][j] := i,j 之间的曼哈顿距离
  • 终态各个数字的下标预处理: idx_end[i] := 终态中 i 数字所在的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
#include <cmath>

using namespace std;

using ll = long long;

const int N = 3;
const int M = 3;
const int L = N * M;

// “u”、“d”、“l”、“r”
int d[4] = {-M, M, -1, 1};
string ops = "udlr";
unordered_set<ll> visited;
vector<int> idx_end;
vector<vector<int>> dist;

void _swap(ll& s, int x, int y)
{
    // 交换 x, y 元素
    x = L - 1 - x;
    y = L - 1 - y;
    ll digit = (s / (ll)pow(10, x)) % 10;
    ll digit2 = (s / (ll)pow(10, y)) % 10;
    s -= digit * (ll)pow(10, x);
    s -= digit2 * (ll)pow(10, y);
    s += digit * (ll)pow(10, y);
    s += digit2 * (ll)pow(10, x);
}

void change_zero(ll& s, int zero_idx)
{
    int x = zero_idx / M;
    int y = zero_idx % M;
    while(y < M - 1)
    {
        _swap(s, zero_idx, zero_idx + 1);
        ++y;
        ++zero_idx;
    }
    while(x < N - 1)
    {
        _swap(s, zero_idx, zero_idx + M);
        ++x;
        zero_idx += M;
    }
}

int get_digit(ll s, int i)
{
    return (s / (ll)pow(10, (L - 1 - i))) % 10;
}

bool check(ll s, ll t, int zero_idx)
{
    change_zero(s, zero_idx);
    vector<int> idx(L, -1);
    idx_end.assign(L, -1);
    for(int i = 0; i < L; ++i)
    {
        idx[get_digit(s, i)] = i;
        idx_end[get_digit(t, i)] = i;
    }
    int swap_cnt = 0;
    for(int i = 0; i < L; ++i)
    {
        ll a = get_digit(s, i);
        ll b = get_digit(t, i);
        if(a == b)
            continue;
        int j = idx[b];
        _swap(s, i, j);
        idx[b] = i;
        idx[a] = j;
        ++swap_cnt;
    }
    return (swap_cnt & 1) == 0;
}

int h(ll s)
{
    int ans = 0;
    for(int i = 0; i < L; ++i)
    {
        int digit = get_digit(s, i);
        if(digit == 0)
            continue;
        int j = idx_end[digit];
        ans += dist[i][j];
    }
    return ans;
}

bool dfs(ll s, const ll t, int zero_idx, int deep, const int max_depth, string& path)
{
    if(deep + h(s) > max_depth)
        return false;
    if(s == t)
        return true;
    for(int i = 0; i < 4; ++i)
    {
        int nxt_zero_idx = zero_idx + d[i];
        if(nxt_zero_idx < 0 || nxt_zero_idx >= L || (nxt_zero_idx / M != zero_idx / M && nxt_zero_idx % M != zero_idx % M))
            continue;
        ll nxt_s = s;
        _swap(nxt_s, nxt_zero_idx, zero_idx);
        if(visited.count(nxt_s))
            continue;
        visited.insert(nxt_s);
        path += ops[i];
        if(dfs(nxt_s, t, nxt_zero_idx, deep + 1, max_depth, path))
            return true;
        path.pop_back();
        visited.erase(nxt_s);
    }
    return false;
}

void init_manhattan()
{
    dist.assign(L, vector<int>(L, -1));
    for(int i = 0; i < L; ++i)
    {
        for(int j = 0; j < L; ++j)
        {
            dist[i][j] = (abs(i / M - j / M) + abs(i % M - j % M));
        }
    }
}

int main()
{
    // fstream fin("test/prob179.test");
    ll end = 123456780;
    ll start = 0;
    int zero_idx = -1;
    for(int i = 0; i < L; ++i)
    {
        char ch;
        cin >> ch;
        start *= 10;
        if(ch == 'x')
        {
            zero_idx = i;
            continue;
        }
        int num = ch - '0';
        start += num;
    }
    if(!check(start, end, zero_idx))
    {
        cout << "unsolvable" << endl;
        return 0;
    }
    init_manhattan();
    int depth = 0;
    visited.insert(start);
    string path;
    while(!dfs(start, end, zero_idx, 0, depth, path))
    {
        ++depth;
        path = "";
        visited.clear();
        visited.insert(start);
    }
    cout << path << endl;
}
Share