Backtracking Search Function Trouble

[Steven Spear]

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_childr en () = 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_child ren();

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<<"Backtrac king...\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_childr en ();

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_solutio n () {
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_c hildren() {

if (!children.empt y()) 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_b ack(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;
}

[Smitsky]

Hi Martin. If you (or anyone else) want(s) me to answer this question, I
will if I have time soon. Right now I'm in the middle of something. Send me
an email, and I'll get back to you.

Meanwhile, I have discovered the answer to my question regarding this
problem.

Thanks, Steve

"Martin Magnusson" <lo*******@frus tratedhousewive s.zzn.com> wrote in message
news:35******** *************** ***@posting.goo gle.com...

sm*****@hotmail .com (Steven Spear) wrote in message
news:<66******* *************** ****@posting.go ogle.com>...

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

What is the command line argument supposed to mean? And why do you
have different indexes for goodmt3 and badmt3 (for goodmt3 you
initialize [0][2], [1][2] and [2][2], while for badmt3 you do
[0][0],[1][1] and [2][2])?

/ martin