4 citations · 9 across the 6 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2021★ 4 cited
Yin-Yang Puzzles are NP-complete
Erik D. Demaine, Jayson Lynch, Mikhail Rudoy +1
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-paper puzzles. Viewed as a graph partitioning problem, we prove NP-completeness of partitioning a rectangular g…
cs.CC2016
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
cs.CC2015★ 3 cited
Threes!, Fives, 1024!, and 2048 are Hard
Stefan Langerman, Yushi Uno
We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m x n board, we show t…