jcdcggg – A.S.A.R.G.

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.

Tile Pattern-Building Games on a Grid are PSPACE-complete (Short Abstract).

Angel A. Cantu, Arturo Gonzalez, Cesar Lozano, Austin Luchsinger, Eduardo Medina, Fernando Martinez, Arnoldo Ramirez, and Tim Wylie.
The 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3’18), 2018.

Abstract: In this paper, we investigate a certain class of tile-based pattern games through a simplified version of a recent game titled Nonads. We prove that Nonads is PSPACE-complete with a reduction from bounded 2-player constraint logic (Bounded 2CL) even when both players share the same target and there is only one type of playable tile. This has application to any grid-based pattern building game.

Bibtex: