UVa 10181 15-Puzzle Problem 题解《挑战程序设计竞赛》

UVa 10181 15-Puzzle Problem 

滑动拼图：给定拼图，求解决方案。

4.5开动脑筋智慧搜索 

A*与IDA* 

滑块拼图问题是否有解的判断方法是，先将表格平铺：

然后计算N=逆序数对之和，e=空白所在的行数。若N+e为偶数，则有解，反之无解，证明在此。

然后估计最优解的下界，对所有非0数字，最理想的情况是表格中其他数字都不存在，不浪费一步避让，一路畅通无阻抵达目标。此时所需的步数为曼哈顿距离：

之后就是常规的IDA*搜索了。

#include <iostream>
#include <climits>
#include <string>
#include <algorithm>

using namespace std;

const int dy[4] = {0, 0, +1, -1};
const int dx[4] = {+1, -1, 0, 0};
const int direction[4] = {'R', 'L', 'D', 'U'};
const int MAX_N = 50;
string path;
int T[15][15], e_y, e_x;

// 最优解下界
int h()
{
    int limit = 0;
    for (int y = 0; y < 4; y++)
    {
        for (int x = 0; x < 4; x++)
        {
            if (T[y][x] == 0)
                continue;
            int goal_y = (T[y][x] - 1) / 4;
            int goal_x = (T[y][x] - 1) % 4;
            limit += abs(goal_y - y) + abs(goal_x - x); // 曼哈顿距离
        }
    }
    return limit;
}

bool dfs(int current_steps, int prev_direction, int bound)
{
    int limit = h();
    if (limit == 0)
        return true;
    if (current_steps + limit > bound)
        return false;

    for (int i = 0; i < 4; i++)
    {
        if (i == (prev_direction ^ 1))  // 小三爷，不回头
            continue;

        int ny = e_y + dy[i];
        int nx = e_x + dx[i];
        if (ny < 0 || ny >= 4)
            continue;
        if (nx < 0 || nx >= 4)
            continue;

        path.push_back(direction[i]);
        swap(T[ny][nx], T[e_y][e_x]);
        swap(ny, e_y);
        swap(nx, e_x);
        if (dfs(current_steps + 1, i, bound))
            return true;
        swap(ny, e_y);
        swap(nx, e_x);
        swap(T[ny][nx], T[e_y][e_x]);
        path.pop_back();
    }

    return false;
}

bool ida_star()
{
    for (int limit = h(); limit <= MAX_N; ++limit)
    {
        if (dfs(0, -1, limit))
            return true;
    }
    return false;
}

bool solvable()
{
    int N = 0;
    bool occur[16] = {false};
    for (int y = 0; y < 4; y++)
    {
        for (int x = 0; x < 4; x++)
        {
            if (T[y][x] == 0)
            {
                e_y = y;
                e_x = x;
            }
            else
            {
                N += count(occur + 1, occur + T[y][x], false);
                occur[T[y][x]] = true;
            }
        }
    }
    return ((N + (e_y + 1)) & 1) == 0;  // N + e 为偶数，则当前局面有解，否则无解
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int N;
    scanf("%d", &N);
    while (N--)
    {
        for (int y = 0; y < 4; y++)
        {
            for (int x = 0; x < 4; x++)
            {
                scanf("%d", &T[y][x]);
            }
        }
        path.clear();
        if (!solvable() || !ida_star())
        {
            puts("This puzzle is not solvable.");
        }
        else
        {
            printf("%s\n", path.c_str());
        }
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

Reference

https://amoshyc.github.io/ojsolution-build/uva/p10181.html

 知识共享署名-非商业性使用-相同方式共享：码农场 » UVa 10181 15-Puzzle Problem 题解《挑战程序设计竞赛》