Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Thu Apr 24, 2014 2:49 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 14 posts ] 
Author Message
 Post subject: How many stickers does a cube need?
PostPosted: Tue Nov 05, 2013 6:24 am 
Offline
User avatar

Joined: Mon Apr 20, 2009 5:24 am
This is a continuation of viewtopic.php?f=8&t=22729
When I saw that topic I suddenly wanted to peel stickers off to get an optimally unstickered cube. But I didn't like how the problem was left unsolved :| . The only confirmed solution was 20 removed stickers, and that was done quite randomly IMO. So ... here's my take (complete with steps). I removed 24 stickers. Please confirm if this is indeed a solution.

The problem
You have a 3x3 cube, and a limited number of stickers. You want to save as many stickers as you can. Any two pieces stickered identically are considered indistinguishable. Any state where all faces have one color on them are considered solved states, even if it wasn't the same as the original "solved" state. You have no memory of which sticker were removed, but you do remember the color scheme. For simplicity, its the BOY color scheme. When scrambled, the cube can be in any spatial orientation.
How many stickers can you remove and still keep one unique solution?

Limitations of a legal cube position:
Only an even number of edges can have swapped orientation
The orientation twists of corners must add up to a whole number of twists
Only an even number of (edge-swaps + corner-swaps + center axis quarter turns) are allowed

Now here's my solution

Corners
I tried to make a huge even-numbered cycle of adjacent corners, since adjacent corners with 1 sticker are interchangeable.
Image
Keeping 1 sticker is better than keeping 2, but keeping none severely limits your options, because any 0-sticker corner can swap with 0- or 1-sticker corners indistinguishably.
I used an even number because that requires an odd number of swaps, which means the edges must have an odd number of swaps as well. I can't get past 6, because there are only 6 colors. An 8-cycle leaves 2 pairs of identical edges.
This is not a unique state, but the other solved state require at least 1 pair of edges to swap. If I fix the edges, then this alternative solution will be visually apparent.

Edges
I started with the 6-cycle for edges, and I made a small modification. Luckily, I came across a state with only 1 visibly solved state. At least I think. Please verify this step - its the weakest link.
Image
There is a 3-cycle of indistinguishable edges, but if you use it, you end up with an odd number of orientation swaps. So it can't be legally solved from there. I think.

Centers
Only 2 centers are needed to uniquely fix the center axis. There will only be 1 visibly correct state.

Corners II
There are still 2 corners with 3 stickers. You only need 2 stickers to identify any corner. So I removed one from each. As for why I specifically removed a yellow and a blue sticker...you'll see :wink:

Image

Final Roundup
All centers are fixed. The corners has 1 alternate state, but that leaves at least 1 swap with the edges. The edges are fixed. So there is only 1 solution.
-12 stickers from the corners
-6 stickers from the edges
-4 stickers from the centers
-2 stickers from the corners (II)
24 stickers removed (30 stickers remaining)

Image

