Numbering the insides of a Rubiks Cube uniquely

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Sun Jan 15, 2012 8:31 pm UTC

This is a puzzle I just came up with, but it is also a question I hope to get the answer to, as it's needed for a project I'm developing.

Suppose I have a Rubiks Cube in some random configuration. Now I take it completely apart, so I end up with 27 cubelets, each of which have 0-3 sides that are coloured, and the rest are black. Now I decide to put a white sticker over all the colours, so that each cubelet only contains white and black. But before I do that, I want to be able to assemble the Rubiks Cube in the exact same configuration, but without having to look at the colours, so I decide to write numbers on all the black surfaces.

Two surfaces that meet, get the same number written on both surfaces. So a corner cube could for instance have the numbers 1, 2 and 3 written on each of its surfaces. I want to number the surfaces such that I can only assemble them into one possible configuration, given the rule that only two black surfaces with the same number can meet. Since there are 27x6-54=108 hidden surfaces on a Rubiks Cube, I could use the numbers 1 through 54.

But what I'd like to know is the minimum number of numbers I could write on the surfaces, and still only assemble it in the correct configuration. I can obviously still see which cubelets are corner, edge and centre cubelets because of the white stickers, but along with the numbers on the black surfaces, those are the only information I get to reassemble the cube.

This probably isn't important, but just for good measure I'll point out that for my example the configuration could just as easily be an invalid Rubiks Cube. The point is not the Rubiks moves, but just having a way to identify each side as one of six possible. Thus a valid Rubiks cube with one cube twisted, giving a parity of 0 would be just as fine for my puzzle. Also keep in mind that reassembling the cube back but with one of the cubes twisted compared to the original configuration yields a different configuration in this case.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby WarDaft » Sun Jan 15, 2012 10:13 pm UTC

4 numbers is enough to lock down the configuration of a slice of a cube (4 numbers around the center piece, then the corners of the slice have the numbers the that their two adjacent pieces lock to the center with) and 2 more to lock the slices together gives us an upper bound of 14 numbers.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Jplus
Posts: 1717
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Numbering the insides of a Rubiks Cube uniquely

Postby Jplus » Sun Jan 15, 2012 10:17 pm UTC

