//	
//	class backtrackFramework
//		general framework for solving problems
//		involving backtracking
//		
//	(can also be compiled using list instead of deque)
//

template <class T> class backtrackFramework {
public:
	// protocol for backtrack problems
	virtual void    initialize     () { }
	virtual bool    advance        (T newstate) { }
	virtual bool    run            ();
	
protected:
	stack < deque <T> >  theStack;
	bool            done;
};

template <class T> bool backtrackFramework<T>::run ()
{
	// initialize the problem
	initialize ();
	done = false;

	// do the main loop
	while ((! done) && (! theStack.empty ())) {
		// if we can't advance from current state
		// then pop the stack
		if (! advance(theStack.top ()))
			theStack.pop ();
		}
	
	// return true if stack is not empty
	return ! theStack.empty ();
}