4
$\begingroup$

I stumbled across this game in Simon Tatham's puzzle app. It's called cube. The description according to the game is:

You have a grid of 16 squares, six of which are blue; on one square rests a cube. Your move is to use the arrow keys to roll the cube through 90 degrees so that it moves to an adjacent square. If you roll the cube on to a blue square, the blue square is picked up on one face of the cube; if you roll a blue face of the cube on to a non-blue square, the blueness is put down again. (In general, whenever you roll the cube, the two faces that come into contact swap colours.) Your job is to get all six blue squares on to the six faces of the cube at the same time.

Attached is a link to a screenshot of the game here.

I would like to ask the CS community if there is a known algorithm for solving such a problem as I haven't found anything online.

Improve this question
$\endgroup$
6
  • $\begingroup$ link to image: ibb.co/cFyQK4v $\endgroup$ Commented Dec 25, 2022 at 7:35
  • 2
    $\begingroup$ (Please Edit instead of comments to add information to posts.) $\endgroup$ Commented Dec 25, 2022 at 15:03
  • 2
    $\begingroup$ There are at most $16 \cdot {16 + 6 \choose 6}$ possible states: $16$ possible positions of the cube and $6$ colors can be either on the board ($16$ positions) or the cube ($6$ positions). After that, use the standard idea: treat this game as a graph, and use BFS to reach the position where all $6$ colors are on the cube. $\endgroup$ Commented Dec 27, 2022 at 1:25
  • 1
    $\begingroup$ Also posted on math stackexchange. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without wasting anybody's time. If you don't get a satisfying answer after a week or so, you may flag to request migration. $\endgroup$ Commented Dec 29, 2022 at 21:45
  • $\begingroup$ @JohnL. Apologies. I was under the impression that each community would have a different approach. I'll keep that in mind for future questions. Thank you. $\endgroup$ Commented Dec 30, 2022 at 1:07

2 Answers 2

Reset to default
12
$\begingroup$

As Dmitry noticed there is very little possible states of the game, so it's relevant to search for solution using BFS traversal. But let's start from some numbers.

Staring positions

In terms of possible staring states we have $$ 16 \cdot {16 \choose 6} = 128128 $$ Coloring of $4\times4$ gird using $6$ colors gives ${16 \choose 6}$ cases, and $16$ for initial position of cube, but you can easily reduce this number by a factor of $16$, because you always can place cuboid on any (white) cell of the gird not changing its coloring pattern (after each move doing its reverse and doing this move again).

notice: we can use such trick only finding any solution, not optimal one.

Secondly we aren't interested in starting positions that are symmetric. So let's eliminate them, and enumerate positions (Burnside lemma will be helpful). The final count equals

$$1051 \; \text{positions}$$

Concluding, we can use this fact and precompute solutions for all possible starting game states and it won't hurt our memory.

Algorithm

Let's construct directed graph of this game. Each node will be representing some state of the game (including current coloring of grid, position of cube and colors on the cube itself). Each directed edge from one state to another will represent possibility of moving between this states (each state has at most $4$ neighbors, so graph isn't dense).

Then using BFS on so build graph, we can calculate (for example) distance to each state from initial one. That's even better, because now we can find optimal solution! And this is description of above approach:

  1. Create queue containing starting state
  2. Repeat while solved state aren't found
  3. Take first state from queue and mark as visited
  4. For each achievable next state, push it on queue (if next state is unvisited already)
Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Beautiful solution! Thank you!! Could you please explain how you used the Burnside lemma to calculate the final count? $\endgroup$ Commented Dec 28, 2022 at 23:32
6
$\begingroup$

Of course, but let me show the process on simpler example and then just use same method for calculating final count.

Small example

We are given $2 \times 2$ square grid and two colors (black and white). We are trying to find out number of different coloring of this grid. Obviously, there are $2^4 = 16$ possible patterns, but we don't want to count symmetrical ones twice. To visualize problem, look at below table:

