pith. sign in

arxiv: 2603.09483 · v2 · pith:OMTTGKRYnew · submitted 2026-03-10 · 🧮 math.OC · math.CO

An Integer Linear Programming Model for the Evolomino Puzzle

Andrei V. Nikolaev , Yuri A. Myasnikov This is my paper

Pith reviewed 2026-05-21 12:02 UTC · model grok-4.3

classification 🧮 math.OC math.CO
keywords Evolominointeger linear programmingpolyominologic puzzleconstraint satisfactionpuzzle generationNikoli puzzles
0
0 comments X

The pith

The rules of Evolomino translate into linear constraints of an integer linear program.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an integer linear programming model that directly encodes the evolution of polyomino blocks according to arrow directions on the grid. It adds constraints to keep blocks connected and consistent with the printed clues. This formulation lets standard solvers find solutions or confirm uniqueness. The same model supports an algorithm that creates new random puzzles guaranteed to have exactly one solution. Tests show the approach finishes 10-by-10 instances in a second and 18-by-18 instances in under a minute.

Core claim

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×10 within one second and up to 18×18 within one minute.

What carries the argument

The integer linear programming model that represents cell states and evolution directions with binary variables and enforces evolution rules, connectivity, and consistency via linear constraints.

If this is right

  • Off-the-shelf optimization solvers can solve or verify Evolomino puzzles without additional rule-specific code.
  • Random puzzles with guaranteed unique solutions can be generated at scale using the same model.
  • Performance on larger grids will improve automatically as CP-SAT or other solvers advance.
  • The formulation supplies a formal certificate of correctness for any solved or generated instance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same constraint-encoding approach could be adapted to other Nikoli puzzles that involve directional growth or connectivity.
  • Hybrid methods might combine the ILP model with local search to handle even bigger or more constrained instances.
  • The generation procedure could be modified to target specific difficulty levels by controlling the number or placement of arrows.

Load-bearing premise

The linear constraints correctly and completely capture every Evolomino rule without allowing invalid grids or forbidding valid ones.

What would settle it

A grid that satisfies the ILP constraints yet violates an Evolomino rule such as a block evolving against an arrow or losing connectivity.

Figures

Figures reproduced from arXiv: 2603.09483 by Andrei V. Nikolaev, Yuri A. Myasnikov.

