idea_bt

//puzzle seria el tablero
backtrack(Puzzle &p){

 //poda: si ya sabemos que la rama no puede ganarle a la mejor
  //que conocemos hasta el momento, dejamos de explorar esa rama
 if( p.maximum_possible_score() <= best_so_far.score() )
  return;

 //Si ya llegamos hasta el final del tablero,
  //vemos el puntaje de esta solucion. Si es mejor que la
  //mejor solucion conocida, actualizamos
 if( p.solved() ){
  if( p.score() > best_so_far.score() )
   best_so_far = p;
  return;
 }

 //Para cada pieza disponible, hacer:
 for(Puzzle::Iterator it(p.begin()); it!=p.end(); it++){
  //Si la pieza se puede poner en el proximo casillero, se pone
  if( p.push_piece(*it) ){
   backtrack(p); //y luego exploramos la rama correspondiente
   p.pop_piece();//sacamos la pieza que acabamos de poner
  }
 }
}