Тема: Пятнашки
Всем привет!
Предположим, что головоломка пятнашки имеет решение. Нужно найти минимальное количество ходов для того, чтобы решить головоломку.
Можно как-нибудь найти ответ не используя перебор всех вариантов перемещения квадратов?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Пятнашки
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Всем привет!
Предположим, что головоломка пятнашки имеет решение. Нужно найти минимальное количество ходов для того, чтобы решить головоломку.
Можно как-нибудь найти ответ не используя перебор всех вариантов перемещения квадратов?
Эту задачу можно эффективно решить используя метод IDA* (http://en.wikipedia.org/wiki/IDA*). Я когда-то решил такую задачу, при этом решение работает достаточно быстро, когда минимальное число перемещений для решения головоломки не превосходит 50. Вот мой исходный код:
#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int pos[16][2] =
{
{3, 3}, {0, 0}, {0, 1}, {0, 2},
{0, 3}, {1, 0}, {1, 1}, {1, 2},
{1, 3}, {2, 0}, {2, 1}, {2, 2},
{2, 3}, {3, 0}, {3, 1}, {3, 2}
};
const int dx[4] = { 0, 1, 0,-1};
const int dy[4] = {-1, 0, 1, 0};
const char c[4] = {'L','D','R','U'};
const int rev[4]= {2, 3, 0, 1};
typedef struct
{
int a[4][4];
} board;
int d[4][4][4][4];
vector <char> res;
board BD;
bool have_answer;
int max_dist;
int ab(int x) {return x >= 0 ? x : -x;}
void calc_d()
{
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 4; j ++)
for (int r = 0; r < 4; r ++)
for (int s = 0; s < 4; s ++)
d[i][j][r][s] = ab(r - i) + ab(s - j);
}
int dist(board X)
{
int res = 0;
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 4; j ++)
if (X.a[i][j] != 0) res += d[i][j][pos[X.a[i][j]][0]][pos[X.a[i][j]][1]];
return res;
}
bool val(int p, int q)
{
if (p >= 0 && q >= 0 && p < 4 && q < 4) return true;
return false;
}
void rec(int g, int x0, int y0, int prev)
{
if (have_answer) return;
int h = dist(BD);
if (h == 0)
{
for (int i = 0; i < res.size(); i ++) printf("%c", res[i]);
printf("\n");
have_answer = true;
return;
}
if (g + h > max_dist) return;
for (int i = 0; i < 4 && !have_answer; i ++)
if (val(x0 + dx[i], y0 + dy[i]) && rev[i] != prev)
{
swap(BD.a[x0][y0], BD.a[x0 + dx[i]][y0 + dy[i]]);
res.push_back(c[i]);
rec(g + 1, x0 + dx[i], y0 + dy[i], i);
res.pop_back();
swap(BD.a[x0][y0], BD.a[x0 + dx[i]][y0 + dy[i]]);
}
}
bool solution()
{
int sum = 0;
int a[16], k = -1;
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 4; j ++)
k ++, a[k] = BD.a[i][j];
for (int i = 0; i < 16; i ++)
for (int j = i; j < 16; j ++)
if (a[j] != 0 && a[j] < a[i]) sum ++;
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 4; j ++)
if (BD.a[i][j] == 0) sum += i + 1;
return (sum % 2) ? false : true;
}
void solve()
{
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 4; j ++)
scanf("%d", &BD.a[i][j]);
if (!solution())
{
printf("This puzzle is not solvable.\n");
return;
}
res.resize(0);
have_answer = false;
int x0, y0;
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 4; j ++)
if (BD.a[i][j] == 0) x0 = i, y0 = j;
int s = dist(BD);
for (int i = s; i <= 50 && !have_answer; i ++)
{
max_dist = i;
rec(0, x0, y0, -1);
}
if (!have_answer)
{
printf("No solutions found.\n");
}
}
int main()
{
calc_d(); int t;
scanf("%d", &t);
for (int it = 1; it <= t; it ++) solve();
return 0;
}
Формат входных и выходных данных соответствует задаче http://uva.onlinejudge.org/index.php?op … oblem=1122
При этом выводится решение, содержащее минимальное число ходов.
Большое спасибо, Dima Sobolev !
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Пятнашки