License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.1
URN: urn:nbn:de:0030-drops-159719
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15971/
Go to the corresponding LIPIcs Volume Portal

A. Akitaya, Hugo ; Löffler, Maarten ; Viglietta, Giovanni

Pushing Blocks by Sweeping Lines

pdf-format:
LIPIcs-FUN-2022-1.pdf (3 MB)

Abstract

We investigate the reconfiguration of n blocks, or "tokens", in the square grid using line pushes. A line push is performed from one of the four cardinal directions and pushes all tokens that are maximum in that direction to the opposite direction by one unit. Tokens that are in the way of other tokens are displaced in the same direction, as well.
Similar models of manipulating objects using uniform external forces match the mechanics of existing games and puzzles, such as Mega Maze, 2048 and Labyrinth, and have also been investigated in the context of self-assembly, programmable matter and robotic motion planning. The problem of obtaining a given shape from a starting configuration is know to be NP-complete.
We show that, for every n, there are sparse initial configurations of n tokens (i.e., where no two tokens are in the same row or column) that can be compacted into any a×b box such that ab = n. However, only 1×k, 2×k and 3×3 boxes are obtainable from any arbitrary sparse configuration with a matching number of tokens. We also study the problem of rearranging labeled tokens into a configuration of the same shape, but with permuted tokens. For every initial configuration of the tokens, we provide a complete characterization of what other configurations can be obtained by means of line pushes.

BibTeX - Entry

@InProceedings{a.akitaya_et_al:LIPIcs.FUN.2022.1,
  author =	{A. Akitaya, Hugo and L\"{o}ffler, Maarten and Viglietta, Giovanni},
  title =	{{Pushing Blocks by Sweeping Lines}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15971},
  URN =		{urn:nbn:de:0030-drops-159719},
  doi =		{10.4230/LIPIcs.FUN.2022.1},
  annote =	{Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation}
}

Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI