Frogs Game

• Download demo - 7.91 KB
• Download source - 262.97 KB

Introduction

First, I've written the program to play the game with frogs. It is a simple game. You have three frogs on the left leaves and three frogs on the right leaves. The goal of the game is to have the left three frogs on the right side and the right ones on the left.

The frog with an 'L' can move from left to right for one position or for two positions if it jumps the frog with an 'R'. The frog with an 'R' can move from right to left for one position or for two positions, if it jumps the frog with an 'L'.

Writing the code for playing the game is simple. All we have to do is to validate the user move and check if he has reached the goal. It is also possible that no more moves are possible and the goal isn't reached. In this case, we notify the user and reset the game.

The problems begin when the computer solves the game. The computer must make moves which lead to the goal. When it makes the first move, it isn't clear if this move will lead to a happy ending. The computer must try all the possibilities in a situation. If the move is leading to the goal, the computer must remember the move and the path to reach this move. If the move leads to a situation where no more "legal" moves are possible, the computer must discard the move and take the alternative.

Background

The algorithm for solving the problem is a standard backtracking algorithm with which we review the nodes of a tree. The solution of the problem is usually in the leaves of the tree or (in our case) the path to a leaf.

Let's look to our problem. I decide to make a table containing 7 elements with indexes from 0 to 6. The starting position is LLL_RRR. Each element has its position, its letter and new possible position. In the starting position, there are two possible moves : "L from 2 to 3" and "R from 4 to 3". We can decide to take the first possibility in each step. So let's take the move "L from 2 to 3". The new situation is LL_LRRR.

Now we have also two possibilities: "L from 1 to 2" or "R from 4 to 2". We take the first one and the new situation is L_LLRRR.

In third step there is only one possible move : "L from 0 to 1". New situation is _LLLRRR.

We don't have any possible move left and we didn't reach the goal. So we must go back for one step. We have to resume the old situation: L_LLRRR. In this situation, there was only one possible move, so we must go one more step back and resume the situation: LL_LRRR. Since we exploited the first possibility and we didn't reach the goal, we take the other possible move: "R from 4 to 2". The new situation is LLRL_RR.

We continue the procedure until we reach the goal or we have run out of possible moves.

In the picture, we see at the most left level the first two possible moves. With red forecolor are signed moves that were taken. With black backcolor are signed moves that were taken but cancelled because they didn't lead to the goal.

After the first move, "L from 2 to 3" we see, that moves "L from 1 to 2" and "L from 0 to 1" don't lead to the end of the game. So we take the alternative second move, "R from 4 to 2". In the third step, we explore the possible move "L from 3 to 4". Since this is not a winning one, we have to take the move "R from 5 to 4". We continue this procedure until we reach the goal. We also have to think that the game can't be solved.

Using the Code

For the solution, I've programmed a method called TryThis. It is a recursive method, so it is using an edge condition and a recursive call. The edge condition is reached when there are no more elements left in the array of all possible moves.

The method TryThis takes one parameter which describes the number of the step (or the depth of the tree - for example "L 1 2" and "R 4 2" have the same step number).

First, I declared a struct solutionData, which describes one step of the solution.

public struct solutionDataa
    {
        public int oldIndex;
        public int newIndex;
        public char ch;
    }

The code of method TryThis is as follows:

private bool TryThis(int i)
        {
            bool success = false;
            //find all possible moves in a situation
            ArrayList a = FindAll(s, i);
            int last = a.Count;
            int j = 0;
            //lookup all possible moves
            while (!success && last != j)
            {
                solutionData c = (solutionData)a[j];
                writeMove(c);
                if (TheEnd()) return true;
        //recursive call
        success = TryThis(i + 1);
                if (!success)
                {
                    //cancel the move
                    GoBack(i, c);
                    //try the next possible move
                    j++;
            }
            return success;

        }

In the method TryThis, we call the method FindAll. With this method, we find all possible moves in a "situation" and we return the moves in an ArrayList. With "situation" I mean diverse positions of L and R frogs (for example L_LLRRR or _LLLRRR).

private ArrayList FindAll(StringBuilder s, int k)
       {
           //finds all possible moves on level k
           ArrayList a = new ArrayList();
           solutionData b = new solutionData();
           for (int i = 0; i < 7; i++)
           {
               if (i < 6)
                   if (s[i] == 'L' && s[i + 1] == ' ')
                   {
                       b.oldIndex = i;
                       b.newIndex = i + 1;
                       b.ch = 'L';
                       a.Add(b);
                   }
               if (i < 5)
                   if (s[i] == 'L' && s[i + 1] == 'R' && s[i + 2] == ' ')
                   {
                       b.oldIndex = i;
                       b.newIndex = i + 2;
                       b.ch = 'L';
                       a.Add(b);
                   }
               if (i > 0)
                   if (s[i] == 'R' && s[i - 1] == ' ')
                   {
                       b.oldIndex = i;
                       b.newIndex = i - 1;
                       b.ch = 'R';
                       a.Add(b);
                   }
               if (i > 1)
                   if (s[i] == 'R' && s[i - 1] == 'L' && s[i - 2] == ' ')
                   {
                       b.oldIndex = i;
                       b.newIndex = i - 2;
                       b.ch = 'R';
                       a.Add(b);
                   }
           }
           return a;
       }

I've tried to present the solution in three different ways. First I've used a ListBox to view, if my solution works. Then I've added a TreeView. In TreeView, you can see how the computer makes his moves. In the end, I've added a simulation of the game.

With the program, you can also play the game. For this purpose (and for the simulation), I decided to create a UserControl called ATable. The control contains a TableLayoutPanel with labels (for the position of the frog) and seven buttons. These buttons share a lot of properties, so I put them in a table of buttons.

Button[] frog = new Button[7];

Each button is initialized with the letter (L or R) and has registered an event handler called LegalMove.

EventHandler LegalMove;
public ATable()
        {
            .......
            LegalMove = new EventHandler(MoveB);
            for (int i = 0; i < 7; i++)
            {
                frog[i] = new Button();
                .....
                frog[i].Click += LegalMove;
                tLP.Controls.Add(frog[i], i, 1);

            }
        }

Method MoveB moves the button to the left or to the right. To validate if the move is legal, I've used a StringBuilder variable called situation. After each move, the control changes the variable situation.

In the program, we also need to fire an event when a user makes a move. So I've added an event called NextM.

public delegate void Next(int position);
public event Next NextM;

The parameter of the event is the position of the button which was moved. The event is fired on every click on the button.

private void MoveB(object sender, EventArgs e)
        {
            if (((Button)sender).Text == "L")
                MoveFromLeftToRight(situation, tLP.GetColumn((Button)sender));

            else
                MoveFromRightToLeft(situation, tLP.GetColumn((Button)sender));
            if (NextM != null)
                //fire the event
                this.NextM(tLP.GetColumn((Button)sender));
        }

In the main form, I've put an object of type ATable and then I've programmed the event handler:

private void aTable1_NextM(int position)
        {
            if (TheEnd())
                MessageBox.Show("Congratulations! You won!",
                                "The end",
                                 MessageBoxButtons.OK,
                                 MessageBoxIcon.Information);
            else
                if (NoMovePossible())
                {
                    MessageBox.Show("No more moves are possible\n",
                                     "The end",
                                      MessageBoxButtons.OK,
                                      MessageBoxIcon.Information);
                    //reset game
                    aTable1.ResetSituation();

                }
        }

Points of Interest

We could program a new user control with pictures of frogs instead of buttons. The program should work with small changes.

My program doesn't search all the solutions for the game. When it finds the first sequence of moves, which leads to the goal, it ends. You can see the unexploited moves in the TreeView. They have a white background and black text color.

With the same algorithm, we could solve other problems like eight queens on a chess board or search the way through a labyrinth.

History

• 18^th August, 2008: This is the first version of the program. It is meant to learn one basic programming algorithm. By the way, we also learn how to make a new user control in combination with existing user controls.