Click here to Skip to main content
Click here to Skip to main content
Go to top

Frogs Game

, 21 Aug 2008
Rate this:
Please Sign up or sign in to vote.
In this article, we explain the backtracking algorithm which is a refinement of brute force approach.
Frogs_src

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.

Starting position

Starting position

Goal

Goal

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.

After first step

Situation after the first step

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.

After second step

Situation after the second step

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

After third step

Situation after the third step

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.

Two steps back one forward

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

Tree of possibilities

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

  • 18th 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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

BarbaraPušnar
Instructor / Trainer Tehniški šolski center Nova Gorica
Slovenia Slovenia
I have a degree in mathematics, but I've worked as a programmer and now I teach programming in high school in Slovenia.

Comments and Discussions

 
Generalcute:) I liked it! PinmemberMember 44110571-Nov-08 20:09 
Smile | :)
GeneralAnother way... PinmemberAvenue6021-Aug-08 5:49 
JokeKua-kua :) PinmemberVitaly Tomilov21-Aug-08 4:01 

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
Web01 | 2.8.140916.1 | Last Updated 21 Aug 2008
Article Copyright 2008 by BarbaraPušnar
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid