论文标题
通过扫线推动块
Pushing Blocks by Sweeping Lines
论文作者
论文摘要
我们使用“ Line Puspers”在方格网格中调查了$ n $块或“代币”的重新配置。从四个基本方向之一执行线路，并将所有方向最大的令牌推到相反方向。以其他代币方式的令牌也朝着相同的方向移位。 使用统一外力来操纵物体的类似模型与现有游戏和难题的机制相匹配，例如Mega Maze，2048和迷宫，并且在自组装，可编程的物质和机器人运动计划的背景下也进行了研究。从启动配置中获得给定形状的问题被称为NP完整。 我们表明，对于每$ n $，都会有$ n $令牌的“稀疏”初始配置（即，没有两个令牌在同一行或列中）可以重新排列到任何$ a \ times b $ box中，因此$ ab = n $。但是，仅$ 1 \ times k $，$ 2 \ times k $和$ 3 \ times 3 $ box可以从任何任意稀疏配置中获得，并具有匹配数量的令牌。我们还研究了将标记令牌重新排列为相同形状的配置的问题，但具有置换令牌。对于代币的每个初始“紧凑”配置，我们提供了可以通过线推可以获得其他配置的完整表征。
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. 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 rearranged into any $a\times b$ box such that $ab=n$. However, only $1\times k$, $2\times k$ and $3\times 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 "compact" configuration of the tokens, we provide a complete characterization of what other configurations can be obtained by means of line pushes.