table

I've printed all $16$ cases, but I also grouped them by symmetry (there are $6$ different patterns). The key is to deeply analyze those symmetries. There are $8$ isometries of a square:

  1. Identity (or $0^\circ$ rotation)
  2. Rotations: $90^\circ$, $180^\circ$, $270^\circ$ rotations
  3. Reflections: x-axis, y-axis reflections and both diagonal reflections

From now, we'll call this set a group, also denoted as $D_4$ (more info about this particular group here)

Useful definitions

For some coloring $a$, let orbit of $a$ be the set of coloring patterns that are achievable from $a$ by applying on it any symmetry of a square (denoted as $\texttt{orb}(a)$). Example:

orbit

note: On the first table we grouped patterns into orbits.

For any isometry $g$, the set of its fixed points will be all colorings of a such that $g(a) = a$ - we will denote this set as $\texttt{fix}(g)$. Example (here $g$ is vertical reflection): fixed points

Our problem has been reduced to counting orbits. So let's jump right into Burnside lemma:

$$ | \Omega | = \frac{1}{|G|} \cdot \sum_{g \in G} | \texttt{fix}(g) | $$

Here $\Omega$ is set consisting all orbits, so finding $|\Omega|$ is our goal. Our group of symmetries is here denoted as $G$.

That's great because we don't care about set of possible colorings (which can have too many elements). The only difficulty left is calculation for each isometry how many fixed points it has. To do this, we have to look which of the corners of the square the given isometry transforms on which ones. This way we will break them down into cycles and each one will have to be the same color. If an isometry has $k$ cycles, then it has $2^k$ fixed points, because we color each of them with one color.

For simplicity, let's enumerate corners of the square from $1$ to $4$. The table below shows what cycles will arise for all isometries. I encourage to do a thorough analysis.

isometry table

And just plug this result into Burnside lemma:

$$ | \Omega | = \frac{2^4 + 2 \cdot 2^3 + 3 \cdot 2^2 + 2 \cdot 2 }{8} = \frac{48}{8} = 6 $$

Just as we expected.

side note: It's easy to generalize this process for any number of colors.

Final count

Now, when we have such a powerful mathematical machinery, we can proceed to calculate the proper count. This time we should take into consideration larger grid, hence we must analyze more complex cycles.

Let's start from identity. We have $16$ one-piece cycles, but only $6$ may be blue. Value of $\texttt{fix}$ for identity is $16 \choose 6$.

Then $90^\circ$ and $270^\circ$ rotation have $4$ cycles, each with $4$ elemets, we cannot color such gird using $6$ colors. Hence $\texttt{fix}$ for both this rotations is $0$.

Let's move on to $180^\circ$ rotation and both vertical and horizontal flips. All of these isometries has $8$ cycles, with $2$ elements in each. So we must color $3$ out of $8$ cycles to blue. Hence result for these three is $8 \choose 3$.

And lastly, both diagonal flips has $4$ single element cycles and $6$ containing two elements. So we can pick $4$, $2$ or $0$ from diagonal which sum up to $116 = 6 + 90 + 20 = 6 + {4 \choose 2} {6 \choose 2} + {6 \choose 3}$.

What gives longed-for result (denoted with $F$)

$$ F = \frac{8008 + 3 \cdot 56 + 2 \cdot 116}{8} = \frac{8408}{8} = 1051 $$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ thank you for the answer. I understood it all except for the 90 degree rotation for 8C3 fix value. I understand that the 90degree rotation has 4 cycles and 4 elements with no way to put in 6 colors so the fix value is 0, and I understand the vertical and horizontal flip logic, but what is the third 8C3 fix value? $\endgroup$ Commented Dec 30, 2022 at 1:06
  • 1
    $\begingroup$ Oh, I meant 180 rotation not 90, it was a typo. I've already corrected it. $\endgroup$ Commented Dec 30, 2022 at 10:49

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.