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] |
Things are not going well for the villagers that live near the dark volcano that dominates the landscape. The smoke and ash the billows from the inaccessible crater is only a minor problem, far worse are the horrible creatures that dwell in the crevices that split the mountain’s flanks. And lurking somewhere deep within the lava-fulled depths – Ashardalon awaits!
The ultimate goal changes depending on the scenario chosen at the start of the game. In our most recent game we had to fight our way through the random tunnels to find a special tile that opened into a large chamber filled with monsters led by a special “villain” monster with extra abilities. Our first attempt failed utterly but we got there in the end.
I don’t use my computer for games much these days, but I have been playing a bit of 
Or not so simple. There are 8 role cards, each player will get one of these each turn which will enable certain actions. For instance, the Magician role can swap hands with another player, the Architect can build more in a turn, the King gets first choice of roles for next turn, etc. Because there are more roles than players and the roles are chosen secretly in turn, the way to win lies in choosing the correct role at the correct time. Some of the more expensive districts also confer additional bonuses apart for score such as more money or protection from certain attacks so thinking several turns ahead is required.
Secondly, The Spoils is a collectable card game just like Magic the Gathering. Seriously, it is basically Magic with a quick paint job and the VIN ground off. This is not necessarily a bad thing – I like Magic the Gathering, but the similarities are pretty blatant. I can almost imagine playing a Spoils deck against a Magic deck in the same game, most of the rules work in exactly the same way, only with different keywords (cards don’t get tapped, they become “depleted”, etc.)
Having said that, Spoils does differ in a few interesting ways which seem to be designed to make the decks play more consistently. A common problem with Magic is that sometimes you just don’t draw enough land cards of the correct type to play your hand full of spells. In The Spoils, you start the game with two staple resources (basic land) cards of your choice already in play – this hugely helps if you are running a 2 colour deck since you can ensure that you have both colours available.
You can play any card in your hand as a resource by playing it face down. These work just like regular resources but do not count towards threshold at all. Although you can usually only play a single resource a turn, you can deplete 3 resources to put another resource into play at any time. 
If you are getting a bunch of guys together to play a board game, you may as well make it a nerdy one. 