Spoilered in case people want to think for themselves first:
Spoiler:
To fix all of the corner pieces and most of the edge pieces, treat them like a "snake" that wraps around the cube (there are multiple ways to do this, as long as you start and end with an edge piece). You get a chain of 17 cubies, so you need 16 numbers to connect the intermediate surfacelets, plus 3 numbers to "branch off" the remaining edge pieces.
Now you have a "frame" in which you can attach the center cubies. Each of them only needs one number to fix its position and orientation (by connecting it to a certain side of a specific edge piece). You can reuse the numbers from the corner-and-edge chain, because these connections are from a different category so you can't confuse them.
Finally, IF you want to also fix the inner piece (I think it shouldn't matter), you only need two numbers to fix the orientation: one to a center piece, and one to another center piece not opposite to it. Again, this is a different connection category so you can reuse previously applied numbers.

Conclusion: you only need 19 numbers.

You can also chain up all cubelets in one big snake, in that case you can do it such that you have less corner-edge connections and more edge-center connections. Because of the reuse you end up needing less numbers: only 14. I leave the exact way to do that as a challenge.

Ninja'd by WarDaft's post. I think that if you combine both strategies, you can get a smaller number.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Sun Jan 15, 2012 11:35 pm UTC

WarDaft, I see what you mean, but putting 4 numbers on 4 surfaces of the center piece would ensure that the 4 edge cubes were placed correctly. But then I could swap the corner cubes of that slice around anyway I wanted to. Or am I misunderstanding you?

Also, I forgot to state that the same number can be used for more than one pair of surfaces, as long as only one possible configuration can be assembled from the numbers. And even if the same number is used on two or more pairs of surfaces, it still only counts as one number.

Edit:
I realized now, upon reading Jplus' post, that I forgot to specify one more thing. The configuration only refers to the white/coloured surfaces, not to the black ones. Thus the center cube can be turned ever which way and it will be part of the same configuration either way. So really, it wouldn't be necessary to put numbers on its surfaces or those surfaces that it touches. This is because the centre cube is unique because there's only one of it.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby WarDaft » Mon Jan 16, 2012 2:44 am UTC

Consider:

Code: Select all

  X1 1X3 3X
  2   2   2

  2   2   2
  X1 1X3 3X
  4   4   4

  4   4   4
  X1 1X3 3X


Does this not satisfy your placing criteria?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby WarDaft » Mon Jan 16, 2012 2:47 am UTC

Hmm, actually... if we use a few more numbers to glue the slices together, we can re-use 1,2,3 and 4 in each of them. That brings it down to 8.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

arkanoid0
Posts: 2
Joined: Mon Jul 19, 2010 3:56 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby arkanoid0 » Mon Jan 16, 2012 11:45 am UTC

I can do this with 6 numbers. Simply assign a number to each of the cutting plains of a rubik's cube, and put that number on every black sticker that touches it.

Yat
Posts: 131
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby Yat » Mon Jan 16, 2012 1:22 pm UTC

WarDaft wrote:Consider:

Code: Select all

  X1 1X3 3X
  2   2   2

  2   2   2
  X1 1X3 3X
  4   4   4

  4   4   4
  X1 1X3 3X


Does this not satisfy your placing criteria?


Using the same pieces, you could also get this :

Code: Select all

  X1 1X3 3X
  2   2   4

  2   2   4
  X1 1X3 3X
  4   4   2

  4   4   2
  X1 1X3 3X

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Numbering the insides of a Rubiks Cube uniquely

Postby Xias » Mon Jan 16, 2012 5:34 pm UTC

Spoiler:
You only need 2 numbers to uniquely identify each of the center pieces (1111, 1112, 1122, 1212, 1222, 2222), which leaves three different possible arrangements of edge pieces (11, 12, 22). You need three numbers to uniquely identify and rotate each of the corner pieces (112, 221, 113, 331, 223, 332, 123, 132).

Going from there, with three numbers you can uniquely label up to nine edge pieces with a 12 (1121,1122, 1123, 2121, 2122, 2123, 3121, 3122, 3123), and three each of edge pieces with 11 or 22 (1**2, 1**3, 2**3), which is perfect since you only need to label twelve.

Since the corner edge pieces have eight each of 1s, 2s, and 3s, our edge piece labeling must sum to that as well. If you arrange your center pieces in such a way that you have three edges labeled 11, three labeled 22, and six labeled 12, you can use (1122, 1123, 2121, 2123, 3121, 3122, 1112, 1222, 1113, 1223, 2113, 2223).

So the lower bound is 3, though that allows for multiple configurations.


My guess, based on intuition alone, is that the answer is

Spoiler:
Six. Label each of the center pieces 1 through 6 on all four sides (1111, 2222, etc.) This alone creates uniquely identified and rotated edge pieces. You can then uniquely identify and rotate each corner piece with no more than three numbers.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby WarDaft » Mon Jan 16, 2012 5:50 pm UTC

Yat wrote:Using the same pieces, you could also get this :

Code: Select all

  X1 1X3 3X
  2   2   4

  2   2   4
  X1 1X3 3X
  4   4   2

  4   4   2
  X1 1X3 3X


Hmm, that does satisfy the numbering, but conveniently, gluing the layers together actually solves that problem (as we cannot then flip any of the pieces)
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Tue Jan 17, 2012 11:20 pm UTC

I'm happy to see that there is being made so much effort on solving this, and I thank you for the guesses you have made so far. I need to try the suggestions out physically because it's hard for me to wrap my mind around how they will work. But I'll point one thing out that I have realized reading the thread. Not all surfaces need a number. Take for instance a Rubiks Cube from which a corner cubelet is then detached. Only one of the cubelet's surfaces would then need a number because if the face it was touching before, also had that same number, there would only be one possible way of attaching the cubelet again.

I don't know if this will actually have any effect on the minimum number, but I thought I should point it out for good measure.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

User avatar
Adacore
Posts: 2755
Joined: Fri Feb 20, 2009 12:35 pm UTC
Location: 한국 창원

Re: Numbering the insides of a Rubiks Cube uniquely

Postby Adacore » Tue Jan 17, 2012 11:49 pm UTC

I think if you remove the restriction that you have to number all sides, then that reduces the numbers needed by one, since you can just count 'blank' as one of your number pairs. So I think that would give:
Spoiler:
5 numbers, per arkanoid's solution (which intuitively seems like it would work, although I haven't analysed it in detail). Number five of the cutting planes of the rubiks cube, leave the sixth one blank.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Wed Jan 18, 2012 5:59 am UTC

