Hardness results for Buttons \& Scissors

Aaron Williams
Bard College at Simon's Rock

PDF

Minisymposium: GENERAL SESSION TALKS

Content: \emph{Buttons \& Scissors} is a free single-player puzzle available on iOS and Android. The puzzle is played on an $n$-by-$n$ grid, where each position is empty or has a coloured button sewn onto it. The player's goal is to remove all of the buttons using a sequence of horizontal, vertical, and diagonal scissor cuts. Each cut removes all buttons between two distinct buttons of the same colour, and is not valid if there is an intermediate button of a different colour. We prove that deciding whether a given level can be completed is NP-complete. In fact, NP-completeness still holds when only two different button colours are used, and only horizontal and vertical cuts are allowed. On the other hand, the problem is polytime solvable for a single button colour via matching in hypergraphs with edges containing two or three vertices. We also discuss inapproximability and integer programming solutions to the general problem. This is joint work with three students from Bard College at Simon's Rock, and over a dozen researchers from the 30th Bellairs Winter Workshop on Computational Geometry

Back to all abstracts