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.
