Pushing Blocks by Sweeping Lines

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. Tokens that are in the way of other tokens are displaced in the same direction, as well. Since we consider configurations equivalent under translation, this model is equivalent to having a line barrier touching one of the sides of the bounding box of the configuration and trying to move all tokens toward the barrier by one unit. 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 ) box such that $ab=n$. However, only ($1 ), ($2 ) and ($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.