Here we get around the C++ pointer's shortcomings by utilizing something else in place of it that will still allow us some kind of indirect reference to a configuration object. Instead of an address into the memory space at large, we use a string to reference an associative map.
Define a function that creates a unique string for each distinct configuration. Use this string as a key to the map of configurations. Whenever you want to determine if a new neighbor configuration has already been seen, just compute its key and see if it is in the map. If you want to include a "pointer" in your configuration, e.g., to find your path back to the initial configuration, just remember the string key of the other configuration instead.
The configurations stored in the map can now be pointers, since the unique keys will ensure that exactly one copy of any configuration considered will be kept there. This means that polymorphism of these objects is preserved. Cleaning up your memory usage becomes simply iterating over the map and deleting each pointed-to configuration.
Hint: You are already required to generate a string representation of the configuration's state. Do you know where? Can this functionality do double duty?