Random Cubing Discussion

What's the minimum number of yes/no questions (you are only allowed to ask if one sticker is a certain color) that you have to ask to be able to solve any cube? You can't see the cube of course, and you have amazing logical deduction and piece tracking skills and so on.
 
Last edited:
guysensei1 said:
What's the minimum number of yes/no questions (you are only allowed to ask if one sticker is a certain color) that you have to ask to be able to solve any cube? You can't see the cube of course, and you have amazing logical deduction and piece tracking skills and so on.
Click to expand...

Just some quick thoughts, I might try to actually solve it later:

1. Your question is equivalent to "What number of stickers do you need to know in order to uniquely determine the state of the cube (assuming it's solvable)?"
2. In order to know the colors of a corner piece you only need to see two of it stickers (assuming you know the way the centers are arranged. If you don't, that can take six more questions.)
3. If you know all corners but one, and all edges but one, you know everything. So an upper bound would be 2*7 (all corners - 1) + 2 * 11 (all edges - 1) = 36.
You can actually make it 35 because if you don't know one of the other stickers, you can figure it out by the permutation cycles.
(Now I see that you're talking about yes/no questions, and not asking for color of a sticker. But you can just ask about each of the six colors - or actually, just five. So 5*35 is an upper bound, yet it's impossible that each sticker would require 5 questions so you can probably make it better).
4. A trivial lower bound: each question gives you two possible answers, so you need at least log(number of states)~65.2 questions, so that's at least 66. If you're considering colors and not yes/no questions, that would be ~25.23, so at least 26.

EDIT: The bound mentioned in 3. is actually 8*5+8*5+8*4+8*3+3*2 = 142, which is better than 5*35 = 175. (I got to that by arguing that there aren't that much stickers that take a lot of questions to determine their color)
 
Last edited:
guysensei1 said:
What's the minimum number of yes/no questions (you are only allowed to ask if one sticker is a certain color) that you have to ask to be able to solve any cube? You can't see the cube of course, and you have amazing logical deduction and piece tracking skills and so on.
Click to expand...
That's a fascinating question! I'm not even sure how calculable it is, but great question nonetheless.

A reasonable upper bound is 43, or 45 if you don't start with the cube in a known orientation. One question for each of the 54 stickers on the cube, minus 6 questions for each center sticker (I'm assuming the cube starts in a fixed orientation; if it doesn't, then add 2, because that's how many center stickers you need to know in order to know the cube's orientation), and minus 3 corner stickers and 2 edge stickers, since you can use the configuration of the other pieces to determine the exact position of the final corner and final edge. This would tell you where every piece is on the cube, and be sufficient for a BLD solve, or even a speedsolve, since we're given amazing deduction, piece tracking, and memory. ;)

54 stickers - 6 centers - 3 corner stickers - 2 edge stickers = 43, plus 2 to determine center orientation if that isn't given = 45.

There are plenty of circumstances where you wouldn't need to know all three stickers on a piece to know what every sticker on that piece was, but I have no idea how to calculate how frequently you wouldn't have to know every sticker. I imagine it would vary a lot depending on how lucky you get with your questions. For example, if you've solving white cross, have solved three white corners already and you get lucky and ask about a particular corner sticker location and are told it's white, you know what the other stickers on that piece are immediately, with no further questions. If you don't get lucky, you'll have to ask more than one question about that specific piece. I imagine there are tons of tricks for getting as much information as possible out of what stickers you do know, and to deduce what the rest of the stickers would have to be, but I wouldn't even know where to begin with calculating what the minimum number of yes/no questions needed to solve the cube 100% of the time is.

One approach that I think technically should be allowed is filling in the colors of the cube, Soduku style. If you know 75% or so of the stickers on the cube, you could use your amazing deduction skills to make a list of every possible state the cube can be in; every possible way the 25% of the stickers you don't know the colors of could go on the cube in a way that makes the cube solvable. You could then find a solution to the cube in every one of those positions, and although you wouldn't know which of your many solutions was actually the solution to the cube, you would know that one of those many solutions does in fact solve the cube. In this case, you wouldn't need anywhere near 43 yes/no questions to solve the cube. This approach is a bit of a slippery slope, though, as it hypothetically would work without knowing any of the stickers. You'd know that one out of your 57 quintillion solutions solved the cube then as well. :p

I look forward to seeing a true puzzle theoretician get their hands on this question. :)

EDIT: ninja'd, but I'll leave the ideas here anyway even though some of them were already thought of.

The previous poster is right about only needing to know two corner stickers for each corner; that's a pretty simple mistake I made. I think that lowers my upper bound from 43 to 36, as you need one less corner sticker on each of the seven corners that aren't the final corner, which can be determined by the previous 7 corners alone.

EDIT2: Totally forgot about the yes/no aspect. I was thinking one word answers, not yes/no. So, this post is terribly flawed.
 
Last edited:
If you knew the locations of all the edges(so 22 stickers,) wouldn't you only need to know the orientation of the last two corners in order to determine what they are? This would mean you'd need to get one sticker on each piece, so you'd be at -4 instead of -3, giving you 42/44 questions.

EDIT: You wouldn't even need the guess a sticker of the last piece, because you'll know the orientation of 7 corners, thus determining the 8th. so -5 for corners instead of -3, giving you 41/43 questions.

EDIT2: oh I didn't even see the post detailing it all :o
 
Last edited:
You must log in or register to reply here.

Similar threads

Xishem
Random Blindfold Cubing Discussion
99 100 101
Replies
2,007
Views
260,589
abunickabhi
abunickabhi
n0nco
send your random facts/information about cubing
2 3
Replies
53
Views
7,440
Caleb Valenzuela
Caleb Valenzuela
Cuber.Hello.com(:
Cubing memes I found online (: (also being rickrolled by random people. Come with me if u want to cringe) XD
3 4 5
Replies
91
Views
9,494
MeGrimlockKing
MeGrimlockKing
CubeRed
Random cubing facts
Replies
2
Views
1,154
abunickabhi
abunickabhi
That70sShowDude
Selling 2 random assortments of Rubik's Cubes and cubing accessories on ebay
Replies
0
Views
1,100
That70sShowDude
That70sShowDude
Back
Top