How to Solve the Lattice Bacteria Puzzle: Vacate a 4x4 Grid in 3 Moves Explained

The Lattice Bacteria Puzzle presents a fascinating challenge that blends discrete mathematics with spatial logic. At its core, the game operates on a simple yet restrictive set of rules that dictate how 'bacteria' or cells occupy a grid. You begin with a single cell at the origin, the coordinate (0,0). The objective is not to fill the board, but rather to move cells in such a way that you can eventually clear a designated area. This specific puzzle, created in collaboration with the National Museum of Mathematics (MoMath), invites participants to find the most efficient path to vacating a 4x4 box. Understanding the mechanics of replication is the first step toward finding a solution.

In this system, a move consists of selecting an existing cell and allowing it to 'replicate.' However, this is not a simple duplication. When a cell replicates, it disappears from its current location and populates the spot directly above it and the spot directly to its right. This transformation from one cell to two follows a strict geometric progression that pushes the population away from the origin and toward the positive quadrants of the Cartesian plane. The logic mirrors certain types of cellular automata where local rules define global outcomes.

However, the replication is governed by an 'exclusivity rule.' A cell can only replicate if both of its target positions—the space above and the space to the right—are currently unoccupied. If even one of these spots is blocked by another bacterium, the chosen cell must remain stationary until the path is cleared. This constraint introduces a significant layer of strategic depth, as the order of operations becomes critical to avoiding gridlock. To clear the origin and its surrounding areas, one must carefully manage the population flow.

The specific challenge posed in this MoMath collaboration is to clear a square region defined by the corners (0,0), (0,3), (3,3), and (3,0). This region contains exactly 16 lattice points. While it might seem intuitive that moving bacteria 'out' of this box is simple, the replication rule means that every move intended to clear a spot creates two new cells further along the grid. The puzzle asks for the smallest number of moves required to ensure that all 16 of these specific points end up empty. This is a classic optimization problem that requires a deep understanding of the 'cost' of each replication.

Clearing the box is difficult because every time you move a cell from a lower coordinate to a higher one, you are essentially 'paying' with space. You cannot simply move a cell out of the box without potentially blocking another cell's path or occupying a spot that you previously cleared. This creates a push-and-pull dynamic where players must visualize several moves ahead. The puzzle is not just about the final state, but the sequence of intermediate states that allow for maximum mobility across the lattice.