八数码

八数码难题【BFS/A*/双向广搜】

题目描述

在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例输入

283104765

样例输出

4

提示

样例解释

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

思路

由于只有一组数据，且只需要算出最短路径长度，因此可直接采用朴素BFS。

对于每次的搜索，枚举空白可移动的四个方向，判断是否会出现越界，重复等情况，如果不会，则加入队列。

由于棋盘格局是由字符串给出，要想还原空格的位置需要如下代码

int k = cur.find('0');
int x = k / 3, y = k % 3;

此时，$x,y$ 即为空白的位置。

CODE

int opx[] = {0, 1, 0, -1};
int opy[] = {1, 0, -1, 0};

void solve()
{
    int n = 3;
    string st;   cin >> st;
    string dst = "123456780";
    
    map<string, int> dist;
    queue<string> q;
    q.push(st);
    dist[st] = 0;

    auto bfs = [&]() -> int
    {
        while (!q.empty())
        {
            auto cur = q.front();   q.pop();
            if (cur == dst) return dist[cur];
            int k = cur.find('0');
            int x = k / n, y = k % n;
            for (int i=0;i<4;i++)
            {
                string tmp = cur;
                int xx = x + opx[i], yy = y + opy[i];
                if (xx >= 0 && xx < n && yy >= 0 && yy < n)
                {
                    swap(tmp[k], tmp[xx * n + yy]);
                    if (!dist[tmp])
                    {
                        q.push(tmp);
                        dist[tmp] = dist[cur] + 1;
                    }
                }
            }
        }
        return inf;
    };

    cout << bfs();
}

八数码【A*/双向广搜】

在一个 $3×3$ 的网格中，$1 \sim 8$ 这 $8$ 个数字和一个 x 恰好不重不漏地分布在这 $3×3$ 的网格中。

例如：

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

输入占一行，将 $3×3$ 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。

如果答案不唯一，输出任意一种合法方案即可。

如果不存在解决方案，则输出 unsolvable。

输入样例：

2 3 4 1 5 x 7 6 8

输出样例

ullddrurdllurdruldr

思路

与上题不同的是，需要输出操作路径。

因此，需要用一个unordered_map记录前一个棋盘格局和从前一个棋盘格局到当前棋盘格局的方式。

此外，A*算法的估价函数f采用的是当前棋盘格局到目标棋盘格局每个棋子需要走的曼哈顿距离之和。

CODE

int n = 3;

int f(string s)
{
    int d = 0;
    for (int i=0;i<(int)s.size();i++)
    {
        if (s[i] != 'x')
        {
            int t = s[i] - '1';
            d += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
        }
    }
    return d;
}

int opx[] = {-1, 0, 1, 0};
int opy[] = {0, 1, 0, -1};
char chose[] = {'u', 'r', 'd', 'l'};

string bfs(string st)
{
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> q;
    unordered_map<string, int> dist;
    unordered_map<string, bool> vis;
    unordered_map<string, pair<string, char>> pre;
    string dst = "12345678x";

    q.push({f(st), st});
    dist[st] = 0;
    while (!q.empty())
    {
        auto [_, cur] = q.top(); q.pop();
        if (cur == dst) break;
        if (vis[cur])   continue;
        vis[cur] = true;

        int k = cur.find('x');
        int x = k / 3, y = k % 3;

        for (int i=0;i<4;i++)
        {
            int xx = x + opx[i], yy = y + opy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < n)
            {
                string tmp = cur;
                swap(tmp[x * 3 + y], tmp[xx * 3 + yy]);
                if (!dist.count(tmp) || dist[tmp] > dist[cur] + 1)
                {
                    q.push({dist[cur] + f(tmp), tmp});
                    dist[tmp] = dist[cur] + 1;
                    pre[tmp] = {cur, chose[i]};
                }
            }
        }
    }

    string path = "";
    while (dst != st)
    {
        path += pre[dst].second;
        dst = pre[dst].first;
    }
    return string(rall(path));
}

void solve()
{
    string ch, st;
    for (int i=0;i<n*n;i++)
    {
        cin >> ch;
        st += ch;
    }

    auto chk = [&](string s) -> bool
    {
        int cnt = 0;
        for (int i=0;i<(int)s.size();i++)
        {
            for (int j=i+1;j<(int)s.size();j++)
            {
                if (s[i] != 'x' && s[j] != 'x')
                    cnt += (s[i] > s[j]);
            }
        }
        return (cnt & 1);
    };

    if (chk(st))    puts("unsolvable");
    else    cout << bfs(st);
}