Noah’s Ark Backtracking Algorithm

In this challenge, we are going to use a backtracking algorithm to solve a puzzle game called Noah’s Ark.

First, you will need to fully understand how the game works. You can check the “How To Play” tab on this page. The game consists of trying to fill up Noah’s Ark by positioning different pieces on a grid. Each piece represents an animal. The pieces come in different shapes (to some extent similar to the shapes using in a Tetris game) and different colours. Each colour represents an animal and, for each animal, there are two pieces of different shapes. The animals are:

• 2 Lions (yellow),
• 2 Zebras (red),
• 2 Hippopotamus (blue),
• 2 Giraffes (yellow),
• 2 Elephants (purple).

There are just enough spaces/cells on the grid to fit all the pieces/animals. The rule is that two pieces of the same colour must be adjacent (have at least one edge in common).

The game starts with a given grid where 1,2, or 3 animals/pieces are already positioned. The player can then use a trial and error approach to position all the remaining pieces on the grid. Each puzzle (starting grid) should have a unique solution.

To implement this game in Python, we will use a 2D array to represent the ark with all its cells.

All our animals will also be stored as 2D arrays using different values to represent each colour:

A backtracking algorithm is a recursive algorithm that will test potentially every possible position of the different pieces of the game, one by one. To reduce the number of possibilities, a backtracking algorithm will try to identify as soon as possible, when an incomplete grid can be discarded as it will not lead to a solution. (Without the need to investigate different moves to complete the grid, hence saving some processing time!).

In our backtracking algorithm, we are positioning one piece at a time on the ark (the 2D grid). A soon as we place a piece on the grid, we check if the piece is in a valid position. If not we try a different position for the piece. If there is no valid position for the piece on the grid, we backtrack one step, cancelling the previous move and we then resume our search for a solution from there.

In the algorithm, an invalid position is defined as follows:

• When positioning the piece, if we create an isolated blank cell, the grid can be discarded as it will be impossible to fill it in later on: All pieces in the game need a gap of at least two consecutives empty cells,
• If both pieces of the selected colour (both animals of a pair) are on the grid, then we check that the two pieces are adjacent. If not, the grid is not a valid one and can be discarded.

Each puzzle to solve will always start with an initial grid with 1, 2 maybe 3 pieces already placed on the grid. Each puzzle should have a unique solution.

For this demo, we will use the following initial grid, with just one piece already in place:

Our Solution

When running this code, you can see how the algorithm is trying to find a solution by shifting different pieces on the grid, one at a time and applying a trial and error approach, backtracking a few steps when a grid cannot be solved.

The algorithm is first trying to position the second blue piece as follows:

However this position is immediately discarded as the two blue pieces are not adjacent.

The second position to be investigated is as follows:

Once again, this position is immediately discarded as the two blue pieces are not adjacent.

The third position to be investigated by the algorithm is as follows:

In this case, the two blue pieces are adjacent, however the algorithm is discarding this position too because it has generated an isolated empty space (in the top right corner of the ark).

The 4th position to be investigated is as follows:

This position is a valid position, so the algorithm can investigate it further by starting to place other pieces till it either finds a solution or backtracks to test a fifth position of the blue piece and so on…

Python Code

You can change the SPEED constant on line 3 to speed up/slow down the algorithm. We are pausing the algorithm for a few milliseconds between each move for visualisation purpose only.