This section presents an abstract base class for representing the nodes of a solution space. By defining an abstract interface, it is possible to hide the details of the specific problem to be solved from the backtracking algorithm. In so doing, it is possible to implement completely generic backtracking problem solvers.

Although a backtracking algorithm behaves as if it is traversing a solution tree, it is important to realize that it is not necessary to have the entire solution tree constructed at once. Instead, the backtracking algorithm creates and destroys the nodes dynamically as it explores the solution space.

Program defines
the abstract class called `Solution`.
The `Solution` class is intended to serve as
the base class from which problem-specific classes are derived.
Each `Solution` instance represents a single node
in the solution space.

**Program:** `Solution` Class Definition

The `Solution` class is derived from the `Object` base class.
Consequently, instances of the `Solution` class can be inserted
in the various containers discussed in the preceding chapters.
The `Solution` class adds the following functions
to the inherited interface:

`IsFeasible`- This function returns true if the solution instance is a feasible solution to the given problem. A solution is feasible if it satisfies the problem constraints.
`IsComplete`- This function returns true if the solution instance represents a complete solution. A solution is complete when all possible decisions have been made.
`Objective`- This function returns the value of the objective function for the given solution instance.
`Bound`-
This function returns a value that is a lower bound (if it exists)
on the objective function for the given solution instance
as well as all the solutions
that can possibly be derived from that instance.
This is a hook provided for to facilitate the implementation
of
*branch-and-bound*backtracking which is described in Section . `Clone`-
This function is used to
*clone*the given solution instance. It returns a reference to another, dynamically allocated solution that is identical to the given solution instance. `Successors`-
This function returns an iterator that enumerates
all of the successors (i.e., the children)
of the given solution instance.
It is assumed that this iterator creates the children of the given
node
*dynamically*.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.