Obscuring squares of Rubik's cube

Question

This is a combinatorial question related to Rubik's cube $3\times3\times3$ (and, in the end, its generalizations $n\times n\times n$). I assume that the readers are familiar with this puzzle. Let's recall some basic terminology and conventions to rule out possible ambiguities. In the following, we use the words state and configuration interchangeably, as exact synonyms.

We are only interested in configurations of Rubik's cube where it has the shape of a cube (so, we consider rotations of its layers by an angle of $90^\circ$ as atomic transformations, and no incomplete rotations are allowed). Also, we consider configurations that can be obtained from one another by solid rotations of the cube as a whole (without any relative movements of its parts) as identical.

The cube has $6$ faces, each one of them is a $3\times3$ grid of squares — $9$ squares per face, and $54$ squares in total. Each square is of a solid color. Orientation of every single square is irrelevant (in fact, this rule has significance only for central squares). There are $6$ different colors, and there are $9$ squares of each color. There is a single selected state where each face consists of all squares of the same color — this state is called the solved state. A state that can be reached from the solved state by a sequence of valid rotations of layers is called a valid state (the solved state, of course, is a valid state too).

As a side note, if we allowed disassembling the cube into its parts and reassemling them, then we would get the number of possible states $12$ times larger than the set of valid states (this larger set would be a disjoint union of $12$ equivalence classes under valid rotations, each of the classes called an orbit). We are only interested in valid states in the following.

Usually, it is assumed that colors of all squares on the cube are visible. Let's consider a possibility that some squares may be obscured (e.g. completely covered by an opaque colorless sticker), so that their colors are not visible.

In general, obscuring some squares can result in some states becoming visually indistinguishable. As trivial examples, obscuring all $54$ squares makes all states indistinguishable, but obscuring only $1$ square (no matter which one) does not make any states indistinguishable.

1. What maximal number of squares in Rubik's cube $3\times3\times3$ can be obscured without making any states indistinguishable?

2. What maximal number of squares in Rubik's cube $2\times 2\times 2$ can be obscured without making any states indistinguishable?

3. What maximal number of squares in Rubik's cube $n\times n\times n$ can be obscured without making any states indistinguishable? Can we find a general formula, recurrence relation, etc. to compute it for every $n\in\mathbb N$?

Answer 1

Disclaimer: This is an old incomplete answer, now aged multiple years. I started this before I had any formal math education and I never came back to finish this.

---

---

---

To make our lives easier, we can separate the pieces by 3 types:

Edges (3 stickers)
Sides (2 stickers)
Centers (1 sticker)

Also note that im observing a cube with Yellow and Black( I call it White later on) colors for the top and bottom sides as my default color scheme.
(Other pieces follow Red, Blue, Orange, Green)

---

For the $3\times3\times3$ Rubik's cube, first we can solve for the middle parts.

