solver.cpp

All are the assignments of mine that I have developped in Data Structure Laboratory Hours

 //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 puzzle
void 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();
  }
}//solve


void 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;
  }
}