I was wondering, how can you tell for sure if your suggestion yields one or more solutions? There have been some good suggestions, but I simply cannot figure out how many solutions it has, without having to try out every combination. Xias made a great discovery, but says that it yields multiple configurations, which I'd like to try and understand why that's the case.

But reading his post struck me with inspiration, and I'm now hoping that it can be done with just 4 numbers, with exactly one 4 on each centre and edge cubelet and none on the corners. And here's why.

Spoiler:
If it can be done by using only 4 numbers and giving every single black surface a number, then it can be done with 3 numbers, leaving the 4th number black. By having exactly one 4 for centres and edges and none for corners, you get 3 numbers for each cubelet. And here's the beauty of this, if you replace 1, 2, 3 with 0, 1, 2 instead, you can think of the numbers on each cube as being ternary, thus providing a number between 0 and 26 for each cube, and hopefully making each cube having a unique number, which is made easier by being able to choose the order in which you read the numbers on each cube.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

ttnarg
Posts: 39
Joined: Tue Jan 05, 2010 5:50 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ttnarg » Fri Jan 20, 2012 10:20 am UTC

I think the line "Two surfaces that meet, get the same number written on both surfaces." meens you cant leave a side blank but if you think you can then take 1 from my numbers.

upper and lower bounds so far:
Spoiler:
WarDaft solution which works in 3D even if it dose not in 2D gives us an upper bound of 6
Xias points to lable each corner differently you need 3 number which gives us a lower bound of 3

If I get time I might write a computer program to search this as I'm intressed in the anser.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Fri Jan 20, 2012 3:58 pm UTC

ttnarg, well I could've rephrased that line differently, I guess. I wrote that to specify that two surfaces get the same number and not two different numbers. But two adjoining surfaces don't need a number. They either get the same number, or stay blank. So either way they would be exactly the same.

I was thinking of writing a program myself, but that's including the added restraints from my previous post. If you make a program for the minimum number, we would get both answers, unless of course I actually find a working configuration for mine, which would mean that 3 is in fact the lowest number. And I'm glad that my problem has gained some interest with people. :)
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Numbering the insides of a Rubiks Cube uniquely

Postby Xias » Fri Jan 20, 2012 4:37 pm UTC

ThemePark wrote:I was wondering, how can you tell for sure if your suggestion yields one or more solutions?


Good question.

My original solution basically says that it's possible to uniquely solve a Rubik's cube that has been deconstructed in the way you describe using only three numbers (or two and a blank but I think the difference is unimportant). That is, it's possible to uniquely identify and rotate (in the same way that putting colored stickers on the outside of each piece does) each piece with three numbers. Someone with knowledge of which position each piece has could use that unique identification to solve the puzzle.

However, a person who does not know which position each piece has (ie someone to whom you hand all of the pieces to) might not be able to solve it, which is why I included the option for multiple configurations. I actually have no idea if multiple configurations are possible. It might be that they aren't, and any attempt to put the wrong piece somewhere will lead to a contradiction later on a la Sudoku. I don't know and don't have the capacity to find out.

