An Integer Linear Programming Model for the Evolomino Puzzle
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916015161475072 |
|---|---|
| author | Nikolaev, Andrei V. Myasnikov, Yuri A. |
| author_facet | Nikolaev, Andrei V. Myasnikov, Yuri A. |
| contents | Evolomino is a pencil-and-paper logic puzzle published by the Japanese company Nikoli, renowned for culture-independent puzzles such as Sudoku, Kakuro, and Slitherlink. Its name reflects the core mechanic: the polyomino-like blocks drawn by the player must gradually "evolve" according to the directions indicated by arrows pre-printed on a rectangular grid.
In this paper, we formalize the rules of Evolomino as an integer linear programming (ILP) model, encoding block evolution, connectivity, and consistency requirements through linear constraints. Furthermore, we introduce an algorithm for generating random Evolomino instances, utilizing this ILP framework to ensure solution uniqueness. Computational experiments on a custom benchmark dataset demonstrate that a state-of-the-art CP-SAT solver successfully handles puzzle instances of up to $10 \times 10$ within one second and up to $18 \times 18$ within one minute. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09483 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Integer Linear Programming Model for the Evolomino Puzzle Nikolaev, Andrei V. Myasnikov, Yuri A. Optimization and Control Combinatorics 90C10, 90C27, 90C90, 00A08, 05B50 Evolomino is a pencil-and-paper logic puzzle published by the Japanese company Nikoli, renowned for culture-independent puzzles such as Sudoku, Kakuro, and Slitherlink. Its name reflects the core mechanic: the polyomino-like blocks drawn by the player must gradually "evolve" according to the directions indicated by arrows pre-printed on a rectangular grid. In this paper, we formalize the rules of Evolomino as an integer linear programming (ILP) model, encoding block evolution, connectivity, and consistency requirements through linear constraints. Furthermore, we introduce an algorithm for generating random Evolomino instances, utilizing this ILP framework to ensure solution uniqueness. Computational experiments on a custom benchmark dataset demonstrate that a state-of-the-art CP-SAT solver successfully handles puzzle instances of up to $10 \times 10$ within one second and up to $18 \times 18$ within one minute. |
| title | An Integer Linear Programming Model for the Evolomino Puzzle |
| topic | Optimization and Control Combinatorics 90C10, 90C27, 90C90, 00A08, 05B50 |
| url | https://arxiv.org/abs/2603.09483 |