How pretty, every face has an equal number of stickers! (That's why I specifically removed 1 yellow and 1 blue from Corners II)

You can test this cube out using this applet. I can't find any others that lets you blank out stickers and play by dragging.
http://www.randelshofer.ch/rubik/virtua ... tions.html

So ... is this the optimal solution? Is this a solution?

_________________
I'm going to try learning puzzle design!
*10 years later...*
Yes! I made a sphere! Now, what was step 2 again?


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Tue Nov 05, 2013 8:41 am 
Offline
User avatar

Joined: Wed Jun 19, 2013 2:50 pm
Location: Deep in the Heart of Texas
I remember going through that post a while back because of someone else's cube they had taken stickers off of. I now stand by my guess of 24 because someone made it. Who knows, maybe someone can take off 25 or 26 in the near future, and maintain a single solution

_________________
For all of you that bought a KO 8x8x8: You should have bought a V8!


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Wed Nov 06, 2013 1:39 am 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
Nice problem. But why restrict the color scheme to BOY? For your stickering, if you don't know it's BOY, is there another solution?


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Wed Nov 06, 2013 2:51 am 
Offline
User avatar

Joined: Mon Apr 20, 2009 5:24 am
I don't really know how to go about solving this if the color scheme is unknown, but I don't think it's easy to solve a cube originally in a certain color scheme into another color scheme, so it's not really going to invalidate a solution. Here's what I think:

Most solutions would contain the 2 centers. If you fix everything else, you can get away with 1. The centers don't move, so to solve in a different color scheme, only the other 4-5 centers are allowed to be exchange colors. Say you wanted to exchange the colors of a set of faces (at least 2 faces). Then all cubies on either of these faces must change places. But at least 3 cubies (likely 6-12) of them intersect with the faces of the known centers, and when these pieces move, they will look out of place. And the new ones that take their place will also look out of place. So you have to give 2 homes for 6-24 pieces.
Any non-center piece can be identified by 2 stickers, so any piece with 2 stickers will look misplaced unless it's where it should be. So you have at least 6 cubies with 1 or 0 colors. Having <=1 color is not enough - that one color must be a color that the piece should have in its new position (after the color scheme swap). It takes some effort to find a state where these 6-24 cubies fulfill these conditions and cannot swap with one another.

_________________
I'm going to try learning puzzle design!
*10 years later...*
Yes! I made a sphere! Now, what was step 2 again?


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Wed Nov 06, 2013 1:34 pm 
Offline
User avatar

Joined: Sun Jul 14, 2013 11:10 pm
bhearn wrote:
Nice problem. But why restrict the color scheme to BOY? For your stickering, if you don't know it's BOY, is there another solution?

Looking at it, no two corners are identical, so it's possible to eventually figure it out.

_________________
My budding baby blog, Twisted Interests!


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Fri Nov 08, 2013 4:43 am 
Offline
User avatar

Joined: Mon Apr 20, 2009 5:24 am
Ok, I tried to solve this cube a few times in the virtual simulation. Its a lot harder than a fully stickered 3x3 :D . I tried my best to forget the original sticker pattern, and here's the results.

First solve: Cannot do the last F2L pair without making huge changes to the cross - the 2 candidates for the last edge were both in the cross. When I finally solved F2L, the last layer was easy and the solved cube looked identical to how I set it up.

Second solve: F2L went by acceptably, and I tried to make it different from the original. However, the last layer had what both pseudo-OLL and pseudo-PLL parity. According to how I designed the scheme, that means I used the alternate corner configuration and the 3-cycle in the edges.

Third solve: Again, the last F2L pair was blocked, but I overcame the obstacle in a different way. I ended up with only pseudo-OLL parity. The reason why I didn't get only pseudo-PLL parity so far is probably because I consciously tried to make the white face look different from how it was set-up.

Fourth solve: I focused more on the corners and left the edges in the original configuration. When I got to the last layer, I figured that the orientation of the last 2 corners couldn't work out. There was no valid place for the two yellow stickers. But they both didn't have a yellow sticker, so it was possible to make each face of the cube the same color an alternate way. Thus I found a secondary solution

Fine, my solution failed. Here's why:

Recall the 12 stickers I took from the corners. I intended them to only have 1 alternative solution, and that was supposed to be the 6-cycle. But it turns out that you can also do 2 swaps and some legal orientation changes; that won't affect the edges.

Image

The blue lines represent the alternative solution I had under control. The red lines show the pairs of swaps that I didn't notice. The yellow and white cubies stay on the same face, while the red and orange ones get oriented in opposite directions. This is what the cube looks like after the swap:

Image

I'm trying to find another way to remove 14 stickers from the corners without introducing too many alternative solutions. I'll tell you if I found one. But for now, you can remove 13, and here's how it looks.

Image

This one is unique, and it would work on a 2x2x2 as well.

_________________
I'm going to try learning puzzle design!
*10 years later...*
Yes! I made a sphere! Now, what was step 2 again?


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Fri Nov 08, 2013 11:16 am 
Offline
User avatar

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
JubilantJD wrote:
I'm trying to find another way to remove 14 stickers from the corners without introducing too many alternative solutions. I'll tell you if I found one. But for now, you can remove 13, and here's how it looks.

Image

This one is unique, and it would work on a 2x2x2 as well.

I believe this is exactly the solution I presented for the 2x2x2 in the following post:

viewtopic.php?p=272691#p272691

Anyway, I think it's cool that this topic has been revived, and I hope you succeed in finding a minimal stickering!


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Fri Nov 08, 2013 11:35 am 
Offline
User avatar

Joined: Mon Apr 20, 2009 5:24 am
Quote:
I believe this is exactly the solution I presented for the 2x2x2 in the following post:

Oh, I vaguely remembered reading this stickering pattern and testing it out before. I checked just now and found that it was from your post in the old topic. So, I guess I should've given credit :oops:

I have a case with 14 removed corner stickers in the works. It seems promising: there are no indistinguishable 2-swaps, and there is my intended 6-cycle. But who knows, maybe a wild 5-cycle lurks in it.

_________________
I'm going to try learning puzzle design!
*10 years later...*
Yes! I made a sphere! Now, what was step 2 again?


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Fri Nov 08, 2013 11:54 am 
Offline
User avatar

Joined: Fri Jan 07, 2011 2:37 pm
This thread on the SpeedSolving forum discusses this topic. It might help. Also, a video was made based on one of the proposed solutions.

The SpeedSolving thread was started in 2010. That was before this one (which has already been mentioned). Despite the difference in dates, I don't think that there was any sharing of information. I'm not sure though; I didn't completely go through both threads.


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Sat Nov 09, 2013 5:13 pm 
Offline
User avatar

Joined: Mon Apr 20, 2009 5:24 am
I just read that speedsolving topic, and I thought the solution with 24 removed stickers and 2 solvable color schemes is actually really cool. It certainly wasn't too hard to solve though, compared to the various prototypes I made and tested on the virtual cube.

Yes, the corner solution I thought I had really had a 5-cycle lurking in there...ironic

But I found a way to easily determine whether extra solutions exist or not: number the cubies, write the numbers down in a circle, and draw arrows whenever a piece can take the place of another - but the pieces doesn't necessarily have to swap with one another. Any complete cycle in the picture means the numbered cubies can cycle with one another in that way.

Here's a solution with 14 removed corner stickers that passes the drawing test (with only 1 swap possible) and worked out every time I solved it in the virtual simulator.

Image

Its modified from the 13-sticker solution posted earlier.

I then removed the edge stickers and center stickers according to my previous plans, adjusting the orientation of each set to make each face have the same number of stickers and to increase difficulty.

Image

Interestingly, this scheme can solved into something that looks almost exactly like its mirror reflection, color scheme and all. Only 1 face was not reflected; it was rotated 180 degrees instead. I see that color schemes are not too hard to change after all!

_________________
I'm going to try learning puzzle design!
*10 years later...*
Yes! I made a sphere! Now, what was step 2 again?


Last edited by JubilantJD on Sat Nov 09, 2013 5:40 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Sat Nov 09, 2013 5:28 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
JubilantJD wrote:
But I found a way to easily determine whether extra solution exist or not: number the cubies, write the numbers down in a circle, and draw arrows whenever a piece can take the place of another - but the pieces doesn't necessarily have to swap with one another. Any complete cycle in the picture means the numbered cubies can cycle with one another in that way.

This ignores parity. If there is an odd-cycle in one piece type, there need to also be an odd-cycle in the other piece type otherwise the parity restriction of the edges+corners would prevent using the cycle.

You also need to account for pairs of odd-cycles in one piece type because that keeps the permutation parity the same. So for example two 2-cycles in the edges would allow for a 2-2 swap which doesn't need to affect corners.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Sat Nov 09, 2013 5:36 pm 
Offline
User avatar

Joined: Mon Apr 20, 2009 5:24 am
Yeah, that's how I checked my states. I intended my corners to only have one even permutation available, because the edges must also be messed up to make that permutation. And since my edges are visibly wrong when messed up at all, the one even permutation cannot make another solution.

What I didn't know is that there can also be orientation blocking. My edges have a 3-cycle available, but using it and orienting them to looked solved will make the cube unsolvable with OLL parity. I don't know how that works.

_________________
I'm going to try learning puzzle design!
*10 years later...*
Yes! I made a sphere! Now, what was step 2 again?


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Sat Nov 09, 2013 5:45 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
JubilantJD wrote:
What I didn't know is that there can also be orientation blocking. My edges have a 3-cycle available, but using it and orienting them to looked solved will make the cube unsolvable with OLL parity. I don't know how that works.
Yep you'll have to make sure that you track the total twist of each cycle to and then only choose cycles such that the total twist modulo 3 is 0.

I'm pretty sure all of this is basically the same as using the Stabilizer() function in GAP and then asking GAP what the size of the group is.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: How many stickers does a cube need?
PostPosted: Sat Nov 09, 2013 6:05 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Thinking about your proposal more... This will only check if there is a unique solution for a given color scheme. It can't find alternative colors schemes. This is the same problem Taus had with his GAP code.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 14 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Google [Bot] and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group