fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <queue>
  6. #define MAX 1000000
  7. using namespace std;
  8. struct node{
  9.     int state[9], num;
  10.     int gScore, hScore, fScore;
  11.     string action;
  12.     node *parent;
  13.     node *child;
  14. //    friend bool operator < (node a,node b) {
  15. //        if (a.fScore==b.fScore) {
  16. //            return a.num>b.num;
  17. //        }
  18. //        return a.fScore>b.fScore;
  19. //    }
  20. };
  21. void swap(int&, int&);
  22. int Sovability(int[]);
  23. int Heuristic(node*);
  24. int Successor(int[],int*,string[]);
  25. node* Reverse(node*);
  26. priority_queue<node*,vector<node*>,greater<node*>> que;
  27. int Goal(int data[]) {
  28.     int i=0;
  29.     while (data[i]==i)
  30.         i++;
  31.     if (i>8)
  32.         return 1;
  33.     return 0;
  34. }
  35.  
  36. int main(int argc, const char * argv[]) {
  37.     string orgdataS;
  38.     node *myNode, *newNode, *Final;
  39.     int nextState[9], orgdataI, i, j, count, times=0;
  40.     string nextAction[4];
  41.  
  42.     Final=new node();
  43.     myNode=new node();
  44.  
  45.     cin >> orgdataS;                                      //Ask the user to input the initial state of a N-puzzle game
  46.     orgdataI=atoi(orgdataS.c_str());                      //String -> Int ->Int[] & Save the initial state
  47.     for (i=8; i>-1; i--) {
  48.         myNode->state[i]=orgdataI%10;
  49.         orgdataI=orgdataI/10;
  50.     }
  51.  
  52.     if (Goal(myNode->state))                              //If it's the goal
  53.         cout << "It is the goal state." << endl;
  54.     else if (Sovability(myNode->state))                                                // check if the given state is solvable
  55.         cout << "No solution!!" << endl;
  56.     else {
  57.         //    myNode->num=num;
  58.         myNode->gScore = 0;                                   //Start to calculate
  59.         myNode->hScore = Heuristic(myNode);                   //hScore is the Manhattan distance of a given state
  60.         myNode->fScore = myNode->gScore + myNode->hScore;
  61.         //    cout << myNode->gScore << " " << myNode->hScore << endl;
  62.         myNode->parent = NULL;
  63.         //    myNode->child = NULL;
  64.         que.push(myNode);
  65.  
  66.         //    num++;
  67.  
  68.         while (!que.empty()) {
  69.  
  70.             myNode = que.top();
  71.             que.pop();
  72.  
  73.             //        cout << myNode->action << endl;
  74.             //        cout << "myNode ";
  75.             //        for (int k=0; k<9; k++) {
  76.             //            cout << myNode->state[k] << " ";
  77.             //        }
  78.             //        cout << endl;
  79.             //        cout << myNode->gScore << " " << myNode->hScore << endl;
  80.  
  81.             if (Goal(myNode->state)) {
  82.                 Final = myNode;
  83.                 break;
  84.             }
  85.  
  86.             count = Successor(myNode->state, nextState, nextAction);
  87.             for (i=0; i<count; i++) {
  88.                 newNode = new node();
  89.  
  90.                 //            cout << nextAction[i] << endl;
  91.                 //            cout << "newNode.state ";
  92.                 for (j=0; j<9; j++){
  93.                     newNode->state[j] = nextState[i*100+j];
  94.                     //                cout << newNode->state[j];
  95.                 }
  96.                 //            cout << endl;
  97.                 //            myNode->child = newNode;
  98.                 newNode->action = nextAction[i];
  99.                 //            newNode->num=num;
  100.                 newNode->gScore = myNode->gScore + 1;
  101.                 newNode->hScore = Heuristic(newNode);
  102.                 newNode->fScore = newNode->gScore + newNode->hScore;
  103.                 newNode->parent = myNode;
  104.                 //            cout << newNode->gScore << " " << newNode->hScore << endl;
  105.                 que.push(newNode);
  106.                 //            num++;
  107.             }
  108.  
  109.             //        cout << "count " << count << endl;
  110.  
  111.         }
  112.  
  113.         if (Final->parent==NULL)
  114.             cout << "No solution!!" << endl;
  115.         else {                                                //Reverse the linked list & print out the actions
  116.             //        cout << "Find the answer!!" << endl;
  117.             Final=Reverse(Final);
  118.             while (Final!=NULL) {
  119.                 cout << "move 0 to " << Final->action <<endl;
  120.                 Final = Final->parent;
  121.                 times++;
  122.             }
  123.             //        times++;
  124.             cout << times;
  125.             cout << " steps" << endl;
  126.  
  127.         }
  128.     }
  129.  
  130.     return 0;
  131. }
  132.  
  133. void swap(int &x, int &y) {
  134.     int temp = x ;
  135.     x = y ;
  136.     y = temp ;
  137. }
  138.  
  139. int Sovability(int data[]) {
  140.     int i, j, disorder=0;
  141.  
  142.     for (i=0; i<9; i++) {
  143.         if (data[i]==0)
  144.             i++;
  145.         for (j=i+1; j<9; j++) {
  146.             if (data[j]==0)
  147.                 j++;
  148.             if (data[i]>data[j])
  149.                 disorder++;
  150.         }
  151.     }
  152.  
  153.     if (disorder%2==1)
  154.         return 1;
  155.     return 0;
  156. }
  157.  
  158. int Successor(int data[], int *nextData, string nextAction[]) {
  159.     int i, j, cor=0, target=0;
  160.  
  161.     for (i=0; i<9; i++)
  162.         if (data[i]==0) {
  163.             if (i-3>=0)
  164.                 cor++;
  165.             if (i+3<9)
  166.                 cor++;
  167.             if (i!=0 && i!=3 && i!=6)
  168.                 cor++;
  169.             if (i!=8 && i!=5 && i!=2)
  170.                 cor++;
  171.             target = i;
  172.             break;
  173.         }
  174. //    cout << "cor&target " << cor << " " << target << endl;
  175.  
  176.     i=0;
  177.     if (target-3>=0) {
  178. //        cout << endl << "move 0 to up" << endl;
  179.         nextAction[i] = "up";
  180.         swap(data[target], data[target-3]);
  181.         for (j=0; j<9; j++) {
  182.             nextData[i*100+j] = data[j];
  183. //            cout << nextData[i*100+j];
  184.         }
  185.         swap(data[target], data[target-3]);
  186.         i++;
  187.     }
  188.     if (target+3<9) {
  189. //        cout << endl  << "move 0 to down" << endl;
  190.         nextAction[i] = "down";
  191.         swap(data[target], data[target+3]);
  192.         for (j=0; j<9; j++) {
  193.             nextData[i*100+j] = data[j];
  194. //            cout << nextData[i*100+j];
  195.         }
  196.         swap(data[target], data[target+3]);
  197.         i++;
  198.     }
  199.     if (target!=0 && target!=3 && target!=6) {
  200. //        cout << endl  << "move 0 to left" << endl;
  201.         nextAction[i] = "left";
  202.         swap(data[target], data[target-1]);
  203.         for (j=0; j<9; j++) {
  204.             nextData[i*100+j] = data[j];
  205. //            cout << nextData[i*100+j];
  206.         }
  207.         swap(data[target], data[target-1]);
  208.         i++;
  209.     }
  210.     if (target!=8 && target!=5 && target!=2) {
  211. //        cout << endl  << "move 0 to right" << endl;
  212.         nextAction[i] = "right";
  213.         swap(data[target], data[target+1]);
  214.         for (j=0; j<9; j++) {
  215.             nextData[i*100+j] = data[j];
  216. //            cout << nextData[i*100+j];
  217.         }
  218.         swap(data[target], data[target+1]);
  219.     }
  220. //    cout << endl;
  221.     return cor;
  222. }
  223.  
  224. int Heuristic(node* data) {
  225.     int i, dis=0 ,cha;
  226.  
  227.     for (i=0; i<9; i++) {
  228.         if (data->state[i]!=0)
  229.             if (data->state[i]!=i%100) {
  230.                 cha=abs(data->state[i]-i);
  231. //                cout << data[i] << " ";
  232.                 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))
  233.                     dis+=3;
  234.                 else if ((data->state[i]==2&&i==6)||(data->state[i]==6&&i==2))
  235.                     dis+=4;
  236.                 else
  237.                     dis=dis+cha/3+cha%3;
  238. //                cout << dis << endl;
  239.             }
  240.     }
  241. //    cout << "dis " << dis << endl;
  242.     return dis;
  243. }
  244.  
  245. node* Reverse(node *data) {
  246.     node *previous = NULL,
  247.          *current = data,
  248.          *preceding = NULL;
  249.  
  250.     while (current != NULL) {
  251.         preceding = current->parent;
  252.         current->parent = previous;
  253.         previous = current;
  254.         current = preceding;
  255.     }
  256.  
  257.     return previous->parent;
  258. }
  259.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
351042678
stdout
copy 
move 0 to right
move 0 to up
move 0 to right
move 0 to down
move 0 to left
move 0 to left
move 0 to up
7 steps
https://ideone.com/rnPk8f
language:
C++ (gcc 8.3)
created:
29 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!