So, finding a method to prove whether there are multiple solutions could prove the optimal numbers needed to be three (two with a blank).

EDIT: This puzzle reminds me of those little cardboard puzzles where you have a bunch of squares with half of a picture on each edge, and you have to arrange them so that each edge matches up.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Fri Jan 20, 2012 5:04 pm UTC

Xias, let me see if I understood you correctly. You mean that anyone who knew that cubes with 3 black surfaces would be corner cubes, cubes with 4 edge cubes and cubes with 5 centre cubes could solve it, while someone who wouldn't know this could find multiple configurations?
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Numbering the insides of a Rubiks Cube uniquely

Postby Xias » Sat Jan 21, 2012 1:27 am UTC

ThemePark wrote:Xias, let me see if I understood you correctly. You mean that anyone who knew that cubes with 3 black surfaces would be corner cubes, cubes with 4 edge cubes and cubes with 5 centre cubes could solve it, while someone who wouldn't know this could find multiple configurations?


Oh, no, of course not. In fact, I've been picturing an actual deconstructed rubik's cube, which has clearly defined corners, edges, and centers (because each piece is rounded out in a way that allows the toy to hold together while being twisted).

What I meant was, say you have four triangles with this setup. One of them is labeled with a 1 on each edge, one labeled 123, one 134, and one 142. This allows for two possible unique orientations (Try it). However, say you know that the correct solution has each number adjacent to it's twin.s Then you can arrange them correctly without any prior knowledge.

Essentially, if the rule is to label the pieces in such a way that they can be logically solved following only the rule "Each face must touch a face with the same label", then my 3-number solution would require a proof that there are no extra configurations. If having a list that says, for instance that the corner piece labeled 112 is the white-blue-orange corner piece, and so on for all of the pieces, is allowed, then my 3-number solution is optimal (because you only need 3 numbers to uniquely identify and rotate each piece, meaning you cannot confuse any two different pieces or the same piece in a different orientation.)

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Mon Jan 23, 2012 2:32 am UTC

@ttnarg: Do you have any ideas on how to check whether there is only one possible configuration with a given distribution of numbers? All I can think of is having to try every single combination of cubelets, save rotation of course, or to start off with one layer and then adding one more if the first is valid. But both ways seem to me like they'd take a lot of time to comb through.



@Xias: I am honestly still not sure I understand what you mean. If I got it right, you're talking about only getting the information and then having to make the triangles yourself, which would lead to these two solutions.

Code: Select all

________ ________
\   3   ^   3   /
 \     / \     /
  \2 1/1 1\1 4/
   \ /     \ /
    V___1___V
     \  1  /
      \2 4/
       \ /
        V

________ ________
\   2   ^   2   /
 \     / \     /
  \3 1/1 1\1 4/
   \ /     \ /
    V___1___V
     \  1  /
      \3 4/
       \ /
        V


which depends on how you write the numbers on the 123 piece. If that is the case, I intend on writing the numbers on the cubes for my project, instead of just giving the numbers. If I got you wrong, then please let me know, I'd really like to understand this. Also, I'm not sure what you mean by each number being adjacent to its twin, which is the requirement for the puzzle I stated anyway.



@Everybody: I got a lot of inspiration from Xias' post at January 16th @6:34pm UTC. So since then I have been mixing the requirements for my own project with the puzzle I originally stated, as I wanted to find the solution for this puzzle in order to further work on the project. But I have decided to go another way after Xias' post. So because I am now also interested in finding the minimum number, and to avoid any confusion, I'll restate the original puzzle that this thread is for solving, and then I'll try and figure out the puzzle for my project myself, based on the information I gathered here, which I thank all of you for.

The idea is to take a 3x3x3 cube that has some way of obtaining unique configurations. I chose a Rubik's Cube, but it could be any 3x3x3 cube for that matter. And the parity issue of the Rubik's Cube is not important either, the only point is having a 3x3x3 cube with a known and unique configuration. And also, using the Rubik's Cube, the mechanics aren't important, for the purpose of this puzzle just think of it as 27 cubes that are the exact same size and shape.

