Thread: Function causing error

  1. #1
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

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

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  3. #3
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79
    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

  4. #4
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

    Cool Solution Found

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. We Got _DEBUG Errors
    By Tonto in forum Windows Programming
    Replies: 5
    Last Post: 12-22-2006, 05:45 PM
  2. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  3. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 01:03 PM
  4. pointer to array of objects of struct
    By undisputed007 in forum C++ Programming
    Replies: 12
    Last Post: 03-02-2004, 04:49 AM
  5. qt help
    By Unregistered in forum Linux Programming
    Replies: 1
    Last Post: 04-20-2002, 09:51 AM