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