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