The usual way to implement a backtracking algorithm
is to write a function or procedure which traverses the solution space.
This section presents an alternate, object-oriented approach
that is based on the notion of an
*abstract solver* .

Think of a solver as an abstract machine, the sole purpose of which is to search a given solution space for the best possible solution. A machine is an object. Therefore, it makes sense that we represent it as an instance of some class.

Program declares the abstract class `Solver`.
The public interface of this class consists
of the single function `Solve`.
This function takes as its lone argument
a reference to a `Solution` instance that is the node
in the solution space from which to begin the search.
The `Solve` function returns a reference to the
to the best solution found.

**Program:** `Solver` Class Definition

Program also declares two protected member variables,
`bestSolution` and `bestObjective`,
and two protected member functions,
`UpdateBest` and `DoSolve`.
Since `DoSolve` is a pure virtual function,
its implementation must be given in a derived class.
Program gives the implementations
for `Solve` and `UpdateBest`.

**Program:** `Solver` Class `Solve` and `UpdateBest` Member Function Definitions

The `Solve` function does not search the solution space itself.
It is the `DoSolve` routine,
which is provided by a derived class,
that does the actual searching.
The `Solve` routine merely sets things up for `DoSolve`.
When `DoSolve` returns it is expected that the
`bestSolution` variable will point to the best solution
and that `bestObjective` will be the value of the objective
function for the best solution.
In this case,
it is assumed that the goal is to *minimize* the objective function.

The `UpdateBest` function
is meant to be called by the `DoSolve` routine
as it explores the solution space.
As each complete solution is encountered,
the `UpdateBest` routine is called to keep track
of the solution which minimizes the objective function.

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