2014/08/15 by Jens Maßberg, Maßberg, Jens
Computer Science · Mathematics · #Artificial Intelligence in Games #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.CO
paper · pdf · doi:10.48550/arxiv.1408.3645
6 pages
openalex publication_date 2014/08/15 · arxiv created 2014/08/20 · arxiv updated 2014/08/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the "Game about Squares" the task is to push unit squares on an integer lattice onto corresponding dots. A square can only be moved into one given direction. When a square is pushed onto a lattice point with an arrow the direction of the square adopts the direction of the arrow. Moreover, squares can push other squares. In this paper we study the decision problem, whether all squares can be moved onto their corresponding dots by a finite number of pushes. We prove that this problem is NP-hard.