#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <queue>
#define MAX 1000000
using namespace std;
struct node{
int state[9], num;
int gScore, hScore, fScore;
string action;
node *parent;
node *child;
// friend bool operator < (node a,node b) {
// if (a.fScore==b.fScore) {
// return a.num>b.num;
// }
// return a.fScore>b.fScore;
// }
};
void swap(int&, int&);
int Sovability(int[]);
int Heuristic(node*);
int Successor(int[],int*,string[]);
node* Reverse(node*);
priority_queue<node*,vector<node*>,greater<node*>> que;
int Goal(int data[]) {
int i=0;
while (data[i]==i)
i++;
if (i>8)
return 1;
return 0;
}
int main(int argc, const char * argv[]) {
string orgdataS;
node *myNode, *newNode, *Final;
int nextState[9], orgdataI, i, j, count, times=0;
string nextAction[4];
Final=new node();
myNode=new node();
cin >> orgdataS; //Ask the user to input the initial state of a N-puzzle game
orgdataI=atoi(orgdataS.c_str()); //String -> Int ->Int[] & Save the initial state
for (i=8; i>-1; i--) {
myNode->state[i]=orgdataI%10;
orgdataI=orgdataI/10;
}
if (Goal(myNode->state)) //If it's the goal
cout << "It is the goal state." << endl;
else if (Sovability(myNode->state)) // check if the given state is solvable
cout << "No solution!!" << endl;
else {
// myNode->num=num;
myNode->gScore = 0; //Start to calculate
myNode->hScore = Heuristic(myNode); //hScore is the Manhattan distance of a given state
myNode->fScore = myNode->gScore + myNode->hScore;
// cout << myNode->gScore << " " << myNode->hScore << endl;
myNode->parent = NULL;
// myNode->child = NULL;
que.push(myNode);
// num++;
while (!que.empty()) {
myNode = que.top();
que.pop();
// cout << myNode->action << endl;
// cout << "myNode ";
// for (int k=0; k<9; k++) {
// cout << myNode->state[k] << " ";
// }
// cout << endl;
// cout << myNode->gScore << " " << myNode->hScore << endl;
if (Goal(myNode->state)) {
Final = myNode;
break;
}
count = Successor(myNode->state, nextState, nextAction);
for (i=0; i<count; i++) {
newNode = new node();
// cout << nextAction[i] << endl;
// cout << "newNode.state ";
for (j=0; j<9; j++){
newNode->state[j] = nextState[i*100+j];
// cout << newNode->state[j];
}
// cout << endl;
// myNode->child = newNode;
newNode->action = nextAction[i];
// newNode->num=num;
newNode->gScore = myNode->gScore + 1;
newNode->hScore = Heuristic(newNode);
newNode->fScore = newNode->gScore + newNode->hScore;
newNode->parent = myNode;
// cout << newNode->gScore << " " << newNode->hScore << endl;
que.push(newNode);
// num++;
}
// cout << "count " << count << endl;
}
if (Final->parent==NULL)
cout << "No solution!!" << endl;
else { //Reverse the linked list & print out the actions
// cout << "Find the answer!!" << endl;
Final=Reverse(Final);
while (Final!=NULL) {
cout << "move 0 to " << Final->action <<endl;
Final = Final->parent;
times++;
}
// times++;
cout << times;
cout << " steps" << endl;
}
}
return 0;
}
void swap(int &x, int &y) {
int temp = x ;
x = y ;
y = temp ;
}
int Sovability(int data[]) {
int i, j, disorder=0;
for (i=0; i<9; i++) {
if (data[i]==0)
i++;
for (j=i+1; j<9; j++) {
if (data[j]==0)
j++;
if (data[i]>data[j])
disorder++;
}
}
if (disorder%2==1)
return 1;
return 0;
}
int Successor(int data[], int *nextData, string nextAction[]) {
int i, j, cor=0, target=0;
for (i=0; i<9; i++)
if (data[i]==0) {
if (i-3>=0)
cor++;
if (i+3<9)
cor++;
if (i!=0 && i!=3 && i!=6)
cor++;
if (i!=8 && i!=5 && i!=2)
cor++;
target = i;
break;
}
// cout << "cor&target " << cor << " " << target << endl;
i=0;
if (target-3>=0) {
// cout << endl << "move 0 to up" << endl;
nextAction[i] = "up";
swap(data[target], data[target-3]);
for (j=0; j<9; j++) {
nextData[i*100+j] = data[j];
// cout << nextData[i*100+j];
}
swap(data[target], data[target-3]);
i++;
}
if (target+3<9) {
// cout << endl << "move 0 to down" << endl;
nextAction[i] = "down";
swap(data[target], data[target+3]);
for (j=0; j<9; j++) {
nextData[i*100+j] = data[j];
// cout << nextData[i*100+j];
}
swap(data[target], data[target+3]);
i++;
}
if (target!=0 && target!=3 && target!=6) {
// cout << endl << "move 0 to left" << endl;
nextAction[i] = "left";
swap(data[target], data[target-1]);
for (j=0; j<9; j++) {
nextData[i*100+j] = data[j];
// cout << nextData[i*100+j];
}
swap(data[target], data[target-1]);
i++;
}
if (target!=8 && target!=5 && target!=2) {
// cout << endl << "move 0 to right" << endl;
nextAction[i] = "right";
swap(data[target], data[target+1]);
for (j=0; j<9; j++) {
nextData[i*100+j] = data[j];
// cout << nextData[i*100+j];
}
swap(data[target], data[target+1]);
}
// cout << endl;
return cor;
}
int Heuristic(node* data) {
int i, dis=0 ,cha;
for (i=0; i<9; i++) {
if (data->state[i]!=0)
if (data->state[i]!=i%100) {
cha=abs(data->state[i]-i);
// cout << data[i] << " ";
if ((data->state[i]==2&&i==3)||(data->state[i]==3&&i==2)||(data->state[i]==5&&i==6)||(data->state[i]==6&&i==5))
dis+=3;
else if ((data->state[i]==2&&i==6)||(data->state[i]==6&&i==2))
dis+=4;
else
dis=dis+cha/3+cha%3;
// cout << dis << endl;
}
}
// cout << "dis " << dis << endl;
return dis;
}
node* Reverse(node *data) {
node *previous = NULL,
*current = data,
*preceding = NULL;
while (current != NULL) {
preceding = current->parent;
current->parent = previous;
previous = current;
current = preceding;
}
return previous->parent;
}