Аннотация:

Evolomino is a pencil-and-paper logic puzzle popularized by a 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 the puzzle that satisfies Evolomino's 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 $\texttt{#}$P-complete.