API tools faq
paste
Guest User

Eightpuzzle Assignment

a guest
Feb 10th, 2014
128
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.00 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <queue>
  5. #include <stdlib.h>
  6. using namespace std;
  7.  
  8. class State{
  9. private:
  10.     vector<vector<int>> cState;
  11.     vector<int> loc;
  12.    
  13. public:
  14.     int cost;
  15.     int heuristic;
  16.     int total;
  17.    
  18.     State(vector<vector<int>> sState,int costval){
  19.         cState = sState;
  20.         loc = findLoc(cState);
  21.         cost = costval;
  22.         cout<<"in constructor "<<cost<<endl;
  23.     }
  24.    
  25.     State(vector<vector<int>> sState){
  26.         cState = sState;
  27.         loc = findLoc(cState);
  28.     }
  29.    
  30.     void setHeuristic(State goal){
  31.         int i,j;
  32.         int h=0;
  33.         for(i=0;i<3;i++){
  34.             for(j=0;j<3;j++){
  35.                 if(this->cState[i][j]!=goal.cState[i][j]) h++;
  36.             }
  37.         }
  38.         this->heuristic = h;
  39.     }
  40.    
  41.     void setfN(State state){
  42.             int total = state.cost + state.heuristic;
  43.             this->total = total;
  44.     }
  45.    
  46.     vector<int> findLoc(vector<vector<int>> state){
  47.         int i,j;
  48.         vector<int> loc;
  49.         loc.resize(2);
  50.         for(i=0;i<3;i++){
  51.             for(j=0;j<3;j++){
  52.                 if(state[i][j]==0){loc[0] =i; loc[1] =j; return loc;}
  53.             }
  54.         }
  55.         loc[0] = 999;
  56.         loc[1] = 999;
  57.         return loc;
  58.     }
  59.    
  60.     bool isGoal(State gState){
  61.         int i,j;
  62.         for(i=0;i<3;i++){
  63.             for(j=0;j<3;j++){
  64.                 if(cState[i][j] != gState.cState[i][j]){return false;}
  65.             }
  66.         }
  67.         return true;
  68.     }
  69.    
  70.     void printState(State state){
  71.         int i,j;
  72.         for(i =0; i<3; i++){
  73.             for(j=0; j<3; j++){
  74.                 cout<<state.cState[i][j];
  75.             }
  76.             cout<<endl;
  77.         }
  78.         cout<<"cost= "<<state.cost;
  79.         cout<<"heuristic= "<<state.heuristic;
  80.         cout<<"total= "<<state.total<<endl;
  81.        
  82.     }
  83.    
  84.     vector<State> nextState(State astate){
  85.         int row = astate.loc[0];
  86.         int col = astate.loc[1];
  87.         int cost = astate.cost;
  88.         cout<<"printing astate"<<endl;
  89.         astate.printState(astate);
  90.         cout<<"in next state"<<cost<<endl;
  91.         vector<vector<int>> nState;
  92.         vector<State> states;
  93.         int temp;
  94.         if(row==0){
  95.             if(col==0){
  96.                 nState = astate.cState;
  97.                 temp = nState[0][1];
  98.                 nState[0][0] = temp;
  99.                 nState[0][1] = 0;
  100.                 State state(nState,cost+2);
  101.                 state.printState(state);
  102.                 states.push_back(state);
  103.                
  104.                 nState = astate.cState;
  105.                 temp = nState[1][0];
  106.                 nState[0][0] = temp;
  107.                 nState[1][0] = 0;
  108.                 State state1(nState,cost+2);
  109.                 states.push_back(state1);
  110.                 return states;
  111.             }
  112.             else if(col==2){
  113.                 nState = astate.cState;
  114.                 temp = nState[0][1];
  115.                 nState[0][2] = temp;
  116.                 nState[0][1] = 0;
  117.                 State state(nState,cost+2);
  118.                 states.push_back(state);
  119.                
  120.                 nState = astate.cState;
  121.                 temp = nState[1][2];
  122.                 nState[0][2] = temp;
  123.                 nState[1][2] = 0;
  124.                 State state1(nState,cost+2);
  125.                 states.push_back(state1);
  126.                 return states;
  127.             }
  128.             else{
  129.                 nState = astate.cState;
  130.                 temp = nState[0][0];
  131.                 nState[0][0] = 0;
  132.                 nState[0][1] = temp;
  133.                 State state(nState,cost+2);
  134.                 states.push_back(state);
  135.                
  136.                 nState = astate.cState;
  137.                 temp = nState[0][2];
  138.                 nState[0][2] = 0;
  139.                 nState[0][1] = temp;
  140.                 State state1(nState,cost+2);
  141.                 states.push_back(state1);
  142.                
  143.                 nState = astate.cState;
  144.                 temp = nState[1][1];
  145.                 nState[1][1] = 0;
  146.                 nState[0][1] = temp;
  147.                 State state2(nState,cost+2);
  148.                 states.push_back(state2);
  149.                
  150.                 return states;
  151.             }
  152.         }
  153.         else if(row==2){
  154.             if(col==0){
  155.                 nState = astate.cState;
  156.                 temp = nState[1][0];
  157.                 nState[1][0] = 0;
  158.                 nState[2][0] = temp;
  159.                 State state(nState,cost+2);
  160.                 states.push_back(state);
  161.                
  162.                 nState = astate.cState;
  163.                 temp = nState[2][1];
  164.                 nState[2][0] = temp;
  165.                 nState[2][1] = 0;
  166.                 State state1(nState,cost+2);
  167.                 states.push_back(state1);
  168.                
  169.                 return states;
  170.                
  171.             }
  172.             else if(col==2){
  173.                 nState = astate.cState;
  174.                 temp = nState[1][2];
  175.                 nState[2][2] = temp;
  176.                 nState[1][2] = 0;
  177.                 State state(nState,cost+2);
  178.                 states.push_back(state);
  179.                
  180.                 nState = astate.cState;
  181.                 temp = nState[2][1];
  182.                 nState[2][2] = temp;
  183.                 nState[2][1] = 0;
  184.                 State state1(nState,cost+2);
  185.                 states.push_back(state1);
  186.                
  187.                 return states;
  188.             }
  189.             else{
  190.                 nState = astate.cState;
  191.                 temp = nState[2][0];
  192.                 nState[2][1] = temp;
  193.                 nState[2][0] = 0;
  194.                 State state(nState,cost+2);
  195.                 states.push_back(state);
  196.                
  197.                 nState = astate.cState;
  198.                 temp = nState[2][2];
  199.                 nState[2][2] = 0;
  200.                 nState[2][1] = temp;
  201.                 State state1(nState,cost+2);
  202.                 states.push_back(state1);
  203.                
  204.                 nState = astate.cState;
  205.                 temp = nState[1][1];
  206.                 nState[1][1] = 0;
  207.                 nState[2][1] = temp;
  208.                 State state2(nState,cost+2);
  209.                 states.push_back(state2);
  210.                
  211.                 return states;
  212.             }
  213.         }
  214.        
  215.         else{
  216.             if(col==0){
  217.                 nState = astate.cState;
  218.                 temp = nState[0][0];
  219.                 nState[1][0] = temp;
  220.                 nState[0][0] = 0;
  221.                 State state(nState,cost+2);
  222.                 states.push_back(state);
  223.                
  224.                 nState = astate.cState;
  225.                 temp = nState[2][0];
  226.                 nState[2][0] = 0;
  227.                 nState[1][0] = temp;
  228.                 State state1(nState,cost+2);
  229.                 states.push_back(state1);
  230.  
  231.                 nState = astate.cState;
  232.                 temp = nState[1][1];
  233.                 nState[1][1] = 0;
  234.                 nState[1][0] = temp;
  235.                 State state2(nState,cost+2);
  236.                 states.push_back(state2);
  237.  
  238.                 return states;
  239.                
  240.             }
  241.             else if(col==2){
  242.                 nState = astate.cState;
  243.                 temp = nState[0][2];
  244.                 nState[1][2] = temp;
  245.                 nState[0][2] = 0;
  246.                 State state(nState,cost+2);
  247.                 states.push_back(state);
  248.                
  249.                 nState = astate.cState;
  250.                 temp = nState[2][2];
  251.                 nState[2][2] = 0;
  252.                 nState[1][2] = temp;
  253.                 State state1(nState,cost+2);
  254.                 states.push_back(state1);
  255.                
  256.                 nState = astate.cState;
  257.                 temp = nState[1][1];
  258.                 nState[1][1] = 0;
  259.                 nState[1][2] = temp;
  260.                 State state2(nState,cost+2);
  261.                 states.push_back(state2);
  262.                
  263.                 return states;
  264.             }
  265.             else{
  266.                 nState = astate.cState;
  267.                 temp = nState[0][1];
  268.                 nState[1][1] = temp;
  269.                 nState[0][1] = 0;
  270.                 State state(nState,cost+2);
  271.                 states.push_back(state);
  272.                
  273.                 nState = astate.cState;
  274.                 temp = nState[2][1];
  275.                 nState[2][1] = 0;
  276.                 nState[1][1] = temp;
  277.                 State state1(nState,cost+2);
  278.                 states.push_back(state1);
  279.                
  280.                 nState = astate.cState;
  281.                 temp = nState[1][0];
  282.                 nState[1][1] = temp;
  283.                 nState[1][0] = 0;
  284.                 State state2(nState,cost+2);
  285.                 states.push_back(state2);
  286.                
  287.                 nState = astate.cState;
  288.                 temp = nState[1][2];
  289.                 nState[1][2] = 0;
  290.                 nState[1][1] = temp;
  291.                 State state3(nState,cost+2);
  292.                 states.push_back(state3);
  293.                
  294.                 return states;
  295.                
  296.             }
  297.         }
  298.     }
  299.    
  300. };
  301.  
  302.  
  303. //
  304. //  Compare.h
  305. //  assignment1
  306. //
  307. //  Created by Josyula Gopala Krishna on 09/02/14.
  308. //  Copyright (c) 2014 Josyula Gopala Krishna. All rights reserved.
  309. //
  310.  
  311.  
  312. #include <iostream>
  313. #include <string>
  314. #include <vector>
  315. #include <queue>
  316. using namespace std;
  317.  
  318. class Compare{
  319. public:
  320.     bool operator()(State s1,  State s2){
  321.         if(s1.total>s2.total) return true;
  322.         if(s1.total == s2.total) return true;
  323.         if(s1.total<s2.total)return false;
  324.         return false;
  325.     }
  326.    
  327. };
  328.  
  329. int main(){
  330.     int i,j;
  331.     priority_queue<State,vector<State>,Compare> fringe;
  332.     vector<State> tempHolder;
  333.     vector<State> actions;
  334.     vector<vector<int>> intial = {{0,1,2},{ 3, 4, 5}, {6, 7, 8}};
  335.     //vector<vector<int>> gol = {{1,6,4} ,{8,7,0} ,{3,2,5}};
  336.     vector<vector<int>> gol = {{3,1,2} ,{4,5,0} ,{6,7,8}};
  337.     State goal(gol);
  338.     State initial(intial,0);
  339.     initial.setHeuristic(goal);
  340.     initial.setfN(initial);
  341.     vector<vector<int>> fakeState = {{0,0,0},{0,0,0},{0,0,0}};
  342.     State node(fakeState);
  343.     fringe.push(initial);
  344.     initial.printState(initial);
  345.     tempHolder = initial.nextState(intial);
  346.    
  347. /*    while(true){
  348.         if(fringe.size() > 0){
  349.             node = fringe.top();
  350.             fringe.pop();
  351.             actions.push_back(node);
  352.             if(node.isGoal(goal)){
  353.                 for(i=0;i<actions.size();i++)
  354.                     actions[i].printState(actions[i]);
  355.                 cout<<actions.size();
  356.                     exit(0);
  357.             }
  358.             tempHolder = node.nextState(initial);
  359.             for(i=0;i<tempHolder.size();i++){
  360.                 tempHolder[i].setHeuristic(goal);
  361.                 tempHolder[i].setfN(tempHolder[i]);
  362.             }
  363.             for(i=0;i<tempHolder.size();i++)
  364.                 fringe.push(tempHolder[i]);
  365.         }
  366.         else{
  367.             cout<<"reached the end of the states";
  368.             exit(EXIT_FAILURE);
  369.         }
  370.     }
  371. */
  372.     return 0;
  373. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!