Frog Puzzle (Backtracking Algorithm)

This challenge is based on this Frog puzzle board game.

At the start of the game several green frogs and one red frog are positioned on the board/pond on different waterlilies based on a given configuration. (The game comes with a set of cards, each card describing one different configuration / puzzle to solve).

Here is an example of initial configuration:

The aim of this game is to remove all the green frogs from the board/pond so that only the red frog remains on the board. A frog is removed from the board when it falls off its waterlily. This happens when another frog hops above its head:

When a frog is on a waterlily, it can jump over adjacent waterlilies only when:

• There is another green frog on the adjacent waterlily,
• The waterlily where the frog would land is empty.

The aim of this programming challenge was to design and implement an algorithm to search for a solution to this puzzle using a trial-and-error approach. This can be done in Python using a backtracking algorithm which will identify the possible moves on the board, and try these moves until it either finds a solution (only one red frog remains on the board) or reaches a dead end (when several frogs are left on the board but can no longer jump around). If after moving frogs around a dead end, is met, the algorithm will backtrack to previous moves to try alternative possible moves.

The possible moves a frog can do depend on its position on the board as well as the position of other frogs. For instance, here are two different diagrams to show potential moves of a frog placed on the top-left waterlily (0) or on the central waterlily (6):

By investigating all the possible moves from each waterlily we can construct a weighted graph where:

• The nodes of the graph are the thirteen waterlilies (0 to 12),
• The weight for each edge of the graph is number of the waterlily that is being jumped over.

This approach results in the following weighted graph:

In Python, a graph can be stored as a dictionary of lists. Each key of the dictionary represents a node, the value associated to each key is a list of edges. Each edge will contain a sub-list of two values: the node/waterlily being reached and the waterlily being jumped over (the weight of the edge).

Here is how the above graph is implemented in Python:

#The graph representing all the potential jumps a frog can do
pond = {0:[[2,1],[6,3],[10,5]],
        1:[[5,3],[11,6],[7,4]],
        2:[[0,1],[6,4],[12,7]],
        3:[[9,6]],
        4:[[8,6]],
        5:[[1,3],[7,6],[11,8]],
        6:[[0,3],[2,4],[12,9],[10,8]],
        7:[[1,4],[5,6],[11,9]],
        8:[[4,6]],
        9:[[3,6]],
        10:[[0,5],[6,8],[12,11]],
        11:[[5,8],[1,6],[7,9]],
        12:[[10,11],[6,9],[2,7]]
       }

Python Code

You can investigate here the full Python code used to implement our backtracking algorithm using a recursve function called jumpAround().

A step further…

• Could a similar approach be used to solve a game of solitaire?
• Could a similar approach be used to implement an AI for a player play a game of draughts against the computer?