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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#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?