Hi. I am trying to perform backtracking with this search function.
Something is going wrong when I enter 2 at the command line. Entering
1 at the command line seems to work fine. I notice that backtracking
never takes place. Obviously there is something wrong with my logic. I
have been trying many things for many days to correct the situation,
but nothing seems to help. Does anyone have any suggestions? Thanks,
Steve
#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(s.size()*2);
cout<<"Solution found!\n";
return true;
}
else
{
tmp->print(s.size()*2);
tmp->visited=true;
}
tmp->generate_children();
int i;
for(i=0; i<tmp->children.size()
&& tmp->children[i]->visited; i++){}
if(!tmp->children[i]->visited)
{
cout<<"Going to child...\n";
s.push(tmp);
tmp=tmp->children[i];
continue;
}
else 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();
cout<<"Backtracking...\n";
s.pop();
continue;
}
}
}
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;
}
