An Integer Linear Programming Model for the Evolomino Puzzle

This paper presents an integer linear programming model to formalize the rules of the Nikoli puzzle Evolomino and introduces an algorithm for generating unique instances, demonstrating that state-of-the-art solvers can efficiently solve grids up to 18x18.

The Gist

Imagine you have a new, tricky logic puzzle called Evolomino. It's like a mix between drawing shapes on graph paper and playing a game of "follow the leader," but with a twist: the shapes you draw have to grow and change in a very specific way.

This paper is about two main things:

1. Teaching a computer how to solve these puzzles using a mathematical "recipe" (called an Integer Linear Programming model).
2. Building a machine that can create brand-new, fair puzzles that only have one correct answer.

Here is the breakdown of how they did it, using some everyday analogies.

1. The Puzzle: Growing Shapes on a Grid

Think of the puzzle board as a checkerboard. Some squares are shaded (like rocks you can't step on), and some are white.

• The Arrows: On some white squares, there are pre-drawn arrows.
• The Goal: You must draw squares to form "blocks" (like Tetris pieces).
• The Rules:
  • Every block must touch an arrow.
  • An arrow must pass through at least two blocks.
  • The "Evolution" Rule: This is the tricky part. If an arrow points from Block A to Block B, Block B must be exactly like Block A, but with one extra square added. You can't rotate it or flip it; you just slide it and add a piece. It's like a caterpillar growing a new segment as it moves forward.

2. The Computer's "Recipe" (The ILP Model)

The authors realized that instead of guessing and checking, they could write a strict set of rules (a mathematical model) that describes the puzzle perfectly. They call this an Integer Linear Programming (ILP) model.

Think of this model as a super-strict bouncer at a club. The bouncer has a checklist:

• "Is this square filled? Yes/No."
• "Did this shape grow by exactly one square?"
• "Are all the squares in this shape connected, like a single piece of dough, or are they floating apart?"
• "Did the shape move in the direction of the arrow without spinning?"

The computer doesn't "think" like a human; it just checks millions of combinations against this checklist until it finds the one arrangement where every single rule is satisfied.

The "Flow" Trick:
One of the hardest parts is making sure a shape is connected (no floating islands). The authors used a clever trick called a "Flow" model. Imagine pouring water into the shape.

• One square is the "faucet" (the source).
• The water flows to every other square in that shape.
• If the shape is broken into two pieces, the water can't reach the second piece. The computer sees this and says, "Nope, that's not a valid shape," and tries again.

3. Building the Puzzles (The Generator)

Once they had the "bouncer" (the solver), they needed a way to make new puzzles. They built a Puzzle Generator.

Imagine a robot painter:

1. It starts with a blank board.
2. It randomly draws arrows and places some starting squares.
3. It asks the "bouncer," "Hey, does this setup have a solution?"
4. If the answer is "Yes, and it's unique," the robot keeps it.
5. If the answer is "No solution" or "Too many solutions," the robot erases it and tries again.

Finally, the robot plays a game of "Whac-A-Mole." It takes away clues (erases some squares or arrows) one by one. After every erasure, it asks the bouncer, "Is the answer still unique?" If yes, it keeps the erasure. If no, it puts the clue back. This ensures the final puzzle is as simple as possible but still has only one correct answer.

4. The Results: How Fast is It?

The authors tested their system on a custom set of puzzles, ranging from small (5x5) to large (18x18).

• The Winner: They tried four different computer solvers. One, called CP-SAT, was the clear champion. It's like the Formula 1 car of puzzle solvers.
• The Speed:
  • Small puzzles (up to 11x11): Solved in less than one second. Faster than you can blink.
  • Medium puzzles (up to 14x14): Solved in about five seconds.
  • Large puzzles (up to 18x18): Solved in under one minute.

For a puzzle that looks like it might take a human an hour to solve, the computer did it in seconds.

Why Does This Matter?

This paper is a bridge between fun and math.

• For Puzzle Lovers: It proves that even complex, new puzzles can be cracked with modern math.
• For Computer Scientists: It shows that even though these puzzles are theoretically "hard" (mathematicians call them NP-complete), modern computers are so fast that we can solve them practically in real-time.

In short, the authors took a pencil-and-paper game, wrote a strict rulebook for a computer, built a machine to create new levels, and showed that a modern computer can beat the puzzle almost instantly. It's like teaching a robot to play a game of logic so well that it becomes a grandmaster in a heartbeat.

Technical Summary

Here is a detailed technical summary of the paper "An Integer Linear Programming Model for the Evolomino Puzzle" by Andrei V. Nikolaev and Yuri A. Myasnikov.

1. Problem Definition: Evolomino

Evolomino is a pencil-and-paper logic puzzle published by Nikoli (the creators of Sudoku and Kakuro) in March 2023. The game is played on a rectangular grid containing white and shaded cells. Some white cells contain pre-drawn squares and arrows.

Core Rules:

• Blocks: The player must draw squares in white cells to form "blocks" (polyominoes). Each block must contain exactly one pre-drawn arrow.
• Evolution: Arrows indicate a path. The blocks along an arrow must "evolve." The first block contains the arrow's start. Each subsequent block in the sequence must be formed by adding exactly one square to the previous block.
• Constraints:
  • No rotation or flipping is allowed during evolution; the shape is preserved via translation only.
  • Every arrow must pass through at least two blocks.
  • No two consecutive squares along an arrow's path can be empty (implied by the block structure).
  • Blocks must be connected polyominoes.
• Complexity: The decision problem (determining if a valid solution exists) is NP-complete, and the counting problem (determining the number of solutions) is #P-complete.

2. Methodology: The ILP Model

The authors formulate the puzzle as an Integer Linear Programming (ILP) model. The model uses binary and integer variables to encode the grid state, block formation, connectivity, and evolution rules.

2.1 Variables

• Cell Variables ($x_i$): Binary variables indicating if a cell contains a square (1) or is empty/shaded (0).
• Block Variables ($y^k_{a,i}$): Binary variables indicating if cell $i$ belongs to block $k$ along arrow $a$.
• Activation Variables ($b^k_a$): Binary variables indicating if block $k$ on arrow $a$ exists.
• Flow Variables ($f^{k}_{ij}$): Integer variables representing flow between adjacent cells to enforce polyomino connectivity (adapted from the Gavish-Graves model).
• Translation Variables ($t^k_j$): Binary variables indicating the specific shift (translation) applied to evolve block $k-1$ into block $k$.

2.2 Key Constraints

The model enforces rules through several groups of linear constraints:

1. Assignment: Every square belongs to exactly one block.
2. Arrow Spacing: No two consecutive squares along an arrow can be part of the same block (enforcing the "evolution" step).
3. Block Activation: Blocks are activated sequentially; block $k$ cannot exist if block $k-1$ does not.
4. Size Progression: The size of block $k$ must be exactly one unit larger than block $k-1$.
5. Connectivity (Flow Conservation): A flow-based mechanism ensures that all squares in a block form a single connected component. A "source" cell (the one on the arrow) generates flow equal to the block size, which must reach all other cells in the block.
6. Evolution (Shape Preservation): Constraints ensure that block $k$ is a translation of block $k-1$ plus one new square. This is achieved by linking the translation variables to the spatial coordinates of the squares, ensuring no rotation or reflection occurs.

2.3 Model Complexity

• Variables: $O(K \cdot |C|)$, where $K$ is the total number of blocks and $|C|$ is the number of cells.
• Constraints: $O(K \cdot |C|^2)$. The most computationally expensive constraints are those preserving the geometric shape during evolution (correspondence constraints).
• Scale: A $10 \times 10$ puzzle results in ~5,000 variables and ~55,000 constraints.

3. Puzzle Generation Algorithm

To create a benchmark dataset, the authors developed a generator (Algorithm 1) that produces puzzles with guaranteed unique solutions:

1. Construction: Starts with an empty grid and uses a biased random walk to draw arrows.
2. Block Placement: For each arrow, it randomly places an initial block and then iteratively evolves subsequent blocks, checking for conflicts (overlaps or invalid shapes).
3. Uniqueness Verification (Carving): Once a valid board with a solution is found, the algorithm greedily removes clues (squares and shading) in random order.
   • After each removal, it calls the ILP solver to check if an alternative solution exists.
   • If a new solution is found, the clue is restored.
   • This process continues until the puzzle has a minimal set of clues that still yields a unique solution.
   • Note: For very large grids ($>14 \times 14$), the uniqueness check was relaxed due to computational cost, generating puzzles with guaranteed but not necessarily unique solutions.

4. Computational Results

The authors evaluated the model using the Google OR-Tools suite on a custom dataset of 700 puzzles (sizes $5 \times 5$to$18 \times 18$).

4.1 Solver Comparison

Four solvers were tested on $10 \times 10$ instances:

• CP-SAT (Constraint Programming/SAT): The clear winner. Solved 100% of instances within 180 seconds.
• SCIP & BOP: Solved 94% and 94% respectively.
• CBC: Solved 92%.
• Observation: CP-SAT solved 48/50 instances in under 1 second, whereas CBC solved only 7.

4.2 Performance Scaling

Using CP-SAT on the full dataset:

• $11 \times 11$: Median solve time < 1 second.
• $14 \times 14$: Median solve time < 5 seconds.
• $18 \times 18$: Median solve time ~48 seconds (max ~60 seconds).
• Trend: Solve time grows exponentially with grid size, consistent with the cubic growth of constraints relative to grid dimensions.
• Resource Usage: An $18 \times 18$ puzzle involved approximately 40,000 variables and 1,000,000 constraints, yet was solved efficiently.

5. Key Contributions

1. Formalization: The first formalization of Evolomino rules into a rigorous Integer Linear Programming model.
2. Connectivity & Evolution Logic: Novel application of flow-based constraints for polyomino connectivity and specific translation constraints to enforce the "evolution" mechanic without rotation.
3. Generator: A robust algorithm for generating random Evolomino instances with verified unique solutions, addressing the lack of existing datasets.
4. Empirical Benchmark: Established a performance baseline for logic puzzles of this type, demonstrating that modern CP-SAT solvers can handle complex polyomino evolution puzzles up to $18 \times 18$ efficiently.

6. Significance

This work bridges the gap between recreational logic puzzles and combinatorial optimization. It demonstrates that despite the NP-completeness of Evolomino, modern solvers (specifically CP-SAT) can handle non-trivial instances effectively. The paper provides a template for modeling other "evolving" or "growing" polyomino puzzles and contributes to the theoretical understanding of Nikoli-style puzzles, which have historically been under-studied in computer science literature compared to Sudoku or Kakuro. Future work suggested includes exploring DLX (Dancing Links) algorithms or SAT-based reductions.