Grid puzzle solutions

Question

I have a simple grid puzzle: Example:

| X | Y | X |   
| Y | X | Y |  
| Y | X | Y |

The move is defined as a row or a column move. So when you move one cell, whole column/row moves. Example top row right 2 steps:

1 step
| X | X | Y |   
| Y | X | Y |  
| Y | X | Y |
2 step
| Y | X | X |

| Y | X | Y |

| Y | X | Y |

Now column move will look like this on the last row move up

1 step
| Y | X | Y |   
| Y | X | Y |  
| Y | X | X |

and so MoveRight - the most right cell will become the most left cell etc...

I am wondering if it is possible to go to every possible grid combination only with this moves. Let's assume that the grid will be 3x3 but it can be any size.

So, for example, I create random grid 3x3 with the same X count and Y count like this:

| Y | Y | Y |   
| Y | Y | X |  
| X | X | X |

Is it possible to check if there is a solution on how to make this grid the first grid with already specified moves? Or how to approach this problem?

Are we guaranteed that it will be a 3x3 grid and only two values (X and Y)? With such a small grid, you can just brute force the solution by generating every possible configuration — Parseltongue, Jul 23 '19 at 20:24
@Parseltongue No, this is just an example. It can even have every cell other char and the size can be bigger. I am currently building a playable solution to try that, but I want to know more non-brute force method. — Jakub Gabčo, Jul 23 '19 at 20:33
Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html — Ted, Jul 23 '19 at 20:38
I'm not sure of any solution that doesn't just use transposition tables — Parseltongue, Jul 23 '19 at 20:58

score 8 · Accepted Answer · answered Jul 23 '19 at 21:16

8

In the general case (all symbols allowed), you cannot reach every position. The argument is a parity argument, similar to how half of the configurations of a Rubik's Cube cannot be achieved.

Every legal move in your game is equivalent to an even number of "swaps". Say you start with

ABC
DEF
GHI

and move the top row right:

CAB
DEF
GHI

This is equivalent to swapping BC, and then swapping the resulting AC:

ACB
DEF
GHI

CAB
DEF
GHI

Every move you can make is similarly equivalent to two swaps. This means that every position you can possibly ever arrive at is the equivalent of an even number of swaps.

The result of this is that you cannot ever arrive at a configuration that requires an odd number of swaps, like this one:

BAC
DEF
GHI

answered Jul 23 '19 at 21:16

user61579

116
1

This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much. – Jakub Gabčo Jul 23 '19 at 21:19
1

For 4x4 this does not apply if I am right .. There are 3 swaps in 4x4 so only solutions are that has swipes count % 3 == 0. For 5x5 there are 4 swaps and so on.. – Jakub Gabčo Jul 23 '19 at 21:22
Yes - a move in 4x4 is equivalent to 3 swaps, meaning that you can arrive at both even and odd configurations. My response is for odd-sized square grids - I don't have a proof either way about even-sized square grids or rectangular grids with an even and an odd dimension.
Ah, yes - I see your edit and that is the proof. Whatever the sizes, there will be configurations that aren't equal to 0 mod k for some relevant k.
– user61579 Jul 23 '19 at 21:26
I'm confused as to how this constrains the search space, though? You still have to actually figure out if it's possible to get from position A to B in an even number of swaps (for 3x3), which still requires brute-forcing. The fact that you CAN get to a position in an odd number of swaps doesn't mean anything unless all your values are distinct.
For example if you have
```
    [BCA]
    [GHI]```
You can get `["BAC"]` in the top row in an even number of swaps, even though you can also get to it in an odd number of swaps.
```
– Parseltongue Jul 23 '19 at 21:40
This is also a variant of the sliding tile puzzle which has the same property - half the state space is unreachable. (See the proof description here: https://en.wikipedia.org/wiki/15_puzzle) – Nathan S. Jul 24 '19 at 05:08
@Parseltongue It doesn't constrain the search space - it proves that not all positions are solvable, which was one of OP's original questions.
Yes, there may be some solvable positions if symbols are repeated, but I was referring to the general case.

As for brute-forcing, it is probably not necessary. For each adjacent pair of symbols, you can come up with a "move" that swaps those two elements with predictable side effects (like swapping a fixed pair of "key" elements). By combining such moves, and moves that solve the key elements, you can get to any reachable configuration.
– user61579 Jul 24 '19 at 19:37
On this game chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html it happens to me that 15 and 16 were flipped and other positions were correct. I came to the conclusion that every solution should be solvable if I am able to swap the closest pair. – Jakub Gabčo Jul 25 '19 at 09:21

Grid puzzle solutions

1 Answers1