More Fun with Recursion: The Triangle Game

Quite often, I like to dig a little deeper into some problems. That is why I love what I do for a living, write computer software. In this profession, you can simulate just about anything. The cool part is, change your parameters, re-run the process and get new answers from a different perspective. Recently, I was with my family at Cracker Barrel and my son was playing with their famous triangle game. Basically, the way this game works is you start with a triangle board with pegs that looks something like this.

    O
   O O
  O O O
 O O O O
O O O O O

Now there are different ways to play the game but one of the most common ways is to start with the top most peg empty and rest of the pegs with a golf tee in them. Jumps are made in sequence, removing the peg that was just jumped over. the object, remove all but one peg. For example, suppose the board looks like this where O represents an empty spot.

  +-O
  |B X
  A X X
 X X X X
X X X X X

You can make a jump over on the left side which would result in a board that looks like this.

    A
   o X
  o X X
 X X X X
X X X X X

That would be a valid jump. Now that the basic rules have been explained, what does this have to do with computer programming. I started asking questions like
"How many ways are there to win this game?"
"How many ways ar there to lose it?"
"Where are all the places you can leave just one peg?"
"What are the most pegs you can leave on the board without having any jumps left?"
"Is there a way to do just 3 jumps and leave pegs all around the outside with the middle empty, thus leaving you with no jumps?"

With questions like these, I sat down to write the triangle game simulation. When doing something like this, I have found that you need about 3 things.

1. The basic set of rules on how to play and win the game.
2. A model to play the game on.
3. A good approach to finding all the possible combinations.

The basic rules are explained above. Now onto a model. I decided to model the game by representing the board as an array of boolean values. The top most position would be position 0 then incrementing by 1 with the next row, left to right and the next row until all the spaces were represented, 15 in all. The next part of the model was to determine what were all the potential valid moves (pegs not withstanding). For example if the positions looked like this.

    0
   1 2
  3 4 5
 6 7 8 9
A B C D E

an example of some potential moves would be A-6-3 or 5-8-C or 1-4-8. By examining all of the possible moves on a given board, we can determine which ones would work and which ones wouldn't. If we "perform" the move, that would put the board into a different configuration. On each new configuration, the board analyzed. There are two possible outcomes of this analysis.

1) More moves are possible.
2) The game is over as no moves are available.

One each evaluation, once the game is over, that configuration is recorded. Also, a history of the moves that led to that configuration can also be recorded so that you can have a sequence of moves leading up to that win. This can be used to learn to solve the puzzle.

The final piece of the solution was how to implement this. This is where the concept of recursion shines. You can develop the routines to analyze a board and apply the moves once. On each new iteration of a board, you can take that new configuration and recursively call the analysis function. As each new configuration is generated, it is evaluated and recorded. Then the new configuration is run through the same function and the process starts all over for the new configuration. What the recursion does is to provide us with an automatic mechanism to save the state so that when we exit the evaluation process, we are taken back to where that eval was started so that the code can pick back up where it left off and continue. To demonstrate this, let's create a very small sample. Let's say our board looks like this.

  0
 1 2
3 4 5

Pegs are in positions 1-5. Potential jumps are (1) 3-1-0, (2) 0-1-3, (3) 5-2-0, (4) 0-2-5, (5) 3-4-5, (6) 5-4-3. If our board is represented as an array of bools, then the starting configuration would look like this.

0 1 2 3 4 5
F T T T T T


The evaluation would look something like this.

Start - Recursion level 0
0 1 2 3 4 5 - Apply Rule 1 - 0 1 2 3 4 5 
F T T T T T                  T F T F T T 
        Recursion Level 1
        0 1 2 3 4 5 Apply Rule 1 - Invalid
        T F T F T T Apply Rule 2 - Invalid
                    Apply Rule 3 - Invalid
                    Apply Rule 4 - Invalid
                    Apply Rule 5 - Invalid
                    Apply Rule 6 - 0 1 2 3 4 5 
                                   T F T T F F
                Recursion Level 2
                0 1 2 3 4 5 Apply Rule 1 - Invalid 
                T F T T F F Apply Rule 2
                            Apply Rule 3
                            Apply Rule 4 - 0 1 2 3 4 5 
                                           T F T T F F
                        Recursion Level 3
                        0 1 2 3 4 5 Apply Rule 1 - Invalid
                        T F T T F F Apply Rule 2 - Invalid
                                    Apply Rule 3 - Invalid
                                    Apply Rule 4 - 0 1 2 3 4 5
                                                   F F F T F T
                                Recursion Level 4
                                0 1 2 3 4 5 Apply rule 1 - Invalid
                                F F F T F T Apply rule 2 - Invalid
                                            Apply rule 3 - Invalid
                                            Apply rule 4 - Invalid
                                            Apply rule 5 - Invalid
                                            Apply rule 6 - Invalid
                                            All rules invalid. Losing combination.
                        Recursion Level 3
                        0 1 2 3 4 5 Apply Rule 5 - Invalid
                        T F T T F F Apply Rule 6 - Invalid

                Recursion Level 2
                0 1 2 3 4 5 Apply Rule 5 - Invalid 
                T F T T F F Apply Rule 6 - Invalid

        Recursion Level 1
        0 1 2 3 4 5 All Rules applied already
        T F T F T T 
