.png){kind=icon}
Return
A linear-time algorithm for the two-color one-dimensional buttons & scissors
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ipl.2026.106622.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The problem of determining whether a given board of the puzzle Buttons & Scissors is solvable is known to be NP-complete. On the other hand, when the board is restricted to one dimension, it is known to be solvable in O(n(3))-time for a board of size (length) n. This also holds when the button colors are limited to two colors. We provide a simple linear-time algorithm to determine whether an input of the Two-Color One-Dimensional Buttons & Scissors problem is solvable. The algorithm uses a necessary and sufficient condition after applying a linear-time preprocessing.
Keywords:
Buttons & scissors
Puzzle
Linear-time algorithm
Necessary and sufficient condition
Run-length encoding
Journal
I
IF:
0.6
Papers:
17
Citations:
3.4K
Organization
.png){kind=icon}
