A few months ago I came across the following puzzle in a video game I was playing:

Three frogs are happily hopping along a narrow board together when they meet another group of three frogs traveling in the opposite direction. These frogs can only move in the direction they are facing, and only if there is a space directly in front of them. Additionally, a frog can jump over the frog in front but only if there is clear space on the other side to land in.

How can the frogs (moving one at a time) pass each other and continue on their way?

Of course, this is a hoary old puzzle that most people come across and solve as children. It should be only a couple of minutes work with a pen and paper to confirm that it is possible to exchange both sets of frogs but I wouldn’t be much of a programmer if I used a piece of paper where hundreds of dollars of computer equipment would do just as well.

To solve a puzzle like this programatically requires three things: a representation of the current state of the problem, a way of generating every possibly legal move from a given position, and a way of figuring out when is a good time to stop.

Firstly, the representation of the board is a simple python list:

1

start = [1, 1, 1, 0, -1, -1, -1]

Frogs traveling right or left are represented by “1″ and “-1″ respectively. Empty spaces that frog can move into are represented by “0″. The advantage of this representation is that you can calculate the new position of a frog by:

1

newPos = pos + (representation * distance)

where pos is the current index in the array, distance is the size of the hop (either 1 or 2) and representation is either 1 or -1.

Next, we need a way of generating legal moves for a given position:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def legalMoves(board):
	moves = []
	for pos, piece in enumerate( board ):
		jumpmove = pos + (piece * 2)
		move = pos + (piece)
		if ( piece == 0 ):
			continue
		if (not (( jumpmove < 0 ) or ( jumpmove >= len(board)))):
			if (board[jumpmove] == 0):
				t = list(board)
				t[pos] = 0
				t[jumpmove] = piece
				moves.append(t)
		if (not ((move < 0) or ( move >= len(board)))):
			if ( board[move] == 0):
				t = list(board)
				t[pos] = 0
				t[move] = piece
				moves.append(t)
	return moves

Now we need a way of keeping track of all board positions we have seen, so once we find the target we can print the states that led to the solution:

1
2
3
4
5
6
7
8
9
10
11

def evalAll( current, target ):
	next = []
	for a in current:
		n = legalMoves(a[-1])
		for q in n:
			t = list(a)
			t.append(q)
			if ( q == target ):
				return t
			next.append(t)
	return next

This code keeps a list of lists, each sublist being it’s own list of the sequence of moves investigated so far. For each sequence of moves, the next legal moves are discovered and new sequences are added to be investigated the next time this function is called. Technically this is called a breadth-first search because at all of the current legal moves are investigated before moving on the next stage. This is a very simplistic way of doing the job, but in this case the puzzle is small enough that it works well enough.

Finally, a simple wrapper that we can use to set things up and return the final result.

1
2
3
4
5
6
7

def solve(start):
	temp=[[start]]
	end = list(start)
	end.reverse()
	while(temp[-1] != end):
		temp = evalAll(temp, end)
	return temp

So now we can do this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

print solve([1, 1, 1, 0, -1, -1, -1])
 
[[1, 1, 1, 0, -1, -1, -1],
 [1, 1, 0, 1, -1, -1, -1],
 [1, 1, -1, 1, 0, -1, -1],
 [1, 1, -1, 1, -1, 0, -1],
 [1, 1, -1, 0, -1, 1, -1],
 [1, 0, -1, 1, -1, 1, -1],
 [0, 1, -1, 1, -1, 1, -1],
 [-1, 1, 0, 1, -1, 1, -1],
 [-1, 1, -1, 1, 0, 1, -1],
 [-1, 1, -1, 1, -1, 1, 0],
 [-1, 1, -1, 1, -1, 0, 1],
 [-1, 1, -1, 0, -1, 1, 1],
 [-1, 0, -1, 1, -1, 1, 1],
 [-1, -1, 0, 1, -1, 1, 1],
 [-1, -1, -1, 1, 0, 1, 1],
 [-1, -1, -1, 0, 1, 1, 1]]

Success!

You might say this is a waste of time since you figured out the problem in your head. Good for you, but try this on for size:

1

[1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1, -1]