Solvability of a 9-card puzzle game with a similar concept as a rubik’s cube

card-gamespuzzlerubiks-cube

I challenged myself to create a card game that simulates the experience of solving a 3×3 Rubik's cube. I have a first prototype but I'm now stuck at knowing if every random initial state will be solvable.

I will first explain the challenge I'm facing and after that I will provide more context of the actual game, but if you want to check the cards and/or rules first, you can do it here.

In a 3×3 Rubik's cube not every state is solvable, we need to maintain the parity. Of course, if we mix the cube using only legal movements, we are always going to have a solvable state. This is where the first particularity of my game comes in:

  • My idea is to simplify the set-up of the game by shuffling the 9 cards together and place them in the table in a 3×3 grid.

Problem: When shuffling the cards I don't know if I'm performing any illegal movements that will generate an unsolvable state.

With that challenge in mind I will proceed to explain the game:

  • The game consists of 9 identical double-sided cards but each card having a different number [1-9].
    See this image of a single card showing both sides. The dots that appear in the card where the arrows are pointing are just for knowing which color is on the other sides without looking.
  • To set up the game the cards will be shuffled, flipped, and rotated so we have a random initial state. Then, they will be placed in a 3×3 grid on the table making sure each card covers the bottom half of the card in the previous row. See this example of a set up game (Notice we cover the bottom half of every card, except for the cards in the last row as we don't have more cards to cover them).
  • Now, the actions we can do for solving the game are:
    1. Shift rows: For shifting a row, we move the 3 cards of the selected row one step to the right or left. There will be one card that goes off the grid. That card is then flipped horizontally and placed at the opposite side of the grid, where there should be an empty cell. See the following example. Notice the horizontal flip in Step 3
    2. Shift columns: Shifting columns is similar to shifting rows. We move the complete column one step up or down. The difference is that the card that goes off the grid has to be flipped vertically See the following example. Notice the vertical flip in Step 3

The rule of thumb is the card that goes off the grid will be flipped in the direction of the shift and placed at the opposite side of the grid

  • Goal: The puzzle will be completed when all the 9 cards are in numerically ascending order (from left to right and top to bottom), and with the green faces at the top. See example of a solved puzzle

I hope I explained that well, let me know if you want me to clarify something 😀

You can download the Print and Play files of the cards and the rules with more detailed explanation here.

Questions:

  • Will shuffling the cards always generate a solvable state?
  • Do you think there might be a golden path to easily solve the puzzle every time?
  • How many possible combinations the puzzle has? My guess is that it has 95,126,814,720 possible states (counting the solved state). It will be awesome if all of them are solvable 😀
  • Would the same scenario apply to a 2×2 puzzle and a 4×4 puzzle?

Best Answer

It is possible to flip a single card in one direction without affecting any other cards, like this:

A B C   B C a   D C a   C a d   B a d   a d b   C d b   D B C   a B C
D E F   D E F   G E F   G E F   C E F   C E F   G E F   G E F   D E F
G H I   G H I   b H I   b H I   G H I   G H I   A H I   A H I   G H I

      L       U       L       D       L       U       RR      D

Here only moves of the top row and left column are used to flip the card in the top left corner horizontally.

By applying the same moves to different rows/columns you can flip any card, and by applying the moves 90 degrees rotated you can flip any card along the other axis.

This means that for any permutation of the cards, all $4^9$ orientations of those cards is possible.

However, not all $9!$ permutations are possible. Every move is a 3-cycle, which is a permutation with even parity. Combining even permutations only results in even permutations, so no odd permutations can be achieved. It is fairly easy to show that any even permutation is solvable using the 3-cycles you have available (for example by using the well-known theorem that the 3-cycles of the form $(1,2,k)$ generate all even permutations).

The total number of achievable states is therefore $4^9\cdot\frac{9!}2 = 47,563,407,360$, and a randomly chosen shuffled deck of cards has a $50\%$ probability of being solvable.

You can fix this problem by making two cards identical, for example by making cards 8 and 9 blank apart from their colours. By doing that, every shuffled deck becomes solvable because it becomes possible to swap any two numbers. This is because a swap of two numbered cards can be combined with a swap of the two identical blank cards, and such a double-swap is an even permutation and therefore achievable using the moves of the game. Note that the number of permutations is still $9!/2$, so having two unnumbered cards does not reduce the number of solvable positions of the game.

Edit:

For even grid sizes you should still use two blank cards, but it is for a slightly more complicated reason.

If you only look at the permutations of the numbers when both dimensions of the grid are even, then then every permutation can be reached/solved. So you'd think that no blank cards are needed in that case. However, something interesting happens with the orientations when the dimensions are even. Every move changes the parity of the permutation, but also does exactly one card flip. So the total number of card flips will be even or odd, and that must match the parity of the permutation. Both parities are affected by every move, they are equal (both even) in the solved state, so they will remain equal to each other throughout the game and must be equal for the position to be solvable.

Having two cards without numbers will still ensure that every shuffled deck will lead to a solvable position, without reducing the number of positions that can be played.

Something similar happens if only one of the dimensions is odd, but then it is not the total number of flips but the number of flips in the even direction that has to match parity with the permutation. Flips along the odd direction can be done in essentially the same way as in the 3x3 without changing the permutation. So again, using two unnumbered cards will allow the use of a shuffled deck.

In this last case with an even by odd sized grid, then there is a different way to fix the shuffled deck problem. Instead of two unnumbered cards, you could instead have one anomalous card which does not change when flipped over in the even direction. Normally it would be impossible to flip just a single card in the even direction without affecting the numbers (it would have to be an odd permutation of the numbers to match the odd card flip, so some numbers would have to be moved). It is possible however to combine the flip of that single card with a flip of the anomalous card. Flipping both cards can be done without affecting the number permutation, and since the flip of the anomalous card is not visible it is just as if a single card was flipped. Therefore the presence of this anomalous card makes every shuffled state solvable.

Related Question