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

TwistyPuzzles.com Forum

It is currently Thu Apr 24, 2014 10:09 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 22 posts ] 
Author Message
 Post subject: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 3:41 am 
Offline
User avatar

Joined: Tue Sep 08, 2009 8:41 am
Location: The Blue Mountains, Australia
You're playing with a 3x3x3 and a white sticker falls off the red and white edge piece, no biggie, it's the only one so the colour of this sticker can be inferred from the others.

Your lose three non-opposite centre stickers, again the colour scheme can be inferred from a corner piece.

You lose two stickers off a corner leaving just a white sticker and two stickers of a corner now containing just a yellow sticker. Again, both position and orientation of both corners can still be found.

You lose another sticker off the same white red edge, surely now this edge with no visible orientation can be placed in two different ways... but actually for all other edge pieces to be in the correct orientation this edge also has to be due to limitations on the cube itself (one flipped edge is impossible).

I'd say you can see where I'm going with this. How many stickers can peel off before there are multiple solved states with only one colour on each face, before a missing sticker can't be inferred AND in what combination can you lose the most? There's the obvious losing all 9 from one side and having a blank side but it can be taken further. Just glancing at a cube and imagining I'm pretty sure I can get to 19 stickers gone with no change... surely it can be taken further?

This forum has it's fair share of intelligent people. So who can solve this puzzle, about a puzzle, on a forum for puzzle solvers? It'd be nice to see it done mathematically but I study chemistry, I'm not the best mathematician.

