backtrack.h

#ifndef BACKTRACK_H
#define BACKTRACK_H

class MoveState
{
public:  
  virtual bool reject()=0;
  virtual bool accept()=0;
  virtual MoveState* next()=0;

  //move "memory"
  virtual MoveState* before()=0;
  virtual MoveState* after()=0;
};


//the simple backtracking algorithm
bool backtrack(MoveState *c) 
{
  if(c->reject()) return false;
  if(c->accept()) return true;   

  MoveState c2;
  while(c2=c->next()) {
    if(backtrack(c2)) {
        return true;
    }
    delete c2;  //not that one!      
  }

  return false;
}