Figure 1
Figure 1. Figure 1: Example of an Evolomino puzzle – Evolomino is played on a rectangular board with white and shaded cells. Some white cells contain pre-drawn squares and arrows. – The player must draw squares (□) in some of the white cells. – A polyomino-like group of squares connected vertically and horizontally is called a block (including only one square). Each block must contain exactly one square placed on a pre-drawn … view at source ↗
Figure 2
Figure 2. Figure 2: Example of region Ca for arrow a, highlighted in green For example, Koch et al. [18] demonstrated that between 2001 and 2020 com￾puter hardware became roughly 20 times faster and algorithms improved by a factor of about 50, resulting in an overall speed-up of approximately 1 000 for MILP models. Moreover, many instances considered unsolvable twenty years ago can now be solved within seconds. Therefore, onc… view at source ↗
Figure 3
Figure 3. Figure 3: An example of a flow used to verify polyomino connectivity 2.4 Connectivity variables and constraints The following group of variables and constraints ensures that each block forms a connected polyomino. To achieve this, we adapt a classic flow-based model by Gavish and Graves [10]. For each block k on each arrow a ∈ A and for every pair of adjacent cells i and j from Ca (each cell i has up to four neighbo… view at source ↗
Figure 4
Figure 4. Figure 4: Example of a translation with t a2 −7 = 1, i.e., a 7-cell backward shift; the copy of the first block inside the second along the arrow is highlighted in blue – Only one translation can be assigned to each block: X j∈T t ak j = bak ∀a ∈ A, k = 2, . . . , Ka. (19) – Each square of the block must be translated: X j∈T a i t ak j ≥ y a,k−1 i + bak − 1 ∀a ∈ A, ∀i ∈ Ca, k = 2, . . . , Ka, (20) where T a i is the… view at source ↗
Figure 5
Figure 5. Figure 5: Performance profile of the solvers on a 10 × 10 grid (180-second time limit) This comparison was performed to identify the most efficient solver for our ILP model of the Evolomino puzzle. The performance profile of this experiment is presented in [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: CP-SAT performance: median (line), IQR (shaded), and outliers (dots) one second; for grids up to 14 × 14, it stays within five seconds. Starting from 15×15, the IQR expands and outliers become more frequent, indicating that the instances become less homogeneous and the solver’s behavior less predictable. We stopped at puzzles of size 18 × 18, where the median runtime per instance (48 seconds) still remaine… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to formalize the rules of Evolomino as an ILP model by encoding block evolution, connectivity, and consistency through linear constraints. It also introduces an algorithm for generating random unique puzzle instances using this model. Experiments show CP-SAT solver solves up to 18x18 in one minute.

Significance. If the model is correct, this provides a practical tool for solving and generating Evolomino puzzles efficiently. The computational results highlight the feasibility for practical use, though the overall significance is limited by the lack of verification of the encoding's faithfulness.

major comments (2)
  1. §3: No explicit listing of the linear constraints or variables is provided for the evolution, connectivity, and consistency requirements. Without this, it is not possible to assess if the ILP correctly and completely captures the puzzle rules, which is load-bearing for the central claim.
  2. §5: The computational experiments report solving times but do not include validation against hand-solved instances or proof of model fidelity, undermining confidence in the reported results for uniqueness generation.
minor comments (2)
  1. The abstract mentions 'custom benchmark dataset' but the paper does not describe how the dataset was constructed.
  2. Some notation for the variables could be clarified with a table of definitions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's detailed feedback on our manuscript. The comments highlight important areas for improvement in clarity and validation, which we address below. We believe these revisions will strengthen the presentation of our ILP model and its applications.

read point-by-point responses

  1. Referee: §3: No explicit listing of the linear constraints or variables is provided for the evolution, connectivity, and consistency requirements. Without this, it is not possible to assess if the ILP correctly and completely captures the puzzle rules, which is load-bearing for the central claim.

    Authors: We agree that providing an explicit enumeration of the variables and constraints would enhance the transparency and verifiability of the model. In the revised manuscript, we will add a new subsection in Section 3 that lists all decision variables and formulates each constraint explicitly, including those for block evolution (e.g., arrow-directed growth rules), connectivity (ensuring polyomino-like structures), and consistency (matching pre-printed arrows and grid boundaries). Each constraint will be accompanied by a brief explanation of its role in capturing the Evolomino rules. This addition directly addresses the concern and allows readers to verify the encoding's completeness. revision: yes

  2. Referee: §5: The computational experiments report solving times but do not include validation against hand-solved instances or proof of model fidelity, undermining confidence in the reported results for uniqueness generation.

    Authors: We recognize the value of empirical validation for establishing model fidelity. To address this, we will expand Section 5 to include a validation subsection. This will describe how we tested the ILP model on small puzzle instances (e.g., 5x5 grids) that were independently solved by hand, confirming that the solver outputs match the expected unique solutions. We will also report on the generation algorithm's ability to produce instances with verified uniqueness. These additions will provide concrete evidence supporting the correctness of the encoding and the reliability of the uniqueness results. revision: yes

Circularity Check

0 steps flagged

No significant circularity in ILP formalization of Evolomino rules

full rationale

The paper directly encodes Evolomino rules (block evolution via arrows, polyomino connectivity, and consistency) as standard linear constraints in an ILP model, then applies an off-the-shelf CP-SAT solver to solve instances and generate unique puzzles. No derivation step reduces to its own inputs by construction: there are no fitted parameters renamed as predictions, no self-definitional variables, and no load-bearing self-citations or uniqueness theorems imported from prior author work. Solver runtimes are external empirical measurements on benchmark instances, not quantities defined circularly from the model itself. The approach is a straightforward modeling translation with independent computational validation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the assumption that Evolomino rules admit a complete linear encoding and that the CP-SAT solver returns correct feasibility and optimality results for the generated instances. No free parameters or invented entities are introduced; the work uses standard ILP machinery.

axioms (2)
  • domain assumption Evolomino rules (block evolution, connectivity, consistency) can be expressed exactly as a finite set of linear equality and inequality constraints over integer variables.
    Stated in the abstract as the basis for the ILP model; if false, the entire formulation is invalid.
  • standard math A state-of-the-art CP-SAT solver returns correct answers for the feasibility and uniqueness queries posed by the model.
    Implicit in the computational experiments section of the abstract.

pith-pipeline@v0.9.0 · 5687 in / 1492 out tokens · 55120 ms · 2026-05-21T12:02:23.741193+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 1 internal anchor

  1. [1]

    Puzzle Communication Nikoli182(2023)

    work page 2023

  2. [2]

    Journal of Online Mathematics and its Ap- plications8(1) (2008)

    Bartlett, A., Chartier, T.P., Langville, A.N., Rankin, T.D.: An integer program- ming model for the Sudoku problem. Journal of Online Mathematics and its Ap- plications8(1) (2008)

    work page 2008

  3. [3]

    International Review of Economics and Management10(2), 38–49 (2022)

    Bitgen Sungur, B.: An integer programming formulation for the Futoshiki puzzle. International Review of Economics and Management10(2), 38–49 (2022)

    work page 2022

  4. [4]

    Optima65, 16–17 (2001)

    Bosch, R.A.: Painting by numbers. Optima65, 16–17 (2001)

    work page 2001

  5. [5]

    Theoretical Computer Science975, 114138 (2023)

    Burkardt, J., Garvie, M.R.: An integer linear programming approach to solving the Eternity puzzle. Theoretical Computer Science975, 114138 (2023). https:// doi.org/10.1016/j.tcs.2023.114138

    work page doi:10.1016/j.tcs.2023.114138 2023

  6. [6]

    youtube.com/watch?v=yV7GDJo_8zo

    Chaffer, J.: Solving YOUR Evolmino puzzle! Pathologic 6-3 (2025), https://www. youtube.com/watch?v=yV7GDJo_8zo

    work page 2025

  7. [7]

    Springer London (2005)

    Dekking, F., Kraaikamp, C., Lopuhaä, H., Meester, L.: A Modern Introduction to Probability and Statistics. Springer London (2005). https://doi.org/10.1007/ 1-84628-168-7

    work page 2005

  8. [8]

    IEICE Transactions on Fundamen- tals of Electronics, Communications and Computer SciencesE97.A(6), 1213–1219 (2014)

    Demaine, E.D., Okamoto, Y., Uehara, R., Uno, Y.: Computational complexity and an integer programming model of Shakashaka. IEICE Transactions on Fundamen- tals of Electronics, Communications and Computer SciencesE97.A(6), 1213–1219 (2014). https://doi.org/10.1587/transfun.E97.A.1213

    work page doi:10.1587/transfun.e97.a.1213 2014

  9. [9]

    In- formation Processing Letters97(5), 181–185 (2006)

    Efraimidis, P.S., Spirakis, P.G.: Weighted random sampling with a reservoir. In- formation Processing Letters97(5), 181–185 (2006). https://doi.org/10.1016/j.ipl. 2005.11.003

    work page doi:10.1016/j.ipl 2006

  10. [10]

    Working Paper OR-078-78, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA (1978)

    Gavish, B., Graves, S.C.: The travelling salesman problem and related problems. Working Paper OR-078-78, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA (1978)

    work page 1978

  11. [11]

    Technical report, Optimization Online (November 2025), https://optimization-online.org/2025/11/ the-scip-optimization-suite-10-0/

    Hojny, C., Besançon, M., Bestuzheva, K., Borst, S., Chmiela, A., Dionísio, J., Eifler, L., Ghannam, M., Gleixner, A., Göß, A., Hoen, A., van der Hulst, R., Kamp, D., Koch, T., Kofler, K., Lentz, J., Maher, S.J., Mexi, G., Mühmer, E., Pfetsch, M.E., Pokutta, S., Serrano, F., Shinano, Y., Turner, M., Vigerske, S., Walter, An Integer Linear Programming Model...

    work page 2025

  12. [12]

    Lulu Press, Inc

    Hurlimann, T.: Puzzles and Games, A Mathematical Modeling Approach. Lulu Press, Inc. (2025)

    work page 2025

  13. [13]

    Reducibility among combinatorial problems

    Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series. pp. 85–103. Springer US, Boston, MA (1972). https://doi.org/10.1007/978-1-4684-2001-2_9

    work page doi:10.1007/978-1-4684-2001-2_9 1972

  14. [14]

    Entertainment Computing36, 100386 (2021)

    Keçeci, B.: A mixed integer programming formulation for Smashed Sums puzzle: Generating and solving problem instances. Entertainment Computing36, 100386 (2021). https://doi.org/10.1016/j.entcom.2020.100386

    work page doi:10.1016/j.entcom.2020.100386 2021

  15. [15]

    Algorithms5(1), 158–175 (2012)

    Kino, F., Uno, Y.: An integer programming approach to solving Tantrix on fixed boards. Algorithms5(1), 158–175 (2012). https://doi.org/10.3390/a5010158

    work page doi:10.3390/a5010158 2012

  16. [16]

    Addison-Wesley Longman Publishing Co., Inc., USA (1997)

    Knuth, D.E.: The Art of Computer Programming, Volume 2 (3rd Ed.): Seminu- merical Algorithms. Addison-Wesley Longman Publishing Co., Inc., USA (1997). https://doi.org/10.5555/270146

    work page doi:10.5555/270146 1997

  17. [17]

    Knuth, D.E.: Dancing links (2000), https://arxiv.org/abs/cs/0011047

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  18. [18]

    EURO Journal on Computational Optimiza- tion10, 100031 (2022)

    Koch, T., Berthold, T., Pedersen, J., Vanaret, C.: Progress in mathematical pro- gramming solvers from 2001 to 2020. EURO Journal on Computational Optimiza- tion10, 100031 (2022). https://doi.org/10.1016/j.ejco.2022.100031

    work page doi:10.1016/j.ejco.2022.100031 2001

  19. [19]

    IBM Jour- nal of Research and Development47(1), 57–66 (2003)

    Lougee-Heimer, R.: The common optimization interface for operations research: Promoting open-source software in the operations research community. IBM Jour- nal of Research and Development47(1), 57–66 (2003). https://doi.org/10.1147/ rd.471.0057

    work page 2003

  20. [20]

    INFORMS Transactions on Education10(3), 156– 162 (2010)

    Meuffels, W.J.M., den Hertog, D.: Puzzle—solving the battleship puzzle as an integer programming problem. INFORMS Transactions on Education10(3), 156– 162 (2010). https://doi.org/10.1287/ited.1100.0047

    work page doi:10.1287/ited.1100.0047 2010

  21. [21]

    In: Lopes, L.S., Lau, N., Mariano, P., Rocha, L.M

    Mingote, L., Azevedo, F.: Colored nonograms: An integer linear programming approach. In: Lopes, L.S., Lau, N., Mariano, P., Rocha, L.M. (eds.) Progress in Artificial Intelligence. pp. 213–224. Springer Berlin Heidelberg (2009). https: //doi.org/10.1007/978-3-642-04686-5_18

    work page doi:10.1007/978-3-642-04686-5_18 2009

  22. [22]

    Siberian Electronic Mathematical Re- ports22(2), C54–C67 (2025)

    Nikolaev, A.V.: Evolomino is NP-complete. Siberian Electronic Mathematical Re- ports22(2), C54–C67 (2025). https://doi.org/10.33048/semi.2025.22.C05

    work page doi:10.33048/semi.2025.22.c05 2025

  23. [23]

    https://github

    Nikolaev, A.V., Myasnikov, Y.A.: Evolomino benchmark dataset. https://github. com/hsaruJ/evolomino-samples (2026)

    work page 2026

  24. [24]

    Nikoli Co., Ltd.: Evolomino (2025), https://www.nikoli.co.jp/en/puzzles/ evolomino/

    work page 2025

  25. [25]

    Perron, L., Didier, F.: CP-SAT, https://developers.google.com/optimization/cp/ cp_solver/

    work page

  26. [26]

    Perron, L., Furnon, V.: OR-Tools, https://developers.google.com/optimization/

    work page

  27. [27]

    Cryptologia33(4), 321–334 (2009)

    Ravi, S., Knight, K.: Attacking letter substitution ciphers with integer programming. Cryptologia33(4), 321–334 (2009). https://doi.org/10.1080/ 01611190903030920

    work page 2009

  28. [28]

    In: Proc

    Simonis, H.: Kakuro as a constraint problem. In: Proc. seventh Int. Works. on Constraint Modelling and Reformulation (2008)

    work page 2008

  29. [29]

    Erciyes Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi (71), 41–44 (2025)

    Sungur, B., Madenoğlu, F.S.: An integer programming formulation for generating and solving Survo puzzle. Erciyes Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi (71), 41–44 (2025). https://doi.org/10.18070/erciyesiibd.1666419

    work page doi:10.18070/erciyesiibd.1666419 2025

  30. [30]

    In: Logic for Programming, Artificial Intelligence, and Reasoning (LPAR)

    Weber, T.: A SAT-based Sudoku solver. In: Logic for Programming, Artificial Intelligence, and Reasoning (LPAR). pp. 11–15 (2005) 16 A.V. Nikolaev and Y.A. Myasnikov A Detailed computational results T able 1.ILP model complexity and CP-SAT solver runtime on the benchmark dataset [23] (50 instances per grid size) Grid size Problem size (Med.) Running time (...

    work page 2005