八数码难题

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

283104765

样例输出 #1

4

题解

这题是适用于A*算法的一个比较经典的题目，问题在于如何定义估价函数。这里我定义的$h(x)$为当前各个数字到目标位置的曼哈顿距离之和，即

在搜索时不要想着去直接移动数字，不好写代码，可以去移动空位来实现数字的移动。

代码&&注释

#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
int final[] = {-1, 0, 1, 2, 5, 8, 7, 6, 3};
struct node
{
    int state, g, h;
    node(int _state, int _g) // _state状态 _g实际的走的步数
    {
        state = _state;
        g = _g;
        h = 0;
        int tmp = state;
        for (int i = 8; i >= 0; i--) // 算h(x)函数
        {
            int a = tmp % 10; // 分离每一位数字
            tmp /= 10;
            if (a != 0)
                h += abs((i / 3) - (final[a] / 3)) + abs((i % 3) - (final[a] % 3));
            // 算每一位数字到目标位置的曼哈顿距离
        }
    }
};
bool operator<(node x, node y) // A*算法的priority_queue用的
{
    return x.g + x.h > y.g + y.h;
}
priority_queue<node> q;
map<int, bool> vis; // 将9!种排列映射到布尔变量
int main()
{
    int n;
    cin >> n;
    q.push(node(n, 0));
    vis[n] = 1; // 初始状态是一定被访问了的
    while (!q.empty())
    {
        node u = q.top();
        int c[3][3], f = 0, g = 0, n = u.state;
        q.pop();
        if (u.state == 123804765) // 目标状态
        {
            cout << u.g << endl; // 输出步数
            return 0;
        }
        for (int i = 2; i >= 0; i--)
            for (int j = 2; j >= 0; j--) // 把当前的一维状态化为二维矩阵
            {
                c[i][j] = n % 10, n /= 10;
                if (!c[i][j])
                    f = i, g = j; // 找到空位
            }
        for (int i = 0; i < 4; i++) // 上下左右移动空位
        {
            int nx = f + dx[i], ny = g + dy[i], ns = 0;
            if (nx < 0 || ny < 0 || nx > 2 || ny > 2) // 判边界
                continue;
            swap(c[nx][ny], c[f][g]);   // 尝试移动空位
            for (int i = 0; i < 3; i++) // // 把当前的二维矩阵化为一维状态
                for (int j = 0; j < 3; j++)
                    ns = ns * 10 + c[i][j];
            if (!vis.count(ns)) // 查找当前状态是否被遍历过
            {
                vis[ns] = 1;               // 标记
                q.push(node(ns, u.g + 1)); // 扔到priority_queue中
            }
            swap(c[nx][ny], c[f][g]); //把空位再移回来
        }
    }
}

$end$