3
$\begingroup$

The game of roller blocks is played on a rectangular board of size $m\times n$. For example, if $m=5$ and $n=4$ we have $5 \times 4=20$ different gridpoints/coordinates. Just so the conventions are clear, the lower-left corner can be written as $(1,1)$ and the upper-right corner can be written as $(5,4)$.

On the board there are two or more blocks that have been placed. Let's assume, for the sake of concreteness, that we have two blocks. Both of the blocks are specifically numbered as $1$ and $2$.

Some gridpoints on the rectangular board are "walls" while others aren't. To make the description of the game a little easier, I will assume that the whole perimeter of the grid is always covered by walls (there may or may not be walls in other positions too). For example, in the case of $5\times 4$ board above, there are $14$ perimeter positions. We assume that all the perimeter positions are covered with walls.

Just so that there is no ambiguity, in the above case the perimeter positions will be: $(1,1),(2,1),(3,1),(4,1),(5,1),(1,4),(2,4),(3,4),(4,4),(5,4),(1,2),(1,3),(5,2),(5,3)$

Now two goal points are also placed on the board (fixed in advance). The goal points are obviously placed on positions other than the walls. One of the goal points is marked as $1$ and the other is marked as $2$ (in correspondence with blocks $1$ and $2$). Initially the game starts with the blocks $1$ and $2$ at a position other than the walls. The goal of the game is to give a sequence of commands such that both the blocks are on goalpoints simulteneously (block-$1$ on first goal point and similarly block-2 on the second goal point).

At each point in the game the following four commands can be given: right, left, up, down. Each of the commands has a similar effect in the sense that if we understand the effect of the right command then the effect of other three commands can be easily extrapolated.

Assume the first block is at a position $(x_1,y_1)$ and the second one is at a position $(x_2,y_2)$. In the first three cases we additionally assume that first block is not to the right of second block (or vice versa). That is: $$y_1 =y_2 \,\;\, and \,\;\, x_1= x_2+1$$ is false (and similarly the condition for second block being just to the right to the first one is also false). Here is the precise description for the "right command" :

(1) The normal condition

There are no walls at the positions $(x_1+1,y_1)$ and $(x_2+1,y_2)$. In this case the effect of right command would be to move first and second blocks to the positions $(x_1+1,y_1)$ and $(x_2+1,y_2)$ respectively.

(2) There is a wall for one of the blocks

There is a wall at the position $(x_1+1,y_1)$ but not at the position $(x_2+1,y_2)$. The position of first block remains unchanged after the right command --- it stays $(x_1,y_1)$. The second block moves to the position $(x_2+1,y_2)$.

(3) There is a wall for both of the blocks

There are wall at both the position $(x_1+1,y_1)$ and at the position $(x_2+1,y_2)$.

Position of both blocks remains unchanged.The first block stays at $(x_1,y_1)$ and the second one stays at $(x_2,y_2)$

Now we consider the case when the first block is just to the right of second block. That is: $$y_1=y_2 \,\;\, and \,\;\, x_1= x_2+1$$ is true.

(4) There is a wall just to the right of first block

Position of both blocks remains unchanged.The first block stays at $(x_1,y_1)$ and the second one stays at $(x_2,y_2)$

(5) There is no wall just to the right of first block

The position of first block changes to $(x_1+1,y_1)$ and the position of second block remains unchanged --- it stays at $(x_2,y_2)$.

Finally we can observe that the behaviour for cases (4) and (5) will be exactly as expected if block-$2$ was just to the right of block-$1$. One might just ask that what if we had three blocks with block-$2$ just to the right of block-$1$ and block-$3$ to the right of block-$2$. In that case, if we assume that there is no wall just to the right of block-$3$, then it will move one step to the right (while positions of block-$1$ and block-$2$ remain unchanged).

My question is whether there are some known analysis of this game? I have tried searching quite a bit to find the "standard name" of this puzzle game, but I simply can't find it ("maybe" I am just searching the wrong keyword). For example picross/logic pro as nonograms, block-pushing games as sokoban etc. This specific game was included as a "logic game" in commercial videogame "Smart As". The highest difficulty includes an extra twist which changes it somewhat from the above description --- all lower level difficulties are equivalent (or at least very similar) to above description. Here is link to an image where the blocks are moving to the left: http://www.climaxstudios.com/wp-content/uploads/2016/12/rollerblocks.jpg

