5
$\begingroup$

This is a type of puzzle that at first looks like a tile-sliding puzzle, where you have a grid of tiles with 1 missing tile, and you can slide individual tiles into the blank spot, eventually arranging them in the right order.

But it's quite different -- there is no blank spot, and you slide an entire row or column of tiles at a time, where the title that overflows wraps around to the other side. It seems to have more in common with a Rubik's Cube than a sliding puzzle.

Here's an example: https://www.proprofs.com/games/row-slide-puzzle/

There is also an Apple Arcade game The Enchanted World (trailer) with these types of puzzles -- only they aren't in perfect square shapes, each row can have a different number of tiles, and there is sometimes move count limitations, or a mobile bad guy that makes titles unmovable. What makes its puzzles more challenging is that half the puzzle is figuring out what the correct arrangement even is -- as if getting into that arrangement wasn't a challenge enough :)

I can't seem to find any information about solutions to these types of puzzles. All the information I find is about tile sliding puzzles, and Rubik's Cube type puzzles are more complex. This is like a 2D rubik's cube.

Is there a name for this type of puzzle? What movement techniques are useful for solving them?

For example, one technique I've identified lets you fix the order of titles in a particular row. Say the row is '1324' and you need it to be '1234'. This is really 2 separate steps -- the 2 and 3 are each in the wrong position, and you can fix each one separately. For the 2, slide its column up or down, separating it from the row. Then slide the row such that the position the 2 should be in is adjacent to the 2, then slide 2's column the opposite way as you originally did, and now 2 is in the correct position (and if necessary you may now slide the row back to how it originally was relative to the rest of the puzzle). Repeat for 3. The issue with this technique is that it does not leave the rest of the board as it was. You invariably end up trading one misplaced tile for another, just moving the problem around. Insights or academic links to similar puzzles would be helpful!

$\endgroup$
  • 1
    $\begingroup$ Your puzzle has a toroidal mapping. Methods here: researchgate.net/publication/… $\endgroup$ – amI Feb 2 at 22:13
  • $\begingroup$ Ah, I remembered playing a puzzle-game like this 10 years ago, Chuzzle, and getting frustrated.. :) $\endgroup$ – athin Feb 2 at 22:56
  • 1
    $\begingroup$ If you want to be able to solve permutation puzzles in general, you should learn about commutators and conjugates. See this post about the Rubik's cube and other permutation puzzles. Jaap's 3-cycles are instances of commutators, and the final single-swap is an example of parity issue in the general case. $\endgroup$ – user21820 Feb 3 at 3:36
6
$\begingroup$

This puzzle is also in Simon Tatham's Portable Puzzle Collection, where it is called Sixteen.

There are several physical puzzles that are somewhat similar in that you can shift a row or column, but they don't wrap around. For example Crossover, which was made by Nintendo in the early 1980s. It has a 4x4 playing field of tiles, but each row and each column has an extra tile so that the row/column can be shifted one step back and forth. The technique for solving it can also be used on the Sixteen puzzle. Take a look at this diagram:

enter image description here

If you shift a row to the left, a column downwards, shift the row back to the right, and finally the column back upwards, the net effect is that three tiles have been cycled around. The diagram shows which tiles are affected.

On the Sixteen puzzle the rows/columns can shift a larger distance, so you can have other 3-cycles too. Pick any 3 tiles that form a right-angled triangle, i.e. a tile which shares a row with the second tile and shares a column with the third tile. Shift that row (bringing the second tile to the intersection) and column (bringing the third tile to the intersection), and then return the row and the column, and you will have cycled the three tiles around.

Once you are comfortable with these 3-cycles, it is fairly easy to solve the puzzle almost completely. You might however be left with just two tiles that you need to swap. It is mathematically impossible to swap just two tiles using just these 3-cycles - a swap is a permutation with odd parity whereas 3-cycles can only create even permutations. However, if the rows (or columns) of your puzzle have an even number of tiles, then it is possible to swap two tiles in isolation, because shifting such a row (or column) one step is itself an odd permutation. So if you shift the row (or column) one step, the resulting position can be solved with those 3-cycles alone.

There is a quicker technique that works on this puzzle (but not on the Crossover) for solving the last row. You use only one column, and it alternates moving one step up and down, and you combine this with shifts of the last row. Each column move takes out one tile from the row, replacing it with another. It is best illustrated by example. Only the tiles involved in the technique are shown:

 1 3 2 4
       x

We need to do a single swap. As mentioned with the 3-cycle technique, this is an odd permutation, and the row needs to be shifted one step so that we get an even permutation. It does not matter which direction.

 3 2 4 1
       x

Now tile 2 is correct, and the other pieces are incorrect. We will solve those other three tiles relative to tile 2. First take out the tile we have at hand, tile 1. Tile x temporarily takes its place:

       1
 3 2 4 x

Tile 1 needs to go to the left of tile 2, where tile 3 is now. So shift the row so as to bring that position to our column:

       1
 2 4 x 3

Put tile 1 in place, removing tile 3:

 2 4 x 1
       3

Now tiles 1 and 2 are correct relative to each other. Tile 3 needs to go to the right of tile 2, where tile 4 is now. So bring that location into our column:

 x 1 2 4
       3

Put tile 3 in place, removing tile 4:

       4
 x 1 2 3

Tile 4 needs to go in the place where tile x is, so move the x into the column:

       4
 1 2 3 x

And finally put 4 in place:

 1 2 3 4
       x

Because we made sure we had an even permutation to start with, the column returns to its starting position. If we had an odd permutation the column would have ended up shifted, or else we'd have tiles 4 and x swapped.

The above technique essentially consists of running together several 3-cycles involving a shared row and column, but so many moves cancel out that it is easier to think of it as swapping out tiles from the row.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wow this is exactly the kind of info I was hoping for. I need to digest it, but thank you! $\endgroup$ – InfinitiesLoop Feb 3 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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