[kuangbin带你飞]专题二-搜索进阶-A-Eight

描述

题解

传说中和八皇后一样过分经典的搜索问题，所以网上一查，各种强势题解一大堆，更有丧心病狂者，写了《八数码的八境界》这种深度剖析此问题的 blog，让我不敢再多言此题，毕竟我想不了那么系统，所以，我也就只剩下拿着该大牛的 blog 一饱眼福的任务了……

这个问题核心就是搜索，不过问题的优化十分多样化，对于这道题，我的选择是反向bfs + 打表 + hash，成功 AC，对于其他丧心病狂的解法儿，略懂一二，但是没有耐心全部写一遍了，毕竟那样就太强了，不是我的风格。

这个问题的一个拓展是15-puzzle，对于这个题，用我上边的方法就不行了，简单的搜索优化已经不足以对付其庞大的状态数，需要根据曼哈顿距离进行迭代加深启发式搜索，一般是 A* 算法和 IDA* 算法，具体可以看看《挑战程序设计竞赛2算法和数据结构》最后一章-启发式搜索，有详细代码可以参考，写得十分不错哦~~~

代码

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 362882 + 10;   // 9! + 10

int sta_contor;
int end_contor;
int target[10] = {
  1, 2, 3, 4, 5, 6, 7, 8, 0};

struct
{
    int next;
    char dir;
} vis[MAXN];

int fac[10];

// 记录当前棋盘状态和x的位置
struct node
{
    int a[10];
    int x;
};

// hash-康拓展开式
int hash_cantor(int a[])
{
    int ans = 0;
    for (int i = 0; i < 9; i++)
    {
        int temp = 0;
        for (int j = i + 1; j < 9; j++)
        {
            if (a[j] < a[i])
            {
                temp++;
            }
        }
        ans += temp * fac[8 - i];
    }
    return ans;
}

char str[5] = "durl";
int dir[4][2] = {
  {-1, 0}, {
  1, 0}, {
  0, -1}, {
  0, 1}};

void bfs(node end)
{
    queue<node> Q;
    Q.push(end);
    while (!Q.empty())
    {
        node n = Q.front();
        Q.pop();
        int n_contor = hash_cantor(n.a);
        int pos = n.x;
        for (int i = 0; i < 4; i++)
        {
            int x = n.x / 3;
            int y = n.x % 3;
            int x_ = x + dir[i][0];
            int y_ = y + dir[i][1];
            if (x_ >= 0 && x_ < 3 && y_ >= 0 && y_ < 3)
            {
                int cnt = x_ * 3 + y_;
                swap(n.a[cnt], n.a[pos]);
                n.x = cnt;
                int v = hash_cantor(n.a);
                if (vis[v].next == -1 && v != end_contor)
                {
                    vis[v].dir = str[i];
                    vis[v].next = n_contor;
                    Q.push(n);
                }
                n.x = pos;
                swap(n.a[cnt], n.a[pos]);
            }
        }
    }
}

void init()
{
    fac[0] = fac[1] = 1;
    for (int i = 2; i < 10; i++)
    {
        fac[i] = fac[i - 1] * i;
    }

    for (int i = 0; i < MAXN; i++)
    {
        vis[i].next = -1;
    }

    node end;
    swap(end.a, target);
    end.x = 8;
    end_contor = hash_cantor(end.a);

    bfs(end);
}

void printRes(int n)
{
    while (vis[n].next != -1)
    {
        printf("%c", vis[n].dir);
        n = vis[n].next;
    }
}

int main()
{
    init();

    char s[3];
    while (~scanf("%s", s))
    {
        node star;
        if (s[0] == 'x')
        {
            star.a[0] = 0;
            star.x = 0;
        }
        else
        {
            star.a[0] = s[0] - '0';
        }
        for (int i = 1; i < 9; i++)
        {
            scanf("%s", s);
            if (s[0] == 'x')
            {
                star.x = i;
                star.a[i] = 0;
            }
            else
            {
                star.a[i] = s[0] - '0';
            }
        }

        sta_contor = hash_cantor(star.a);

        if (sta_contor == end_contor)
        {
            printf("\n");
        }
        else if (vis[sta_contor].next != -1)
        {
            printRes(sta_contor);
            printf("\n");
        }
        else
        {
            printf("unsolvable\n");
        }
    }

    return 0;
}

参考

《八数码的八境界》