Configuration Puzzles: Design Approaches

Although you are free to make your own design decisions, some suggested approaches are shown here that satisfy the requirement of a framework that adapts well to different "configuration/puzzle" problems. But first, let's ponder some general requirements.

Clearly, if the solver algorithm is going to work with different problems, the notion of configuration should somehow be viewed as an abstraction. This abstraction would contain operations for things like goal testing, finding neighboring configurations,  and display/printing.

Most students of a more pure object-oriented language like Java would immediately think of making Configuration an interface, or an abstract class. And indeed, that is one of the approaches upon which we will expound. However, consider the following peculiarities of C++.

1. In order to determine if configurations have been seen before, they ones already seen probably need to be stored in a container of some kind (something based on a map or set for easy lookup comes to mind as a good choice). It is necessary to be able to compare configurations to keep the container from holding multiple identical configurations.
2. Passing around and storing configurations around by pointer can therefore be problematic, since we would be comparing addresses of configuration objects rather than contents.
3. To allow polymorphism, the configurations must be pointers! (This will be explained by week 4 of the lectures.)
4. If we do use pointers, and therefore dynamic allocation, we must delete the allocated objects to avoid memory leaks, but it is hard to determine if no one is pointing to a configuration anymore, since several configurations could have the same one as a potential neighbor.

So the design choices presented here can be broken into two categories:

1. If we stick with pointers to keep the idea of using an abstract class and polymorphism, how do we get them to work?
   • String-keyed map
   • Smart pointers
   • Very careful tracking of configurations and appropriate deallocation
2. If we abandon pointers, how do we maintain the extensibility of the solver? That is, what other abstraction techniques could we employ?
   • Templates
   • Universal integer vectors

If you feel like the design descriptions are incomplete, that is intentional. We have to leave something left for you to do! Nevertheless, feel free to talk to your instructor about any of these ideas, or others that you have.