2025/02/05 by Andrei V. Nikolaev, Nikolaev, Andrei V.
Computer Science · Engineering · #03D15 #68Q25 #Artificial Intelligence in Games #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2503.07611
openalex publication_date 2025/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02
Evolomino is a pencil-and-paper logic puzzle popularized by the Japanese publisher Nikoli (like Sudoku, Kakuro, Slitherlink, Masyu, and Fillomino). The puzzle's name reflects its core mechanic: the shapes of polyomino-like blocks that players must draw gradually "evolve" in the directions indicated by pre-drawn arrows. We prove, by reduction from 3-SAT, that the question of whether there exists at least one solution to an Evolomino puzzle satisfying the rules is NP-complete. Since our reduction is parsimonious, i.e., it preserves the number of distinct solutions, we also prove that counting the number of solutions to an Evolomino puzzle is #P-complete.