13,449,583 members (39,522 online)
alternative version

#### Stats

37.1K views
16 bookmarked
Posted 21 Aug 2008

# Frogs Game

, 21 Aug 2008
In this article, we explain the backtracking algorithm which is a refinement of brute force approach.

## 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

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.

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.

Situation after the second step

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

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.

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';
}
if (i < 5)
if (s[i] == 'L' && s[i + 1] == 'R' && s[i + 2] == ' ')
{
b.oldIndex = i;
b.newIndex = i + 2;
b.ch = 'L';
}
if (i > 0)
if (s[i] == 'R' && s[i - 1] == ' ')
{
b.oldIndex = i;
b.newIndex = i - 1;
b.ch = 'R';
}
if (i > 1)
if (s[i] == 'R' && s[i - 1] == 'L' && s[i - 2] == ' ')
{
b.oldIndex = i;
b.newIndex = i - 2;
b.ch = 'R';
}
}
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;

}
}```

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.

## About the Author

 Instructor / Trainer Tehniški šolski center Nova Gorica 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

 First Prev Next
 Other Versions done in Flash and Delphi Edy17-Jan-17 11:56 Edy 17-Jan-17 11:56
 Re: Other Versions done in Flash and Delphi BarbaraPušnar25-Jul-17 2:18 BarbaraPušnar 25-Jul-17 2:18
 pertanyaan dan permintaan Ervan Sahidin A6-Jan-16 1:48 Ervan Sahidin A 6-Jan-16 1:48
 cute:) I liked it! Member 44110571-Nov-08 20:09 Member 4411057 1-Nov-08 20:09
 Another way... Avenue6021-Aug-08 5:49 Avenue60 21-Aug-08 5:49
 Kua-kua :) Vitaly Tomilov21-Aug-08 4:01 Vitaly Tomilov 21-Aug-08 4:01
 I bet you are seeing them at night when sleeping... one over another, and another, and another... Professional System Library on www.prosyslib.org
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Mar-18 17:10 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.