//File: $Id: Solver.cpp,v 1.3 2005/04/25 19:22:18 p334-01h Exp p334-01h $//Author: Matthew Dean and Chirag Pujara//Revisions: $Log: Solver.cpp,v $//Revisions: Revision 1.3  2005/04/25 19:22:18  p334-01h//Revisions: Code works and prints answer in correct order//Revisions://Revisions: Revision 1.2  2005/04/24 21:13:55  p334-01h//Revisions: Code now works, however, it prints in reverse order//Revisions://Revisions: Revision 1.1  2005/04/24 21:13:17  p334-01h//Revisions: Initial revision//Revisions:////#include "Puzzle.h"#include "Solver.h"#include <iostream>#include <vector>#include <queue>#include <map>using namespace std;typedef map< vector<int>, vector<int> >::value_type Pair;Solver::Solver( vector<int> init, Puzzle &p1 ) : initial(init), p(p1) {}//solve the puzzlevoid Solver::solve() {  //push the initial value on the queue  q.push( initial );  //insert the initial value into the map with constant vNull as value  myMap.insert( Pair( initial, vNull ) );  //while the queue is not empty and the answer is not at front of queue  while( !(q.empty()) && !( p.isAnswer( q.front() ) ) ) {    //temperary store value for the front of the queue    vector<int> value = q.front();    //find the next configs of value    vector< vector<int> > tempVecVec = p.nextConfigs( value );    //pop the value off the queue    q.pop();    //iterate through the values of tempVecVec    for( vector<vector<int> >::iterator i = tempVecVec.begin();          i != tempVecVec.end(); ++i )      {        //if the value is not in the map already        if( myMap.find( *i ) == myMap.end() ) {          //push the value on the queue          q.push( *i );          //and insert the value into the map          myMap.insert( Pair( *i, value ) );        }      }  }  //if the queue is empty, there is no answer  if( q.empty() ) {    answer = vNull;  }  //else the answer is at the front of the queue  else {    answer = q.front();  }}//solvevoid Solver::outputAnswer() {  cout << "Outputing Answer" << endl;  //starting at the answer  vector<int> temp = answer;  vector<vector<int> > result;  //if there is an answer  if( answer != vNull ) {    //while the current value of the map is not equal to vNull    while( myMap.find( temp )->second != vNull ) {      //push_back the temporary value      result.push_back( temp );      //find the key that corrosponds to the current value      temp = myMap.find(temp)->second;    }        //push on the final value(which is the initial configuration)    result.push_back( myMap.find(temp)->first );    //result now stores the way from initial to solution, but backwards    //this reverses the vector to make it output forwards    for( vector<vector<int> >::reverse_iterator iter = result.rbegin();          iter != result.rend(); iter++) {      p.printPuzzle( (*iter) );    }  }    //if answer == vNull, there was no solution to the puzzle  else {    cout << "There is no solution" << endl;  }}