$\endgroup$
1
  • $\begingroup$ I should add probably that the conditions(4) and (5) can be removed/simplified if one is interested in making the rule-set very small. To be honest, I don't know whether this would make a substantial difference or not (apparently it feels like that perhaps it wouldn't). I gave the description which fits closely with the puzzle game I played (by adding conditions-4,5). $\endgroup$
    – SSequence
    Oct 27, 2017 at 9:30

2 Answers 2

2
$\begingroup$

I believe your game is a variant of what is called The Warehouseman's Problem. This problem has been studied since the 1980's. A recent analysis appears in this book, p.120:

Robert Hearn and Erik Demaine, Games, Puzzles, and Computation, A K Peters, July 2009, (authorlink.)

If I read it correctly (not certain because there are many variations), your version ("unit translations") is PSPACE-Complete.

Here is an earlier literature reference, which you could use to search forward and backward with GoogleScholar:

Sharma, Rajeev, and Yiannis Aloimonos. "Coordinated motion planning: The warehouseman's problem with constraints on free space." IEEE Transactions Systems, Man, Cybernetics, 22.1 (1992): 130-141.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for the references. I wouldn't have been able to find this myself. Just as a brief description, the variation which I have described, the obstacles/walls are not moveable. Furthermore, there are more two or more blocks/robots which move "simultaneously" (unless one of them gets blocked by an obstacle in which case the one which isn't blocked still moves). The "simultaneous movement" or two or more blocks/robots is the main part of the mechanic in this puzzle. $\endgroup$
    – SSequence
    Oct 25, 2017 at 13:00
  • 1
    $\begingroup$ @SSequence: Yes, simultaneous movement might distinguish it from the standard Warehousemen's problem, but quite likely it is still PSPACE-hard, by a similar analysis. $\endgroup$ Oct 25, 2017 at 13:04
1
$\begingroup$

If the number of blocks $k$ is fixed then the puzzle is polynomial-time solvable.

For example if $k = 2$, and assuming that the grid size is $n \times n$, then there are at most $n^2 \times n^2$ configurations (possible combinations of positions of block 1 and 2).

Then you can simply build a reachability directed graph $G$ in which every node is a configuration and there is a directed edge between two configurations $C_i, C_j$ if and only if there is a $Left, Right, Up, Down$ move from $C_i$ to $C_j$.

Then you can simply apply a shortest path algorithm on $G$, between the starting configuration $C_{start}$ and the target configuration $C_{target}$.

If the number of initial blocks is arbitrary, then I suspect that the problem falls in the "limbo" of [probably not | hard to prove] PSPACE-complete problems like Lunar Lockout without fixed blocks

$\endgroup$
3
  • $\begingroup$ Interesting. I think what might be interesting (for example, for the case of two or fixed no. of blocks) and possibly difficult could be showing what is the best way/algorithm to play in general? Regardless my question wasn't just about time complexity, but somewhat open-ended. For example, with two blocks at some given initial positions and given some wall positions, can one prove or disprove (somewhat efficiently) that all combination of non-wall positions can be reached or not? $\endgroup$
    – SSequence
    Oct 27, 2017 at 9:25
  • $\begingroup$ @SSequence: "... with two blocks at some given initial positions and given some wall positions ..."; yes you can prove it "efficiently" (polynomial-time algorithm) using the same "reachability graph" approach. And the same technique can be used efficiently to find the "best" playing strategy (i.e. the shortest path matches the minimum number of moves to solve the puzzle). IMO, from a computational complexity viewpoint the interesting thing would be to dig into the arbitrary number of blocks case. $\endgroup$ Oct 27, 2017 at 9:59
  • $\begingroup$ Well you are right ..... but this is kind of what I had in mind (sorry I don't know much computational complexity). Polynomial-time is good but it is still a very broad classification. For example, if one could solve (two blocks case) in time propotional to $n^3$ (or even better) instead of $n^4$ it would be more preferable. Of course if that kind of efficiency is possible in the first place. $\endgroup$
    – SSequence
    Oct 27, 2017 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.