Backtracking Algorithms : Explaining Cindy's Puzzle with a C++ Program

Classic text books in Algorithm Analysis like Cormen, Leiserson and Rivest, Sedgewick and Flajolet, etc. often neglect or give least preference to the algorithm development technique called backtracking. Even those textbooks discussing backtracking only discuss few selected problems. A classic problem discussed along with backtracking is the eight queens puzzle. Often this problem is unappreciated by persons not well versed in the game of Chess. Here I am trying to explain backtracking using a very simple game often called ‘Cindy’s puzzle’.

The game Cindy’s puzzle involves n Red marbles, n Green marbles and a playing board which consists simply of a line of 2n+1 spaces to put the marbles in. Start with the Red marbles all at one end (say, the left), the Green marbles all at the other end, and a free space in between. For n=2, the initial arrangement on the board is shown below.

To denote this position we use the notation |R|R| _ |G|G| is used.

The aim of the puzzle is to reverse the positions of the marbles as shown below.

So the solution for the puzzle can be denoted as |G|G| _ |R|R|.

The movements of the marbles are restricted by the following rules.

The Red marbles can only move to the right, and the Green marbles can only move to the left (no backing up). At each move, a marble can either

• Move one space ahead, if that space is clear, or
• Jump ahead over exactly one marble of the opposite color, if the space just beyond that marble is clear.

I am trying to develop a backtracking algorithm to solve this puzzle. The algorithm will be able to produce one particular solution to this puzzle. For example for n=2, the solution steps are given below.

           |R|R| _ |G|G|

        |R|R|G| _ |G|

        |R| _ |G|R|G|

        | _ |R|G|R|G|

        |G|R| _ |R|G|

        |G|R|G|R| _ |

        |G|R|G| _ |R|

        |G| _ |G|R|R|

        |G|G| _ |R|R|

Of course this is an ideal solution where no backtracking is used but in the proposed backtracking algorithm, if non winnable situation arises backtracking is applied to go back to a previous state and continue the search for a solution. 

 Click here to download the C++ Program.