0 1 2 3 4 5 - Apply Rule 2 - Invalid
F T T T T T - Apply Rule 3 - 0 1 2 3 4 5 
                             T T F T T F
. . . . . . . .

As you can see from the sample run, each time a move is valid, that move is applied and a new level of recursion is entered into. When all moves for that configuration have been tried, the previous level of recursion is returned to and the rules pick up where they left off. Of course with a bigger playing board, the iterations will be more and deeper. Once this system is in place, you could create different board configurations and rule congfigurations and play a wide variety of virtual boards.

Now that we have the concept out of the way, let's see how to implement it in code.
First we start with a Triangle object. This represents the playing board.

    class Triangle
    {
        bool[] Board = { false, false, false, false, false, 
                         false, false, false, false, false, 
                         false, false, false, false, false };
        string status;
        int MoveApplied = -1;

        public Triangle NextTriangle;
        public Triangle PrevTriangle;

        public Triangle(Triangle starting)
        {
            // Using the last triangle to initialize this triangle.
            for (int x = 0; x < starting.Board.Length; x++)
                Board[x] = starting.Board[x];
            // Setting the pointer to the last triangle.
            PrevTriangle = starting;
        }
        public Triangle(bool[] values)
        {
            // Init through an existing array.
            for (int x = 0; x < values.Length; x++)
                Board[x] = values[x];
        }

We have the ability to create the board with either an existing triangle or if we are creating for the first time, an array of bools that indicate what the starting positions are. Now, I will switch over to the class that defines the legal moves. This is implemented as a static class.

    static class LegalMoves
    {
        static public frmMain TheMainForm;
        static public int SolutionsFound = 0;

        static public string GetString(int ndx)
        {
            if (ndx < 0)
                return "";
            return "[" + moves[ndx, 0] + "," + moves[ndx, 1] + "," + moves[ndx, 2] + "]";
        }
        static public int[] Solutions = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        static public int[,] moves = new int[,]
        {
            {0,1,9},{0,2,5},{1,3,6},{1,4,8},{2,4,7},{2,5,9},
            {3,1,0},{3,4,5},{3,7,12},{3,6,10},{4,7,11},
            {4,8,13},{5,2,0},{5,4,3},{5,8,12},{5,9,14},
            {6,3,1},{6,7,8},{7,4,2},{7,8,9},{8,4,1},{8,7,6},
            {9,5,2},{9,8,7},{10,6,3},{10,11,12},{11,7,4},
            {11,12,13},{12,7,3},{12,8,5},{12,11,10},{12,13,14},
            {13,12,11},{13,8,4},{14,13,12},{14,9,5}
        };

    }

This defines a class that holds all possible legal moves that can be applied to the board. Of course the move is valid if the pegs are in the correct positions. Now back to the triangle class. The recursive procedure is called EvalLegalMoves. This will process any given triangle for legal moves. Once a legal move is found, the move is applied and the EvalLegalMoves procedure is called again. Look below..

        public void EvalLegalMoves()
        {
            int lmi; // Legal Move Index
            bool LegalMovesFound = false;
            for (lmi = 0; lmi < 36; lmi++)
                if (Board[LegalMoves.moves[lmi, 0]] == true &&
                    Board[LegalMoves.moves[lmi, 1]] == true &&
                    Board[LegalMoves.moves[lmi, 2]] == false)
                {
                    LegalMovesFound = true;
                    // Create the next triangle.
                    NextTriangle = new Triangle(this);
                    NextTriangle.ApplyMove(lmi);
                    NextTriangle.EvalLegalMoves();
                    NextTriangle = null;
                }

            // Now that we have done evaluating legal moves, let's see if this 
            // one is one of our end cases.
            if (LegalMovesFound == false)
            {
                int PegsLeft=0;
                for (int x = 0; x < Board.Length; x++)
                    if (Board[x])
                        PegsLeft++;
                // One thing we are looking for is how many solutions leave 
                // one peg.
                if (PegsLeft == 1)
                    DocumentWinner();
            }
        }

You can define DocumentWinner any way you wish. You can output the results or whatever you want to do. Play with the code from here. Hope you enjoyed.

Scott.

Generating String Permutations Recursively in C#

This article will demonstrate a simple routine that uses recursion in C# to generate
a list of string permutations. I originally wrote this routine because I was
interested in a little bit larger project in which I thought a routine like this
would be useful. I had become interested in an online game where, given a
string of X number of characters, you see how many way you can combine the letters
in that string to make words. The program would go something like this.

1. Generate the permutations.
2. Break each permutation down into 3, 4, 5 ... X letter strings.
3. Check each break down against a dictionary, if in the dictionary, keep the word

So the first order of business was to generate every possible permutation of an
X character string. After working with a recursive routine, I managed to get
it down to a very simple few lines of code.

First, before going over the code, let's understand the concept. Let's
look at the permutations for a 2 character string. Let's say our string
is 'AB'. The possible permutations are

1. 'AB'
2. 'BA'

Very easy, we just switch the last two characters. Now if we want to get the
permutations for a 3 character string, Say 'ABC', that process is very simple
too.

1. Start with 'ABC'.
2. Swap the last two characters to get ACB
3. Now take the original string and move the A into the second to last position giving
   you BAC
4. Again Swap the last two characters giving you BCA
5. Now come back out and swap the first two characters giving you CBA
6. And finally swap the last two characters giving you CAB

If you want to do four characters, the process is the same. Permutate the
right most 2 characters, then swap in character 3 and do the permutations, then
swap in character 4 and do the permutations again. The beauty of the recursion
is that upon leaving one swapping operation, you can get back to an original string
(stored on the stack) and keep the permutations going. Since the calls use
the string lenght to determine how to proceed, you should be able to pass a string
of any length in and get the permutations. The only caveat is that the number
of permutations generated for any given string is exponential as the string get's
larger. The number of permutation is X ! given that X is the number of characters
in the original string. As you can see, it can get quite large pretty quick.

String Size	Number of Permutations	Time to Process
1	1 (1!)	Negligable
2	2 (2!)	Negligable
3	6 (3!)	Negligable
4	24 (4!)	Negligable
.....	.....
10	3,628,800 (10!)	7.27 Seconds
12	479,001,600 (12!)	Out of Memory error thrown.

The time to process above was done on a dual processor test machine running at 3
GHz with 2 Gig of internal memory. As you can see, with a short string, you
can generate many permutations. Get much more over 10 and you will start to
see some serious performance degradation. If you really need to generate permutations
on strings that large, consider disk storage.

Now that we have discussed the concept, let's look at the code. I have
encapsulated all of the code into one class. Here is the listing for that
class.

using System;
using System.Collections;

namespace Permutations
{
    // To save space, I have not used proper techniques of 
    // hiding attributes behind properties. There are
    // probably other things that haven't been done as well 
    // but I am just trying to show the concept.
    class PermutateString
    {
        // Holds the final array of permutations
        public ArrayList AL = new ArrayList();

        public PermutateString(string Source)
        {
            Perm("", Source);
        }

        private void Perm(string Beginning, string Shuffle)
        {
            // By the time the Shuffle length get's down to 1, 
            // we have another permutation to store.
            if (Shuffle.Length <= 1)
                AL.Add(Beginning + Shuffle);
            else
            {
                for (int Ndx = 0; Ndx < Shuffle.Length; Ndx++)
                {
                    // here, we move the character at the ndx position
                    // to the front of the line, then copy in the first 
                    // ndx characters of the string and then the characters
                    // after that. so if NDX is at 3 in the following string,

                    // then the string ABCDEF would become DABCEF. This loop
                    // pulls each postion out to the front of the line and then
                    // calls the Perm operation again.
                    Shuffle = Shuffle.Substring(Ndx, 1) +
                        Shuffle.Substring(0, Ndx) +
                        Shuffle.Substring(Ndx + 1);
             
                    // Now that we have moved the shuffled characters around a bit,
                    // we call the perm function again moving one of the characters back
                    
                    // to the beginning string.
                    Perm(Beginning + Shuffle.Substring(0, 1),
                        Shuffle.Substring(1));
                }
            }
        }
    }
}

It may be a little difficult to follow so the best thing to do is to copy the
code into your project and run it through the debugger. As you trace the
values of Beginning and Shuffle, you should see the logic unfold. Hope you
enjoyed this.