For those curious (and to see if I have made a mistake) my 19 is (on a standard colour scheme cube) all the white side (9), the red off the 'white' red edge (10), the green and orange centres (12), the orange off the BOY corner (13) and the red off the BYR corner (14), the blue off the blue yellow edge (15) and all three stickers off the RYG corner (18) (can't have one twisted corner) and the blue sticker off what would have been the BWO corner (19).

Have a proper think about it and all the missing stickers don't affect the final solution (done just in my head, I could have missed something). If I'm right that's 1/3 of the stickers at least that are redundant... I think that's pretty interesting.

It's not often a subject about the regular 3x3x3 hasn't been discussed on here at some point so I suppose this might have had a thread before, but I couldn't find it. I hope I've managed to make some of you think about something new regarding the original Rubik's Cube, if I have I'll be happy (even if my 19 stickers solution has a mistake...).

_________________
Some PBs
3x3x3 :20.7 seconds, 5x5x5 2:33, gigaminx 16:40, 7x7x7 9:48, pyraminx crystal 3:42


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 6:27 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
I can't remember about a topic like this.

I looked at one of my 3x3x3 and I think that you can peel of the RED face as well.


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 7:52 am 
Offline
User avatar

Joined: Tue Sep 08, 2009 8:41 am
Location: The Blue Mountains, Australia
Hmmm, I assume you mean the RED centre sticker and I think you might be right there. It's difficult to delve this far into something using just your thoughts though. So, if there's no mistakes so far that makes it 20 redundant stickers. It would be nice to find a method for working this out properly.

A simpler but similar question is how FEW peeled stickers it takes until a missing sticker can't be inferred, to which the answer I come up with is three. There might be more ways than one to do so with three stickers but the one I thought of is removing the red, orange and blue stickers form the RW, OW, and BW edges or any similar pattern, then these edges can be three cycled without any way to tell. I can't see any way of doing it with just two, there are a few using four.

_________________
Some PBs
3x3x3 :20.7 seconds, 5x5x5 2:33, gigaminx 16:40, 7x7x7 9:48, pyraminx crystal 3:42


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 9:20 am 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
I think I came up with 24 thanks to Elwyn's last comment about fewest stickers idea.

4 centers: You only need 2 stickers to determine the orientation of the core
8 corners: Each corner needs a max of 2 stickers to determine orientation.
2 corners: (building off of the previous step) You can have a few corners with only 1 sticker. Here's my idea to do it. For 3/4 white corners, remove the white sticker. For the 4th corner, remove all non-white corners. Repeat for the yellow stickers.
1 corner: Remove that last white sticker. You can have 1 corner with no stickers and it's twist is inferred from the puzzles total twist.
6 edges: You can easily remove one sticker per face color. The basic idea here is that you don't want to have 2 White-Blank edges.
1 edge: Because you can't swap just 2 edges, you can have 2 White-Blank edges.
2 edge: You can have one edge with no stickers and it's orientation can be inferred because you can't flip just 1 edge.

4+8+2+1+6+1+2 = 24

You might be able to take one more off the corners, but I'm worried that you might be able to swap the single colored corners + reorient and not tell the difference. This might not be a problem if the total twist restricts this or the pieces are far apart enough. This is my best idea for them. Parenthesis around removed stickers
(WBR)
(WG)R
(WB)O
Y(BR)
The rest of the piece have their white or yellow sticker removed. The yellow sticker corner can't exist in either of the other single sticker corners because those are white corners. The other 2 corners can't be swapped because they have opposite colors on them. This would bring my total to 25.

Just realized that the 0-sticker corner could still get swapped with any 1-sticker corner. So my arrangement doesn't work, but that doesn't convince me that one can't exist if you don't have a 0-sticker corner and have more 1-sticker corners.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 10:56 am 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
Just thought of a way to create an upper bound on this problem. As we all know, the cube has 43,252,003,274,489,856,000 possible states. If we convert this number to base six (one for each color), we get 13043352313200000000000000 which is 26 digits (hexigits?) long. This means we need a minimum of 26 stickers to identify a puzzle if we had a crazy computer that worked in base 6 instead of base 2. This requirement doesn't include the core orientation so that's another 2. So in total we need a minimum of 28 stickers. This makes the upper bound for redundant stickers = 9*6 - 28 = 26. Makes my 24 solution look pretty good.

I think my Math is pretty solid here, but I'm starting to doubt that this is a 100% valid way to do it since the blank stickers do add some information.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 12:01 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I'm not 100% convinced that your 24 is a valid solution but I don't have the time right now to fully think it through.

I agree blank stickers do add information. Doesn't that mean we should use base 7?

I get:

? log(43252003274489856000)/log(7)
%1 = 23.235181360574805571918494765075898953

I'm sure we can answer this.

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


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 12:38 pm 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Yes, not having stickers on a face does add information but not enough to be working in base 7. If you did that, you'd find that x stickers are required to sticker it uniquely, but that x includes some blank stickers which are indistinguishable from the other 56-x blank stickers.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 1:12 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
Yeah, I guess base 7 would be a better upper bound than 6. It won't be a tight upper bound, but is it is one.

GuiltyBystander wrote:
2 edge: You can have one edge with no stickers and it's orientation can be inferred because you can't flip just 1 edge.
Just realized that the blank edge could get swapped with some single sticker edges unless you do something super special. This would bring my redundant sticker estimate down to 22.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 1:16 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
I don't have time to really think about this at the moment, but I just wanted to say, nice puzzle!


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 1:19 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
So what are the criteria for removing stickers? If we hand a minimally stickered cube to somebody are they supposed to be able to unambiguously determine the color of all of the missing stickers without prior knowledge of how they were removed? That seems reasonable but it won't give us the minimum.

When we do log(perms)/log(6 or 7) that is telling us the absolute minimum number of stickers needed to encode all of the permutations and I'd argue that it breaks the above criteria. I'm having trouble articulating why but I think it comes down to this. Suppose you had a 2x2x2 and all the corners had stickers except that the white-red-blue only had the white sticker and white-red-green corner only had the red sticker. Without prior knowledge of which stickers were removed a human wouldn't be able to determine which solved state is the correct one but you will still be able to unambiguously define all states. You can "see the difference" between the white-only corner and the red-only corner even though you don't know which one they are anymore.

Simplifying the problem to only the corners of a cube for now, you can sticker them this way:

wgr -> <blank>
wrb -> w
wbo -> b
wog -> o
ygr -> g
yrb -> r
ybo -> y
yog -> yo

All permutations of the corners are still uniquely defined.

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


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 2:22 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Thinking about log(perm)/log(6 or 7) more, I think a certain amount of information is encoded spatially in where you choose to place the stickers.

That is, even if the formula tells us we need to use 24 stickers, there are 54 spots and a blank does convey some information. There are 1402659561581460 ways to place 24 stickers in 54 spots (this number ignores symmetries).

I think this makes log(perm)/log(6 or 7) only a reasonable approximation. A "fuzzy bound".

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


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 19, 2011 10:56 pm 
Offline
User avatar

Joined: Tue Sep 08, 2009 8:41 am
Location: The Blue Mountains, Australia
How many stickers it takes to be able to represent all possible states, while interesting, isn't what I was really asking about and I'd say isn't quite as interesting as how few can be used to know what every missing sticker should be (assuming the person looking has a good knowledge of the cube).

That said simplifying to a 2x2x2 first would be interesting, the configuration you stated is for representing all states but what is the minimum number for being able to identify every missing sticker?

(Also, Hi Brandon. It's been a long while between discussions)

bhearn wrote:
I don't have time to really think about this at the moment, but I just wanted to say, nice puzzle!
I thought so myself, I'm surprised more people haven't discussed it before.

I hope we get an answer. I might even be tempted to make such a cube. Solving it the first time, especially if someone else had done the removal of the stickers and then scrambled it, might be rather fun.

_________________
Some PBs
3x3x3 :20.7 seconds, 5x5x5 2:33, gigaminx 16:40, 7x7x7 9:48, pyraminx crystal 3:42


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Tue Dec 20, 2011 7:24 pm 
Offline
User avatar

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
Cool idea!

I did a bit of preliminary calculation with GAP and found that it is possible to remove 13 stickers and still be able to return a scrambled 2x2x2 cube to its (unique) solved position. Also, this does not presuppose knowledge of which stickers were removed.

The stickers to be removed are the following.
  • Every sticker on the three faces surrounding a corner (e.g. all red, blue and white stickers).
  • A single sticker from the corner opposite the now fully unstickered corner (e.g. the yellow sticker from the orange-green-yellow corner)

If my calculations are correct, there should be a unique solution to this cube.

This is a maximal solution (i.e. no further stickers can be removed), but not necessarily the best possible.

Alas, it is somewhat lopsided removal of stickers. For it to be a good puzzle, it would be better if the stickers were removed in equal numbers on each face.

--Taus


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Tue Dec 20, 2011 8:25 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Hi Taus,

Did you use some particular trick to choose the 13 stickers or did you brute force the 24 choose N for N in [0 .. 24]? That's 2^24 choices. Even just 24 choose 13 is 2496144 possibilities. Does GAP have some feature that helps with this?

If you can't tackle the full 3x3x3 it should be enough to now tackle the edges alone and because there are no ambiguities in the stickering of the corners you can allow for two duplicate solved states in the 3x3x3 edges (the parity of the corners and edges are connected which means the corners will restrict this to only one solved state).

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


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Wed Dec 21, 2011 10:44 am 
Offline
User avatar

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
bmenrigh wrote:
Did you use some particular trick to choose the 13 stickers or did you brute force the 24 choose N for N in [0 .. 24]? That's 2^24 choices. Even just 24 choose 13 is 2496144 possibilities. Does GAP have some feature that helps with this?

No particular trick -- just fiddling around with removing virtual stickers from a representation of the 2x2x2 in GAP. Here's how I did it:

The definition of a 2x2x2 cube is straightforward. I define it by a single face turn and all the rotations of the cube:

Code:
#       +-----+
#       | 1  2|
#       |     |
#       | 3  4|
# +-----+-----+-----+-----+
# | 5  6| 9 10|13 14|17 18|
# |     |     |     |     |           
# | 7  8|11 12|15 16|19 20|
# +-----+-----+-----+-----+
#       |21 22|
#       |     |
#       |23 24|
#       +-----+

cube2 := Group((9,10,12,11)(3,13,22,8)(4,15,21,6),
               (9,10,12,11)(3,13,22,8)(4,15,21,6)(1,14,24,7)(2,16,23,5)(18,17,19,20),
               (5,9,13,17)(6,10,14,18)(7,11,15,19)(8,12,16,20)(1,3,4,2)(21,22,24,23));;

Next we want to list the facelets we want to consider to be equally stickered. We may think of unstickered facelets as being stickered with a new colour. In our case, it's facelets 1 through 12 and, say, 19:
Code:
cube2faces := [[1,2,3,4,5,6,7,8,9,10,11,12,19],[13,14,15,16],[17,18,20],[21,22,23,24]];;

To see whether the solution with this stickering is still unique, we calculate the subgroup of permutations that stabilize the above list when considered to be a tuple of sets. In other words, permutations p such that p applied to, say, the set {13,14,15,16} results in the same set. Thus, we are allowed to swap two equally coloured stickers (e.g. 13 and 14) but not differently coloured ones (e.g. 13 and 1).

This can be done using the Stabilizer command:
Code:
gap> Stabilizer(cube2,cube2faces,OnTuplesSets);
Group(())

As the only element in this group is the identity permutation, we can conclude that there is only only one solution with this combination of stickers.

To see an example of the output when the solution is not unique, consider unstickering sticker number 16:
Code:
gap> Stabilizer(cube2,[[1,2,3,4,5,6,7,8,9,10,11,12,16,19],[13,14,15],[17,18,20],[21,22,23,24]],OnTuplesSets);   
Group([ (8,16)(11,19)(21,24) ])

In this case, we see that there are two solutions, as we can swap the (8,11,21) corner with the (16,19,24) corner without changing the appearance of the cube.

With regard to brute-forcing, I believe the search space is quite a bit smaller than 2^24. This is because the function we're trying to maximize is "monotonic" in a suitable sense. This follows from the observation that adding a sticker can never increase the number of solutions. Thus, if we look at the stickers in sequence and decide on whether to add them or not, we only need to backtrack to points where we removed a sticker and never to points where we let a sticker remain.

Another way of seeing this is to consider the following: We can get multiple solutions by removing just four stickers (two from each of two corners that share a face). No matter how we choose to remove or keep the remaining 20 stickers, we will still have multiple solutions, hence we can disregard the 2^20 possibilities of stickering the rest of the cube, as no possible stickering will make the solution unique again.

Quote:
If you can't tackle the full 3x3x3 it should be enough to now tackle the edges alone and because there are no ambiguities in the stickering of the corners you can allow for two duplicate solved states in the 3x3x3 edges (the parity of the corners and edges are connected which means the corners will restrict this to only one solved state).


I'll try to get some semi-clever brute force running when I get home and try to apply it to the 2x2x2. If this is sufficiently fast, I might try it on the 3x3x3.

--Taus


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Wed Dec 21, 2011 11:11 am 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
Taus wrote:
[...gap stuff...]
Cool stuff. I'm worried that it might not detect another kind of problem with removing stickers. If we remove too many stickers, it could be possible to solve the cube with a different color scheme than what we started with. I can't think of any trivial example at the moment, but I have a gut feeling that one has to exist.

Can you detect this problem or do you (anyone, not just Taus) think that any sticker set that can fit multiple color schemes would also fail the normal conditions.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Thu Dec 22, 2011 6:03 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
@Taus: Very clever.
I am excited about the result.


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Sun Dec 25, 2011 6:17 pm 
Offline
User avatar

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
Okay, time for some results. I managed to brute-force my way through all (relevant) possibilities of stickering the 2x2x2. My program found a solution with 16 stickers removed (i.e. 8 stickers remaining) and no solutions with 17 stickers removed. The solution is as follows:

Code:
      +-----+
      |     |
      |     |
      |    4|
+-----+-----+-----+-----+
|     |     |   14|   18|
|     |     |     |     |           
|    8|   12|     |   20|
+-----+-----+-----+-----+
      |     |
      |     |
      |23 24|
      +-----+

[ [ 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 15, 16, 17, 19, 21, 22 ], [ 4 ], [ 8 ], [ 12 ], [ 14 ], [ 18, 20 ], [ 23, 24 ] ]


Note that this highlights the fact that, as GuiltyBystander noted, this only guarantees a unique solution when the actual colour scheme is known in advance. For instance, we can permute the corner cubelets containing 4, 8 and 12 and still have an apparently correct solution. I am not entirely sure how to detect this situation. Clearly, one can argue intuitively as I just did to see that the above solution is not unique in this sense, but I don't know how to do this rigourously (and programmatically).

For completeness sake, here is the full output from my program:
Code:
gap> FindMaxRemoved(cube2,cube2faces);                               
Max 1 at 2 steps, time 0:00:00.015 with: [ [ 1 ], [ 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 2 at 3 steps, time 0:00:00.025 with: [ [ 1, 2 ], [ 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 3 at 4 steps, time 0:00:00.030 with: [ [ 1, 2, 3 ], [ 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 4 at 5 steps, time 0:00:00.038 with: [ [ 1, 2, 3, 4 ], [  ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 5 at 6 steps, time 0:00:00.043 with: [ [ 1, 2, 3, 4, 5 ], [  ], [ 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 6 at 7 steps, time 0:00:00.049 with: [ [ 1, 2, 3, 4, 5, 6 ], [  ], [ 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 7 at 8 steps, time 0:00:00.057 with: [ [ 1, 2, 3, 4, 5, 6, 7 ], [  ], [ 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 8 at 9 steps, time 0:00:00.061 with: [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], [  ], [  ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 9 at 10 steps, time 0:00:00.064 with: [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [  ], [  ], [ 10, 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 10 at 11 steps, time 0:00:00.070 with: [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ], [  ], [  ], [ 11, 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 11 at 12 steps, time 0:00:00.078 with: [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ], [  ], [  ], [ 12 ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 12 at 13 steps, time 0:00:00.083 with: [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ], [  ], [  ], [  ], [ 13, 14, 15, 16 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 13 at 20 steps, time 0:00:00.121 with: [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 16 ], [  ], [  ], [  ], [ 13, 14, 15 ], [ 17, 18, 19, 20 ], [ 21, 22, 23, 24 ] ]
Max 14 at 70 steps, time 0:00:00.388 with: [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15, 16, 22 ], [  ], [  ], [ 12 ], [ 13, 14 ], [ 17, 18, 19, 20 ], [ 21, 23, 24 ] ]
Max 15 at 2258 steps, time 0:00:12.576 with: [ [ 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 15, 16, 19, 21, 22 ], [  ], [ 8 ], [ 12 ], [ 13, 14 ], [ 17, 18, 20 ], [ 23, 24 ] ]
Max 16 at 25135 steps, time 0:02:25.516 with: [ [ 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 15, 16, 17, 19, 21, 22 ], [ 4 ], [ 8 ], [ 12 ], [ 14 ], [ 18, 20 ], [ 23, 24 ] ]
Completed search after 87340 steps. Elapsed time: 0:08:21.974

Here, every "step" is testing whether the stabilizer is empty (as mentioned in my previous post). In this case, we can get away with testing 87340 out of the 2^24 possibilities.

I also tried doing this for the edges and centers of the 3x3x3, and have a partial result for this. First, the definitions of the relevant groups:
Code:
         +--------+
         | 1  2  3|
         |        |
         | 4  5  6|
         |        |
         | 7  8  9|
+--------+--------+--------+--------+
|10 11 12|19 20 21|28 29 30|37 38 39|
|        |        |        |        |
|13 14 15|22 23 24|31 32 33|40 41 42|
|        |        |        |        |
|16 17 18|25 26 27|34 35 36|43 44 45|
+--------+--------+--------+--------+
         |46 47 48|
         |        |
         |49 50 51|
         |        |
         |52 53 54|
         +--------+


cube3 := Group((19,21,27,25)(20,24,26,22)(23)       # Face.
               (7,28,48,18)(8,31,47,15)(9,34,46,12),# Layer 1.
               (19,21,27,25)(20,24,26,22)(23)       # Face.
               (7,28,48,18)(8,31,47,15)(9,34,46,12) # Layer 1.
               (4,29,51,17)(5,32,50,14)(6,35,49,11) # Layer 2.
               (1,30,54,16)(2,33,53,13)(3,36,52,10) # Layer 3.
               (37,43,45,39)(38,40,44,42)(41),      # Face.
               (28,30,36,34)(29,33,35,31)(32)       # Face.
               (9,37,54,27)(6,40,51,24)(3,43,48,21) # Layer 1.
               (8,38,53,26)(5,41,50,23)(2,44,47,20) # Layer 2.
               (7,39,52,25)(4,42,49,22)(1,45,46,19) # Layer 3.
               (10,16,18,12)(11,13,17,15)(14)       # Face.
);
cube3faces := [[],[1..9],[10..18],[19..27],[28..36],[37..45],[46..54]];

edgecube3 := Group((20,24,26,22)(23)                # Face.
               (8,31,47,15),                        # Layer 1.
               (20,24,26,22)(23)                    # Face.
               (8,31,47,15)                         # Layer 1.
               (4,29,51,17)(5,32,50,14)(6,35,49,11) # Layer 2.
               (2,33,53,13)                         # Layer 3.
               (38,40,44,42)(41),                   # Face.
               (29,33,35,31)(32)                    # Face.
               (6,40,51,24)                         # Layer 1.
               (8,38,53,26)(5,41,50,23)(2,44,47,20) # Layer 2.
               (4,42,49,22)                         # Layer 3.
               (11,13,17,15)(14)                    # Face.
);
edgecube3faces := [[],[2,4,5,6,8],[11,13,14,15,17],[20,22,23,24,26],[29,31,32,33,35],[38,40,41,42,44],[47,49,50,51,53]];


With these definitions, I have found the following (current) maximum:
Code:
         +--------+
         |        |
         |        |
         |        |
         |        |
         |    8   |
+--------+--------+--------+--------+
|        |        |   29   |   38   |
|        |        |        |        |
|13      |22    24|31    33|40 41   |
|        |        |        |        |
|        |   26   |   35   |   44   |
+--------+--------+--------+--------+
         |   47   |
         |        |
         |49 50 51|
         |        |
         |   53   |
         +--------+

Max 12 at 6931 steps, time 0:03:06.079 with: [ [ 2, 4, 5, 6, 11, 14, 15, 17, 20, 23, 32, 42 ], [ 8 ], [ 13 ], [ 22, 24, 26 ], [ 29, 31, 33, 35 ], [ 38, 40, 41, 44 ],
  [ 47, 49, 50, 51, 53 ] ]

I strongly believe that this is the best possible, as the program has been searching for several hours now without finding any better solution. At the time of writing, it has performed more than 700,000 stabilizer tests searching for a solution with 13 removed stickers. Thus, it would appear that 12 is the maximum number of stickers that can be removed from the edges and centers.

Somewhat late in the game, I realized that by randomizing the order in which stickers are removed, I might stand a better chance of getting a good maximum. I tried this on the edges and centers cube, and it quickly found several solutions with 12 removed stickers but none with 13.

I have also tried the randomized algorithm on the full 3x3x3 cube, and the current maximum is 29 removed stickers, for instance the following configuration:
Code:
         +--------+
         |    2   |
         |        |
         | 4     6|
         |        |
         | 7     9|
+--------+--------+--------+--------+
|   11 12|   20   |      30|   38 39|
|        |        |        |        |
|13 14   |22      |31      |40 41 42|
|        |        |        |        |
|   17 18|      27|        |   44   |
+--------+--------+--------+--------+
         |   47   |
         |        |
         |        |
         |        |
         |52 53   |
         +--------+

Max 29 at 76 steps, time 0:00:05.188 with: [ [ 1, 3, 5, 8, 10, 15, 16, 19, 21, 23, 24, 25, 26, 28, 29, 32, 33, 34, 35, 36, 37, 43, 45, 46, 48, 49, 50, 51, 54 ], [ 2, 4, 6, 7, 9 ],
  [ 11, 12, 13, 14, 17, 18 ], [ 20, 22, 27 ], [ 30, 31 ], [ 38, 39, 40, 41, 42, 44 ], [ 47, 52, 53 ] ]


This is only 25 stickers on the cube in total. Note that the corners alone could be fixed using 8 stickers, and the edges and centers using 30-12=18 hence by simply combining these two solutions we would get 26 stickers. With edges, corners and centers at the same time, we can eliminate a single extra sticker. This is probably as good as it gets. The big question now is whether or not the above configuration is "unique" even without pre-knowledge of the colour scheme. I would love to get some input on this.


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Sun Dec 25, 2011 6:37 pm 
Offline
User avatar

Joined: Sat Mar 29, 2008 12:55 am
Location: WA, USA
It is not unique. Since there are only 2 center stickers, you must know the color scheme prior to solving.

_________________
"This is Pretty off-topic"

"You are actually more off topic than me, you mentioned something on topic in the Off Topic forum."

"You more so for discussing the on-topic "off-topic" topic in the off-topic forum."


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Mon Dec 26, 2011 9:00 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Taus wrote:
The big question now is whether or not the above configuration is "unique" even without pre-knowledge of the colour scheme. I would love to get some input on this.
To answer this I allowed myself to introduce Singmasters identifiers:
Code:
         U--------+
         |    2   |
         |        |
         | 4     6|
         |        |
         | 7     9|
L--------F--------R--------B--------+
|   11 12|   20   |      30|   38 39|
|        |        |        |        |
|13 14   |22      |31      |40 41 42|
|        |        |        |        |
|   17 18|      27|        |   44   |
+--------D--------+--------+--------+
         |   47   |
         |        |
         |        |
         |        |
         |52 53   |
         +--------+
This configuration is indeed not unique. You could exchange F and R:
Exchange 22 and 31
Exchange 20 with the totally unstickered edge
Perform a 3-cycle of corners: 27-30-UnstickeredCorner
Since there is one unstickered corner and edge orientations are irrelevant.

Similarly you can exchange R and D.
Similarly you can exchange U and D.
Similarly you can exchange F->D->R->F
There are at most threee additional "color schemes" possible but I haven't tested these.

Andreas


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Sun Jan 01, 2012 12:27 pm 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
I have just now tried applying that sample removed-stickers pattern to a physical 3x3, and have discovered that even without changing the color scheme, there is at least a second solution, because I managed to solve it with the following differences:

4-cycle corners: 39 --> blank corner --> 27 --> 18 --> 39
4-cycle edges: 31 --> blank edge --> 6 --> 20 --> 31
3-cycle edges: 22 --> 47 --> 17 --> 22

(the 3-cycle of edges doesn't stand-alone because it would require a single edge-flip in this case)

I am very interested to see what the actual answer to this question is though.


Top
 Profile  
 
 Post subject: Re: How many stickers are redundant?
PostPosted: Sat Jan 14, 2012 3:15 pm 
Offline
User avatar

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
Thank you Andreas and Daniel for your analyses! (Especially Daniel for
implementing the colour scheme on a physical cube).

As far as I can see, the stickering scheme I gave yields a unique
solution assuming one knows not just the colour scheme but also the
positions of the stickered facelets on each face of the cube. This is
of course not quite as spectacular as I had hoped. It does, however, give a
plausible upper bound on the number of stickers that can be removed.

I think the main problem with trying to find a nice group-theoretical
way of checking if a given stickering has a unique solution is that
the relation that governs which cubelets can be swapped (without
changing the appearance of the cube) is not well-behaved. For
instance, a white+unstickered edge piece can stand in for both a
white+red edge and a white+green edge, but swapping white+red
with white+green will definitely change the appearance of the
cube. Thus, the "swapping relation" is not transitive, and this really
mucks up the possibility of using the predefined procedures in GAP.

Unfortunately, I have very little time to investigate this further. If
anyone is interested in the my code, I can add it to the GAP thread.


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

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 5 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