Backtracking Search Function Trouble

S

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_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->visited; i++){}

if(!tmp->children->visited)
{
cout<<"Going to child...\n";
s.push(tmp);
tmp=tmp->children;
continue;
}
else if(tmp->children->visited && s.empty())
{
cout<<"No solution exists!\n";
return false;
}
else if(tmp->children->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[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[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[j] == 'X') ++rowcount;
if (data->ary[j] == 'X') ++colcount;
}

if (rowcount == 3 || colcount == 3) return true;
}

int left = 0, right = 0;
for (int i = 0; i < 3; ++i) {
if (data->ary == 'X') ++left;
if (data->ary[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[j] == '_') {
mt3* tmp = new mt3;
tmp->copy(*this);
tmp->data->ary[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[j] = tocopy.data->ary[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;
}
 
M

Martin Magnusson

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
 
S

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 said:
(e-mail address removed) (Steven Spear) wrote in message
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top