Function causing error

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

---

>Any ideas why I'm running into a wall here?
There's no solution for when argument is 2. I notice that your code takes this into account in search, but there's one problem. You test for a no solution case inside this loop:

Code:

---

for(int i=0; i<tmp->children.size(); i++)

---

However, if there's no solution then there will be no '_' characters in the array, thus there will be no children, and tmp->children.size() will be 0. You can see how this will happen by looking at tmp->generate_children():

Code:

---

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

---

The vector will remain empty unless there is at least one '_' character in the array. Going back to the loop:

Code:

---

for(i=0; i<tmp->children.size(); i++)

---

0 is not less than 0, so the body is never executed and you proceed to loop infinitely.

Some have suggested that I change the loop to read:

Code:

---

for(i=0; i<tmp->children.size() && tmp->children[i]->visited; i++)

---

However, when I do this, I create an infinite loop when the argument is 1. I am trying to backtrack here, but something is going wrong. Any suggestions? Thanks, Steve

Hi. I just wanted to show you this function. I have figured out the solution with some very good help. This is my first experience with trees and backtracking. I'm excited about it. I asked why it takes the computer so long to find that there is no solution for badmt3. I was told that "it is just stupid." It runs for about 10 to 15 seconds on my system. Run it and see what you think. It is the most complex program I have ever written. I am now going to use this to solve the n-Queens problem. Regards, 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)
{
    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;
        }//if
        else
        {
            tmp->print(s.size()*2);
            tmp->visited=true;
        }//else
       
        tmp->generate_children();
       
        int i;
        for(i=0; i < tmp->children.size()
            && tmp->children[i]->visited; i++){}
           
            if(i==tmp->children.size() && s.empty())
            {
                cout<<"No solution exists!\n";
                return false;
            }//else if
            else if(i==tmp->children.size())
            {
                cout<<"Backtracking...\n";
                tmp=s.top();
                s.pop();
                continue;
            }//else
            else
            {
                cout<<"Going to child...\n";
                s.push(tmp);
                tmp=tmp->children[i];
                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;
}

---