Click here to Skip to main content
Click here to Skip to main content

Solitaire Puzzle with Backtracking

, 10 Sep 2005
Rate this:
Please Sign up or sign in to vote.
A program to play Solitaire puzzle and to seek solutions using backtracking.

Introduction

This program lets you play Solitaire puzzle (also known as Peg Solitaire Puzzle) with two big advantages over a real gaming table:

  1. you never lose the pieces,
  2. 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:

// === methods to override
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:

  1. My code is C++, while Dong's code is C#.
  2. Dong's article deals with Breadth First search (BFS) backtracking, which I have left out.
  3. I have abstracted a general reusable class for backtracking, while Dong's code is tied to that particular puzzle.
  4. 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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Paolo Martinoli
Software Developer (Senior) Next S.p.A.
Italy Italy
No Biography provided

Comments and Discussions

 
Generalsolitaire PinmemberJosphat4-Dec-07 20:53 
Generalhi Pinmember941549611-Sep-06 10:14 
Generalcool ... PinmemberPaul Brower10-Sep-05 16:40 
I've been looking for a little 'easter egg' to bury in my current app.
 
Thanks to you, I've found itBig Grin | :-D
 
got my 5

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.141015.1 | Last Updated 10 Sep 2005
Article Copyright 2005 by Paolo Martinoli
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid