Strategy and Complexity of The Game of Squares
Florian Breuer, John Michael Robson · Bulletin of the London Mathematical Society · 1998
We introduce a game called Squares where the single player is presented with a pattern of black and white squares and has to reduce the pattern to white by making as few moves as possible. We present a method for solving the game, and show that the following problem is NP-complete. Problem 1 (Squares-Solvability). Given a pattern X and k∈N, can X be solved in k or less moves? We demonstrate a reduction to this problem from Not-All-Equal-3SAT. We also present another NP-complete problem that Squares-Solvability can be reduced to. 1991 Mathematics Subject Classification 68Q25.