8
$\begingroup$

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?

Thanks, everyone.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Parseltongue Jul 23 at 20:24
  • $\begingroup$ @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. $\endgroup$ – Jakub Gabčo Jul 23 at 20:33
  • $\begingroup$ Here's a 4x4 one from Simon Tatham's Portable Puzzle Collection, but you can change the size from the drop down. chiark.greenend.org.uk/~sgtatham/puzzles/js/sixteen.html $\endgroup$ – Ted Jul 23 at 20:38
  • $\begingroup$ I'm not sure of any solution that doesn't just use transposition tables $\endgroup$ – Parseltongue Jul 23 at 20:58
  • $\begingroup$ @Ted That is exactly the puzzle I mean. Thanks $\endgroup$ – Jakub Gabčo Jul 23 at 21:10
8
$\begingroup$

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
$\endgroup$
  • $\begingroup$ This answer is gold. Didn't realize that is like Rubick's cube. Thank you very much. $\endgroup$ – Jakub Gabčo Jul 23 at 21:19
  • 1
    $\begingroup$ 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.. $\endgroup$ – Jakub Gabčo Jul 23 at 21:22
  • $\begingroup$ 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. $\endgroup$ – user61579 Jul 23 at 21:26
  • $\begingroup$ 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 [ACB] [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. $\endgroup$ – Parseltongue Jul 23 at 21:40
  • $\begingroup$ 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: en.wikipedia.org/wiki/15_puzzle) $\endgroup$ – Nathan S. Jul 24 at 5:08

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.