Hi. I am having trouble with the search function in this program I am writing. I generate an infinite loop entering 2 at the command line, while entering 1 works fine. Any ideas why I'm running into a wall here? All ideas will be appreciated. Thanks. Steve
Code:#include <iostream> #include <vector> #include <stack> #include <string> using namespace std; template <class T> struct State { bool visited; vector<State*> children; T* data; State () : visited(false), data(0) { } virtual ~State () { } virtual void print (int indent = 0) = 0; virtual bool is_solution () = 0; virtual void generate_children () = 0; }; template <class T> bool search (State<T>& initial) //trouble with this fcn { stack<State<T>*> s; State<T>* tmp; tmp=&initial; bool runner=true; while(runner) { if(tmp->is_solution()) { tmp->print(2*s.size()); cout<<"Solution found!\n"; return true; } else { tmp->print(2*s.size()); tmp->visited=true; } tmp->generate_children(); int i; for(i=0; i<tmp->children.size(); i++) { cout<<"Going to child...\n"; if(!tmp->children[i]->visited) { s.push(tmp); tmp=tmp->children[i]; break; } if(tmp->children[i]->visited && s.empty()) { cout<<"No solution exists!\n"; return false; } else if(tmp->children[i]->visited && !s.empty()) { tmp=s.top(); s.pop(); break; } } } } struct mt3data { char ary[3][3]; }; struct mt3 : public State<mt3data> { mt3 (); ~mt3 (); void print (int indent = 0); bool is_solution (); void generate_children (); void copy (const mt3& tocopy); }; mt3::mt3 () { data = new mt3data; for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) data->ary[i][j] = '_'; } mt3::~mt3 () { delete data; } void mt3::print (int indent) { string theindent = ""; for (int i = 0; i < indent; ++i) theindent += " "; for (int i = 0; i < 3; ++i) { cout << theindent; for (int j = 0; j < 3; ++j) cout << data->ary[i][j]; cout << endl; } } bool mt3::is_solution () { for (int i = 0; i < 3; ++i) { int rowcount = 0, colcount = 0; for (int j = 0; j < 3; ++j) { if (data->ary[i][j] == 'X') ++rowcount; if (data->ary[j][i] == 'X') ++colcount; } if (rowcount == 3 || colcount == 3) return true; } int left = 0, right = 0; for (int i = 0; i < 3; ++i) { if (data->ary[i][i] == 'X') ++left; if (data->ary[i][2-i] == 'X') ++right; } if (left == 3 || right == 3) return true; return false; } void mt3::generate_children() { if (!children.empty()) return; for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) if (data->ary[i][j] == '_') { mt3* tmp = new mt3; tmp->copy(*this); tmp->data->ary[i][j] = 'X'; children.push_back(tmp); } } void mt3::copy (const mt3& tocopy) { for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) data->ary[i][j] = tocopy.data->ary[i][j]; } void syntax (string s) { cout << "Specify an integer argument as to which test to run: " << endl << "1. Successful MT3" << endl << "2. Unsuccessful MT3" << endl; cout << endl; cout << "For example: " << s << " 2" << endl; } int main (int argc, char** argv) { if (argc == 1) { syntax(argv[0]); return 0; } string argument = argv[1]; if (argument == "1") { mt3 goodmt3; goodmt3.data->ary[0][2] = '0'; goodmt3.data->ary[1][2] = '0'; goodmt3.data->ary[2][2] = '0'; search(goodmt3); return 0; } else if (argument == "2") { mt3 badmt3; badmt3.data->ary[0][0] = '0'; badmt3.data->ary[1][1] = '0'; badmt3.data->ary[2][2] = '0'; search(badmt3); return 0; } syntax(argv[0]); return 0; }