So I have such a cube in my hand. I remember the exact configuration it was in, and I then put white stickers on all 54 visible faces so that by looking at it, it's not possible to figure out the configuration, you'd actually have to peel off some stickers but that's not allowed. Having done that, I then disassemble the cube into its 27 cubelets. All 54 faces that were hidden before on the inside are black, and I write a number, a letter or a symbol on them. It doesn't matter what it is, but let's go with numbers for this. Each black face HAS to have a number, and if two black faces met before the disassembly they get the same number. Thus it can be done with 27 pairs of numbers.

The idea is then to number the black face pairs in such a way that I can give the 27 cubelets to any person, even someone who doesn't know about Rubik's Cubes, and tell that person that their job is to assemble the cube back together, by pairing off the black faces with the same number on them and ending up with a 3x3x3 cube. When that person has done that, I then peel off the white stickers to ensure that he has done so correctly.

The idea of the puzzle is to find the minimum number of numbers/letters/symbols that can be applied to all black surfaces, but in such a way that it's only possible to reach ONE configuration. There might be 10 1s which is fine, as long as all but one way of pairing off those 1s and the rest of the numbers are invalid. If there's more than one way, this way of placing the numbers is not a valid solution.

And that's the description of the puzzle. The reason I mentioned blanks at one point is because I didn't want to put numbers on all black pairs. But as it has pointed out, the minimum number is just one less if you use blanks, as one of the numbers used in the solution can be replaced by a blank surface. So blanks are only important to my project.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby tomtom2357 » Mon Jan 23, 2012 10:09 am UTC

In theory, if you are allowed to make your numbers as high as you want, then you only need one number, and you use godel numbering to encode the right configuration.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby WarDaft » Mon Jan 23, 2012 10:42 am UTC

tomtom2357 wrote:In theory, if you are allowed to make your numbers as high as you want, then you only need one number, and you use godel numbering to encode the right configuration.


Except that you can't distinguish between two corner pieces if you're only using one number. It doesn't matter if you encode the configuration for a cube, all 8 corners will have the same encoding, and you will have no way to tell which goes where.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Numbering the insides of a Rubiks Cube uniquely

Postby tomtom2357 » Tue Jan 24, 2012 1:48 am UTC

Okay then, you use 7 numbers. The corner closest to you uses the godel numbering as before, then you proceed to go in a clockwise direction around the three other close corners (incrementing by 1 each corner so you can tell the difference), then you do the same for the other three corners farther away, and you leave the opposite corner blank, and you have effectively distinguished between the corners. You could probably do less, you just need to break the symmetry, the godel numbering encodes the rest.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Numbering the insides of a Rubiks Cube uniquely

Postby ThemePark » Sun Jan 29, 2012 1:11 am UTC

Okay, so after having given this some thought, I have a gut feeling that I have come up with a way to numbering the black sides using only 3 sides, and doing so uniquely. But I haven't done any testing on this, so feel free to prove me wrong.

To apply the numbers, I start out with a Rubiks Cube in its solved state. I then replace all the colours with a number from 1 to 6, both inclusive, and I do this in such a way that the rules of a dice apply, i.e. two opposite sides add up to 7. Now I take the cube apart, making sure to remember where each cubelet goes, and I add the remaining numbers on the black sides of the corner, edge and middle cubes, again using the dice rules. That leaves the centre dice which can't initially be numbered since only one side is known, but using the numbers of the sides touching it, they too can be numbered, that's why you need to remember their position up until this point. Finally, to go from 6 to 3 numbers, I simply use modulo 3 on all numbers, so 1=1, 2=2, 3=0, 4=1, 5=2, 6=0.

And I believe this way of numbering the cubelets should ensure a unique configuration once you reassemble them. But I'm hoping someone will be able to try this out and prove me right or wrong.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 4 guests