本文主要是介绍c语言15-puzzle解法,UVa 10181 15-Puzzle Problem 题解《挑战程序设计竞赛》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
滑动拼图：给定拼图，求解决方案。
4.5开动脑筋智慧搜索
A*与IDA*
滑块拼图问题是否有解的判断方法是，先将表格平铺：
然后计算N=逆序数对之和，e=空白所在的行数。若N+e为偶数，则有解，反之无解，证明在此。
然后估计最优解的下界，对所有非0数字，最理想的情况是表格中其他数字都不存在，不浪费一步避让，一路畅通无阻抵达目标。此时所需的步数为曼哈顿距离
：
之后就是常规的IDA*搜索了。
#include
#include
#include
#include
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
{
for (int x = 0; 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
{
if (i == (prev_direction ^ 1)) // 小三爷，不回头
continue;
int ny = e_y + dy[i];
int nx = e_x + dx[i];
if (ny = 4)
continue;
if (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
{
for (int x = 0; 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
{
for (int x = 0; 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
这篇关于c语言15-puzzle解法,UVa 10181 15-Puzzle Problem 题解《挑战程序设计竞赛》的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
