/*********************************/
/* 知識を用いた探索（８パズル） */
/* coded by Y.Suganuma */
/*********************************/
#include <stdio.h>
#include <queue>
#include <map>
#include <string>
using namespace std;
class Node
{
public:
int dep, est;
string str;
Node (string str1, int dep1, int est1)
{
str = str1; // 状態
dep = dep1; // 深さ
est = est1; // 評価値
}
};
class Depth
{
public:
int dep, est;
string prev;
Depth (string prev1, int dep1, int est1)
{
prev = prev1; // 前の状態
dep = dep1; // 深さ
est = est1; // 評価値
}
};
bool operator< (Node n1, Node n2)
{
bool sw = true;
if (n1.est == n2.est)
sw = (n1.str < n2.str) ? true : false;
else
sw = (n1.est > n2.est) ? true : false;
return sw;
}
/************************/
/* ノードの評価 */
/* dep : 深さ */
/* str : 状態 */
/* goal : 目標状態 */
/* return : 評価値 */
/************************/
int estimation(int dep, string str, string goal)
{
int i1, i2, i3, i4, k1, k2, pi = dep, sw;
char cg[3][3], cn[3][3];
for (i1 = 0; i1 < 9; i1++) {
k1 = i1 / 3;
k2 = i1 - 3 * k1;
cg[k1][k2] = goal.at(i1) - '0';
}
for (i1 = 0; i1 < 9; i1++) {
k1 = i1 / 3;
k2 = i1 - 3 * k1;
cn[k1][k2] = str.at(i1) - '0';
}
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++) {
sw = 1;
for (i3 = 0; i3 < 3 && sw > 0; i3++) {
for (i4 = 0; i4 < 3 && sw > 0; i4++) {
if (cg[i3][i4] == cn[i1][i2]) {
sw = 0;
pi += (abs(i3-i1) + abs(i4-i2));
}
}
}
}
}
if (cn[1][1] != '0')
pi++;
if (cn[0][1] != (cn[0][0]+1)%9)
pi += 2;
if (cn[0][2] != (cn[0][1]+1)%9)
pi += 2;
if (cn[1][2] != (cn[0][2]+1)%9)
pi += 2;
if (cn[2][2] != (cn[1][2]+1)%9)
pi += 2;
if (cn[2][1] != (cn[2][2]+1)%9)
pi += 2;
if (cn[2][0] != (cn[2][1]+1)%9)
pi += 2;
if (cn[1][0] != (cn[2][0]+1)%9)
pi += 2;
if (cn[0][0] != (cn[1][0]+1)%9)
pi += 2;
return pi;
}
/********************************/
/* コマの移動 */
/* str : 現在の状態 */
/* res : 移動後の状態 */
/* return : 移動後の状態数 */
/********************************/
int move(string str, string *res)
{
int k, n = 0;
string str1;
k = str.find("0");
switch(k) {
case 0:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 1:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 2:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 3:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 4:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 5:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 6:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 7:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 8:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;
}
return n;
}
/********************************/
/* 知識を用いた探索（８パズル） */
/* start : 初期状態 */
/* goal : 目標状態 */
/********************************/
void intel(string start, string goal)
{
int i1, n, node1 = 1, node2 = 0, dep = 1, ct = 1, est;
string str, res[4];
priority_queue<Node> p;
map<string, Depth> m;
map<string, Depth>::iterator it;
bool sw;
est = estimation(dep, start, goal);
m.insert(pair<string, Depth>(start, Depth("",dep,est)));
p.push(Node(start,dep,est));
while (!p.empty()) {
str = p.top().str;
dep = p.top().dep;
node2++;
// ゴール
if (str == goal) {
ct = dep;
break;
}
// ゴールでない
// コマを移動し，同じ状態のものがなければキューに追加
else {
p.pop();
n = move(str, res);
for (i1 = 0; i1 < n; i1++) {
sw = true;
est = estimation(dep+1, res[i1], goal);
it = m.find(res[i1]); // 同じ状態か？
if (it != m.end()) {
if (est < ((*it).second).est)
m.erase(it);
else
sw = false;
}
if (sw) {
m.insert(pair<string, Depth>(res[i1], Depth(str,dep+1,est)));
p.push(Node(res[i1], dep+1, est));
node1++;
}
}
}
}
// 結果の出力
printf(" 展開とチェック： %d %d， 最短距離： %d\n", node1, node2, ct);
while (str.length() > 0) {
printf("\n %c %c %c\n", str.at(0), str.at(1), str.at(2));
printf(" %c %c %c\n", str.at(3), str.at(4), str.at(5));
printf(" %c %c %c\n", str.at(6), str.at(7), str.at(8));
it = m.find(str);
str = ((*it).second).prev;
}
}
int main()
{
string goal = "123804765";
printf("例１\n");
string start = "283164705";
intel(start, goal);
printf("例２\n");
start = "216408753";
intel(start, goal);
return 0;
}