We can conclude that if the color scheme is known, that all obscured centers can be determined if we have at least 2 neighbour ones.
This means we can peel off 4 centers if we keep 2 neighbour ones. This can be checked by playing with its own cube or simply by following the laws of legal positions and using something like a solver help you out. (This is because centers can't be really switched, but the pieces around them can so that it looks that way)

Then lets see how many stickers from the edge pieces can be obscured or peeled off, since any configuration of $n\times n\times n$ always has exactly 8 edges.

We can list them by the colors they contain:
(Red, Blue, Green, Orange, Yellow, White) $$ R,G,Y $$ $$ R,G,W $$ $$ R,B,Y $$ $$ R,B,W $$ $$ O,G,Y $$ $$ O,G,W $$ $$ O,B,Y $$ $$ O,B,W $$

If you want to know how many stickers can be peeled off and still be able to identify each corner, you can ask yourself; How many stickers you can take so that when putting them back, you have only one possible way to do so?

I have found out the maximum number of 12 out of 24 stickers; by taking all R or O, then all B or G and finally all Y or W.
Here is an example:

$$ -,-,- $$ $$ -,-,W $$ $$ -,B,- $$ $$ -,B,W $$ $$ O,-,- $$ $$ O,-,W $$ $$ O,B,- $$ $$ O,B,W $$

Now by shuflling the order and rotation of all 8 edges in every way possible, there will be only one way to stick the removed stickers, thus you still can identify the pieces.

Now the Side pieces, which might be a bit tricky.
On the $3\times3\times3$ Rubik's cube, there are 12 Edge pieces:

$$ G,R $$ $$ R,B $$ $$ B,O $$ $$ O,G $$ $$ Y,G $$ $$ G,W $$ $$ W,B $$ $$ B,Y $$ $$ R,W $$ $$ W,O $$ $$ O,Y $$ $$ Y,R $$

Now you can try to do the same thing.
Firstly I tried to remove all White stickers, then it allows me to take one color from $Y,?$ pieces other than yellow, and after that nothing more can be taken without providing multiple solutions for the edges; so that was 5 stickers.
Then after other failed attempts, I found you can remove 6 stickers; one of each color so that there aren't multiple stickers of the same color standing without their second color, and I'm kinda sure it can't be done with more than 6 here.
If someone can do better here, please let me know.

So if I haven't made a mistake, for the $3\times3\times3$ Rubik's cube you can remove total of $12+6+4 = 22$ out of 54 stickers top (following the things I pointed out) without losing any information about the cube's states.

The $2\times2\times2$ Rubik's cube is made of only 8 edge pieces, so 12 out of 24 stickers can be removed here.

---

We can now try to generalize this to other $n\times n\times n$ cubes.

We now know that we can for;
$n=2$ take 12 out of 24
$n=3$ take 22 out of 54

For any $n\times n\times n$ cube, we always have 8 edges, so thats $+12$ obscured stickers.

For the side pieces, we have $n$ of each piece (sorted set of pieces):

$$ W,R $$ $$ W,B $$ $$ W,G $$ $$ W,O $$ $$ Y,R $$ $$ Y,B $$ $$ Y,G $$ $$ Y,O $$ $$ R,B $$ $$ R,G $$ $$ O,B $$ $$ O,G $$

There is nothing more to do here than apply the same thing I did in $3\times 3\times 3$ cube;
Remove 6 stickers, one of each color so that there aren't multiple stickers of the same color standing without their second color and do that for each new set of the side pieces.
This provides us with $6\times(n-2)$ pieces more to obscure.
Again, if you can do better with the sorted set I provided, please let me know.

---

So far then, the number of stickers we can obscure is: $$12+6\times(n-2)+C$$

Where $C$ is the number of "mobile" and "immobile" centers we can obscure, that appear after $n>3$ and have yet to be figured out.
(when $n=3$ then $c=4$ )

---

So now, the center pieces at $4\times 4\times 4$ cube and every other with $2k$ sides ($k>1$) are different than every $2k+1$ sided cubes;

The $2k+1$ like our standart $3\times3\times3$ cube have 6 "real centers" which are immobile and $4$ out of $6$ can be obscured, the rest one-sticker centers here are "mobile" and behave differently when being rotated.
Same goes for all of centers which are all "mobile" in $2k$ cubes.

How many of these mobile centers can be obscured? I would say for a starting bound, all of one color which is then:
$C = (n-2)^2$ for $n>3$
And gives us finally:

$$12+6\times(n-2)+(n-2)^2$$

Pieces we can surely obscure.

I haven't yet started checked if more can be obscured on these centers, but thats because its now end of the day and I don't have any more time, and now decided to post my progress so far.

I think you could take it from here to finish up the generalization and try to see if it is possible to obscure more than $(n-2)^2$ stickers using the color scheme and legal permutations, so maybe separate formulas for $2k$ and $2k+1$ can be found.

Update

Actually I don't think the mobile centers should provide us with any additional problems, thus we can take for $C$ that it is: $ = (n-2)^2 \times 4$ Since we need only 2 full center colors that will tell us the rest, most easily after solving the cube to its solved state.

Then we have: $$12+6\times(n-2)+4\times(n-2)^2$$

I have classes to be on early tomorrow morning now, so good night.

Edit: This should be computed and checked to make sure I haven't made a mistake somewhere.

Answer 2

format of terms used in this answer:

removal = obscuring (hiding a sticker)

piece = mini-cube

face = side of a piece =equiv sticker

$n$ = one 1-dimensional face unit

side = whole face of the rubik's cube

cube = entire rubik's cube

state = configuration

type = which form of piece (corner-proper, edge-proper, or edgeless face)

c = corner_piece (starts with $3C_v$ = three visible faces)

e = edge-without-corner_piece (starts with $2E_v$)

f = face-without-edge_piece (starts with $1F_v$)

$C$ = an individual c face

$C_r$ = a C removed

$C_v$ = a visible C

$C_A$ = all c faces combined

${C_A}_v$ = all visible c faces

$E_A$ = all e faces combined

$F_A$ = all f faces combined

$T_v$ = all visible faces combined ($C_v$+$E_v$+$F_v$)

$X_A$ = all deducible faces

$({X_A})_n$ = arbitrary # deducible faces for $n^3$ cube

(⇒ solve $∀x=r:$ max$[{(X_A)}_n]$ = ${(T_A)}_n$-min$[{(T_v)}_n]$)

---

This question (well, three questions to the same end) boils down to two considerations: What is minimal stickers required to know what the solved state is supposed to look like, and minimal stickers needed to retain the identities of them all. Considering the first part without the second, as few as two diagonally opposite corner pieces would suffice ($2c$, establishing every color's/side's correct alignment to every other). Of course, this defies the second necessity, since not only the other 6 corner pieces' but all the other pieces' identities would become indistinguishable. Considering the second part (which mostly if not wholly absorbs the first), one can afford one piece of each type getting stripped of its 1, 2, and 3 stickers ($6$ so far). Of course there is a lowerbound of $n^2$ (one whole face, 9n for a 3×3×3 cube), but we can do better than that for the n=3 cube (edit bolded for emphasis). For n≥[some integer ≥4], the general maximal formula will include n^2; this formula might be able to fit for smaller n values despite that the particular algorithms for determining the actual faces to remove from smallish differs from what the formula implies. Consider n=50 cube.

To what extent depends upon which variation of 2^2=4 possible ways to interpret the problem as originally presented: do we know correct color-scheme alignment (medium outside information, reasonable supposition since already know how to play the puzzlegame and have access to internet, and confirmed in response to Vepir's question); do we know a particular pattern to how the faces were removed (heftier outside information, mostly absorbing preceding knowledge); do we know both of these info (heftiest outside information); or de we know none of these info (minimum outside information).

I will approach this problem assuming minimal outside information to start, because considering the difference affordable from there upward seems easier to me, and I am curious how the up to four different general formulas would differ.

---

Since any valid state with all stickers visible can be deduced as such (by solving it, even if achieving that from a random state might be computationally pricey), they convey the same information; so one sensible way to think of this problem is as subtracting stickers from the solved state. Besides the straightforward description, the response to Vepir's question confirming knowledge of the color scheme may and likely will increase the maximal count by allowing for more removals of non-corner edge pieces. To start, however, I will ignore this fact. Another possible consideration for n>3 (and possibly even n<4) is if you can presuppose knowledge of pattern to which faces you hid. When I get to the part of formulating a general pattern, I will assume initially that the obfuscated cube is to be decipherable by a stranger.

Any piece within a rubik's cube of of side n length 3 or greater can be separated into three disjoint categories: corner [3 different colors], edge without corner [2 different colors], and face without either [1 color]. In the case of 2×2×2 cube, each type shares the same category (is not disjoint). The number of total faces (visible or not) as a function of integer n is equal to 6⋅(n^2). These might be helpful later in constructing a general formula.

Focusing now on the 3×3×3 cube, with all 8⋅3=24 corner stickers removed you could still ascertain what state$_{[solved]}$ should look like by using $c_a$=${(c_a)}_v$ to track a course around the cube. But that would also make those 8 c indistinguishable, so 8⋅2=16 removals allowed. Remove the remaining face from one of the c making it blank and 1 from a single f = 16+2=18 removals allowed (lower bound), since these single "extra" oddball removals from two different types of the three does not by itself prevent deduction of solved state. That leaves the 10 untouched e and 7 one-sticker c pieces to consider. Well, at least one e could be totally removed, so 18+1=19 removals lower_bound for the 3×3×3 cube.

Here is a good place to pause to calculate the formulas for the different types of pieces (by how many original faces contained) as equations based on n.

corners: 8 (constant); $c_n$=8. non-corner edges: as few as 0, for n={1,2}. For every n beyond that, it increases by 10; $e_n$=10(n-2). non-edge/corner faces: all the rest. For n={1,2}, 0. For every n beyond that, it increases by faces times square of two less than n: $f_n$=6(n-2)^2. Any beyond 1 from this category becomes indistinguishable with its only sticker removed, so +1 should be the only effect to the general formula from this type.

Back to optimizing the 3×3×3 cube. None of the remaining 7 C could get removed, since that would make those c indistinguishable. That leaves the nine remaining e to focus on, or possibly all ten if it can ensure a greater maximum (past lowerbound of 20 or alternative removals). Focusing on the 9 is simpler than 10 and likely the correct path so I shall. Every c piece serves for this purpose also as an e piece, but with all of them out for use except for one serving now as an f piece, the remaining e pieces are the only pieces showing more than 1 side/color. The question now is how many of the eight two-side relationships can be removed from the cube before the full identities of the removed (non-corner) ones cannot be deduced. I believe the answer is 4: two on opposite sides of and sharing a side, the other two on reverse side diagonal from the first 2, allowing for an unobstructed route linking all six sides (contiguous, since every side is contiguous). One of these is accounted for already. So long as the other absent face of that piece is considered (rather than preserving it still on) when deciding the remaining 3 to remove, which I believe means choosing the same "obverse" side (as opposed to the opposite "reverse" side) as the first two mentioned (proving this is another task), it should work out. That results in 19+3 = 22 removals from the 3×3×3 cube's 54 faces without knowing the color scheme. If you know the color scheme, then one whole side could be "removed" (possibly better), so long doesn't cost an existing deduction, which I think it wouldn't if you did so unto the remaining "reverse" side: 22+2 = 24 removals from the 3×3×3 with prior knowledge of the color scheme.

This brings up an important consideration for a general formula. While for n<4 a majority of the removals came from corner pieces, as n increases the corner pieces remains constant whereas the edge pieces increases linearly. As such, for higher n values the majority of faux "data-hiding" will be unto non-corner edge pieces, in alternating half-visible fashion. To formulate a general equation, at first I will suppose no prior knowledge of the color scheme nor methodology to the removals. Considering for a moment the particular case of a 4×4×4, there are 20⋅2=40 E, compared to 8⋅3 = 24 C. Since the corner-pieces reveal more information about the whole cube (particularly without prior info), retaining most of them in favor removing all of the non-corner edgepiece stickers likely yields higher value of lossless data-compression. I'm not sure yet how to formulate this into a general equation without if/else-style verbiage included, though it is probably possible. I will come up with a general formula and post it as a comment or update this post, but for now I'll leave with a summary of some relationships to n-width to consider:

corner stickers = ${(C_A)}_n = 3{c_a} = 3⋅8$

edge stickers = ${(E_A)}_n = 2{(e_a)}_{n-2} = 2[10(n-2)]$

face stickers = ${(F_A)}_n = 1{(f_a)}_{n-2} = 1[6(n-2)^2]$

total stickers = ${(T_A)}_n = 6*{(F_A)}_n = 6⋅n^2$

Considering lower n^3 cubes (to help figure out a general pattern and answer second question):

For n=1, no prior knowledge, 1 face could get removed. With prior knowledge of correct scheme, presumably all except two = 4 of the six could get removed.

For n=2, no prior knowledge, trickier. $T_2$ = ${(C_A)}_2$ = 24. A maximum bound entails linking all sides, from 3 C with 2 c each ⇒ max$[{(X_A)}_2]$ = ${(T_A)}_2$-min$[{(T_v)}_2$] = max$[{(X_A)}_2]$ = $24-(2⋅3)$ = 18. For n=2 with prior knowledge of color scheme: ..

---

For n=4, no prior knowledge: min$[{(E_v)}_4]$ = min$[{(e_v)}_4]$÷2-1 =20÷2-1=9 ⇒ max$[{(E_r)}_4]$=${(E_A)}_4$-9 = 40-9 =31. max$[{(F_r)}_4]$=1. max$[{C_r}_4]$=8⋅2+1=17. Assuming no contradictions (noting thatn=4 is even, n=5 is odd,..) max${(X_A)}_4$=${(T_r)}_4$ = max$[{C_r}_4]$+max$[{(E_r)}_4]$+max$[{(F_r)}_n]$ = 17+31+1 = {49 = upperbound}.

$∀n∈N:$upperbound$[{(X_A)}_n]$ = max$[{(C_r)}_n]$+max$[{(E_r)}_n]$+max$[{(F_r)}_n]$,

⇒ max$[{(X_A)}_n] ≤ 17+(½{(E_A)}_n+1)+1$

⇒ max$[{(X_A)}_n] ≤ 17+1+(½(2[10(n-2)])+1)$

⇒ max$[{(X_A)}_n] ≤ (10n-20+1)+18$

⇒ max$[{(X_A)}_n] $?$=$?$ 10n-2$ doesn't fit; too high

but $[{(X_A)}_n]=10n-9$ seems pretty close for n<4

---

large n value: n=50

lowerbound[max$[{(X_A)}_n]$ = ${f_n}^2+3C_v+2E_v$ = $n^2+3+2$

lowerbound[max$[{(X_A)}_50]$ = $50^2+5$: one whole side removed plus one whole opposite corner and one whole middle edge piece (these latter 5 removals might not all apply, but are guaranteed in a simple quadratic lowerbound). So what other faces can get removed (and still get ascertained by a stranger familiar with the rules of the puzzle but not the color scheme used)?