八数码问题，最开始是在人工智能基础课上学的，然而我已无力吐槽这门课了，现在我才回想起来原来她当时所讲的open表其实就是栈和队列。而当时那些手算看起来很简单的搜索算法，实际写起来还是会有很多坑的，如果现在再重新学这门课我应该会有很多新的思考和认识吧。

八数码问题

编号为$1-8$的八个正方形滑块被摆成3行3列，其中有一个格子留空。每次可以把与空格相邻的滑块移到空格中，它原来的位置就成了新的空格。给定初始局面和目标局面，计算最少的移动步数。
因为是计算最少移动步数，所以用BFS来搜索比较合适。但是和一般的图搜索不太一样，这里没有显式的结点。可以想到把每一个“状态”看做图的一个结点，然后根据合法的移动方式去扩展其它结点，直到到达目标状态。
还有一个问题是如何标记已经访问过的状态，以避免对同一个结点做多次访问。在显式的图搜索里我们一般会开一个vis数组来标记，但是这里如果要用vis数组的话，要开到九维，$9^9$，这对空间的消耗太大了。于是我们可以考虑用之前提到的哈希，每一个状态对应一个整型数，一共的状态数是$9! = 362880$种。这样我们用一个vis数组就可以表示出来了。
下面的代码是用STL里的set代替vis数组实现判断状态是否已访问过

代码

/*
 *
 * Author : Aincrad
 *
 * Date : Wed 26 Dec 08:39:43 CST 2018
 *
 */

#include <bits/stdc++.h>

using namespace std;

struct Node{
    int d[9];
    int dis;
};
int st[9], ed[9];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
set<int> rec;
int ans;

bool vis(int x){
    int len = rec.size();
    rec.insert(x);
    if((int)rec.size() > len) return false;
    else return true;
}

int Trans(Node& u){
    int sum = 0;
    for(int i = 0; i < 9; i++){
        sum *= 10;
        sum += u.d[i];
    }
    return sum;
}

bool Match(Node& u){
    if(memcmp(u.d, ed, sizeof(u.d)) == 0) return true;
    else return false;
}

void bfs(){
    queue<Node> que;
    Node nd;
    memcpy(nd.d, st, sizeof(nd.d));
    nd.dis = 0;
    que.push(nd);

    while(!que.empty()){
        Node TopItem = que.front();
        que.pop();
        if(Match(TopItem)){
            ans = TopItem.dis;
            break;
        }
        int pos;
        for(int i = 0; i < 9; i++){
            if(TopItem.d[i] == 0){
                pos = i;
                break;
            }
        }
        int x = pos / 3, y = pos % 3;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3){
                Node u;
                memcpy(&u, &TopItem, sizeof(u));
                int p2 = nx * 3 + ny;
                int tmp = u.d[pos];
                u.d[pos] = u.d[p2];
                u.d[p2] = tmp;
                u.dis = TopItem.dis + 1;
                if(!vis(Trans(u))){
                    que.push(u);
                }
            }
        }
    }

}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    for(int i = 0; i < 9; i++){
        cin >> st[i];
    }
    for(int i = 0; i < 9; i++){
        cin >> ed[i];
    }
    bfs();
    cout << ans << endl;

    return 0;
}

打印路径版代码

#include <bits/stdc++.h>

using namespace std;

struct Node{
    int d[9];
    int dis;
    int id;
};
int st[9], ed[9];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
set<int> rec;
int ans, num, ItemId;
int pre[1000000];
Node data[1000000];

void PrintPath(){
    vector<int> vec;
    while(ItemId >= 0){
        vec.push_back(ItemId);
        ItemId = pre[ItemId];
    }
    reverse(vec.begin(), vec.end());
    for(int x : vec){
        int* ptr = data[x].d;
        for(int i = 0; i < 9; i++){
            if((i + 1) % 3 != 0) cout << ptr[i] << " ";
            else cout << ptr[i] << endl;
        }
        cout << endl;
        ItemId = pre[ItemId];
    }
}

bool vis(int x){
    int len = rec.size();
    rec.insert(x);
    if((int)rec.size() > len) return false;
    else return true;
}

int Trans(Node& u){
    int sum = 0;
    for(int i = 0; i < 9; i++){
        sum *= 10;
        sum += u.d[i];
    }
    return sum;
}

bool Match(Node& u){
    if(memcmp(u.d, ed, sizeof(u.d)) == 0) return true;
    else return false;
}

void bfs(){
    queue<Node> que;
    Node nd;
    memcpy(nd.d, st, sizeof(nd.d));
    nd.dis = 0;
    nd.id = num++;
    que.push(nd);
    data[nd.id] = nd;

    while(!que.empty()){
        Node TopItem = que.front();
        que.pop();
        if(Match(TopItem)){
            ans = TopItem.dis;
            ItemId = TopItem.id;
            break;
        }
        int pos;
        for(int i = 0; i < 9; i++){
            if(TopItem.d[i] == 0){
                pos = i;
                break;
            }
        }
        int x = pos / 3, y = pos % 3;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3){
                Node u;
                memcpy(&u, &TopItem, sizeof(u));
                int p2 = nx * 3 + ny;
                int tmp = u.d[pos];
                u.d[pos] = u.d[p2];
                u.d[p2] = tmp;
                u.dis = TopItem.dis + 1;
                if(!vis(Trans(u))){
                    u.id = num++;
                    pre[u.id] = TopItem.id;
                    data[u.id] = u;
                    que.push(u);
                }
            }
        }
    }

}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    num = 0;
    ans = -1;
    memset(pre, -1, sizeof(pre));

    for(int i = 0; i < 9; i++){
        cin >> st[i];
    }
    for(int i = 0; i < 9; i++){
        cin >> ed[i];
    }
    bfs();
    PrintPath();
    cout << "Steps: " << ans << endl;

    return 0;
}