Introduction
This program lets you play Solitaire puzzle (also known as Peg Solitaire Puzzle) with two big advantages over a real gaming table:
- you never lose the pieces,
- the program can solve the puzzle in your place - or at least it tries to.
The program, in fact, implements a simple backtracking algorithm to search for a solution starting from the current disposition of the pieces on the board.
Background
The main purpose of this program is to illustrate the concepts of recursive function, inherently recursive problem and backtracking. It also provides an object oriented vestment to backtracking, in the form of a reusable class holding all the backtracking logic. The source code comprises of the template class Stack<class TYPE>, a simple MFC based typed stack.
Using the code
The Backtrack class
The Backtrack class is an extremely general implementation of the DFS (Depth First Search) backtracking algorithm. It was written mainly for teaching purposes in order to take the backtracking logic out of the details of a particular problem. To use this class, you have to derive your own class from it and implement the following abstract methods:
public:
virtual bool solved() const = 0;
private:
virtual Step *firstStep() const = 0;
virtual bool nextStep(Step *p_step) const = 0;
virtual void doStep(const Step *pc_step) = 0;
virtual void undoStep(const Step *pc_step) = 0;
virtual void saveStep(const Step *pc_step,
int level) = 0;
In our example, the Backtrack class is realized by the Solitaire class, which represents the game board and keeps track of the game state, i.e. the current disposition of the pieces on the board.
Backtracking synthesized
We know that backtracking applies to problems that can be solved by performing a sequence of steps. In the Solitaire puzzle, for example, a step consists of a move of a piece on the board, according to the game's rules. We must be able to specify the possible steps (or moves) that can be made at a given state of the game.
We accomplish this task by implementing the first two methods listed above, firstStep() and nextStep(). Note that these methods are declared const, in that they don't have to modify the state of the game: firstStep() returns a pointer to an object of class Step, and nextStep() modifies its argument.
The next two methods, doStep() and undoStep() is where we update the game's state (in our example, where we change the position of the pieces on the board): doStep() must perform the step indicated by its parameter, while undoStep() must roll the game back to the previous state, undoing the specified step.
The solved() method must be overridden in order to tell if the current configuration of the game is a solution (returns true) or not (returns false). When a solution is found, the algorithm calls saveStep() for every step of the solution. One has to override this method in order to save the solution's step.
The class Step is just an empty interface. It must be realized by a class (in our example, the Move class) holding all the information needed to represent a game's move. Once all the abstract methods have been overridden, we are ready to use our derived class to seek a solution. We do this simply by calling the public method solve(). This method performs the recursive search. It returns true when it finds a solution, it returns false after having traversed the whole search tree, in vain, just to ascertain that there is no possible solution.
Some other detail
Optionally, you can override this method too:
virtual void traceStep(const Step *pc_step,
int level, bool undo = false);
It will be called before every call to doStep() or undoStep(), and can be used to trace the search path. In our example, it is used to "animate" the board, showing the pieces quickly moving on it during the search.
It is possible to stop the search by setting the public attribute m_abort to true. Note that it is declared volatile, in case you would set it in another thread than the one executing the search. In fact, it is likely that you might want a worker thread to carry out the search while the main thread "keeps the window alive".
By the way, our program uses a single thread and performs "background processing" instead. This means that it periodically yields execution control to Windows using a PeekMessage loop. You can find the PeekMessage loop in the traceStep() implementation in the CSolitaireView class. In this way, we get the same result - the program window doesn't freeze during the search - with just one thread and a simple code.
A last word on the Step objects' allocation. In the firstStep() method, it is necessary to create new instances of the Step class (or rather, of its concrete subclass Move), and we might wonder whether we have to delete these objects and when: the Backtrack class code takes care to delete them, unless they are returned by the saveStep() method.
Points of interest
Template method pattern
The Backtrack class represents an example of the Template Method Pattern. An abstract class (Backtrack) contains only a part of the logic which is needed to accomplish its purpose. It is organized so that its concrete methods call the protected (or even private) abstract methods where the missing logic would have appeared. The missing logic is provided in a concrete subclass overriding the abstract methods.
Shortcomings
We know that backtracking is, by its nature, not efficient, in that it provides an exhaustive search on the whole tree of the possible states of the game. Its response time grows exponentially as the complexity of the problem grows.
In our example, there are many configurations of the board which the algorithm simply cannot manage.
Improvements
The program has been improved with the ability to recognize symmetries. In this way, the program doesn't waste time passing twice through two search paths that are really equivalent. Symmetry awareness is implemented in the firstStep() and nextStep() methods of the Solitaire class.
It is also possible to change the order in which the search tree is covered. If a search takes too much time, one can stop it and try a different search order. To change the search order go to the menu "Move->Set Search Parameters...".
A further improvement could be to endow the program with a "database" of pre-solved boards to be sought. This is a well known issue in literature, and works well if one is able to write a hash table access algorithm that is faster than the recursive tree traversing.
Since a solution for a given board configuration is such a precious resource, when one is found, the program allows you to save it, together with the board game.
Related articles
In the Code Project there is, at present, another article about backtracking applied to a puzzle: "Backtrack technique to solve Chinese Slide Block Puzzle" by Dong Xiang. The two articles differ in that:
- My code is C++, while Dong's code is C#.
- Dong's article deals with Breadth First search (BFS) backtracking, which I have left out.
- I have abstracted a general reusable class for backtracking, while Dong's code is tied to that particular puzzle.
- My program has a GUI to actually play the puzzle, while Dong's program just solves some preset hard-coded configurations.
History
- 10th September 2005 - Article submitted.
