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.
No comments:
Post a Comment