Title: Relocation with Uniform External Control in Limited Directions (Short Abstract)
Authors: Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.
Conference: The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3’19), 2019.
Abstract: We study a model where particles exist within a board and move single units based on uniform external forces. We investigate the complexity of deciding whether a single particle can be relocated to another position in the board, and whether a board configuration can be transformed into another configuration. We prove that the problems are NP-Complete with $1 \times 1$ particles even when only allowed to move in 2 or 3 directions.