# How many of those 43 quintillion+ cases are 'scrambles'?



## IamWEB (Dec 4, 2009)

This idea suddenly came to my mind, but I have no idea how to figure it out. If anyone else that can would like to, be my guest.

How many of those total positions the 3x3x3 can be in have no F2L pairs done (for any color, and then how many just for 1 cross?), no more than 2 cross pieces correctly done (for any color, and then how many for 1 cross?), and things like that?

I'm curious about how this turns out. Even if I don't understand, seeing how finding the answer is achieved would be nice.

Anyone else care to know this?


----------



## cmhardw (Dec 4, 2009)

If you aren't using computers, you could use inclusion-exclusion for finding a count of no pairs done. It would get tricky when looking at how many possible ways can four or more pairs be made, but it must surely be possible still with only pencil and paper. I'm actually interested to try this and see if I can come up with the same answer as those who will inevitably solve this problem much more quickly than I can 

--edit--
This might be harder than I thought, because as you start to build 3x1x1 blocks, do you consider this a single pair, or two pairs built at once? What happens when a 3x1x1 shares a corner with a different 3x1x1 block?

Hmm..... This is an interesting problem. I'll have to give this a think.

Chris


----------



## Ranzha (Dec 4, 2009)

I'm going to figure this out....
ARGH....


----------



## IamWEB (Dec 4, 2009)

cmhardw said:


> If you aren't using computers, you could use inclusion-exclusion for finding a count of no pairs done. It would get tricky when looking at how many possible ways can four or more pairs be made, but it must surely be possible still with only pencil and paper. I'm actually interested to try this and see if I can come up with the same answer as those who will inevitably solve this problem much more quickly than I can
> 
> --edit--
> This might be harder than I thought, because as you start to build 3x1x1 blocks, do you consider this a single pair, or two pairs built at once? What happens when a 3x1x1 shares a corner with a different 3x1x1 block?
> ...



I would just exclude all blocks, regardless of how many pairs they count as. 1 pair at all and it's excluded.


----------



## cmhardw (Dec 4, 2009)

IamWEB said:


> cmhardw said:
> 
> 
> > --edit--
> ...



Actually it's not really *that* weird to think this way. A solved cube is essentially 6 F2L's, each consisting of 4 corner/edge pairs. So a solved cube has 24 corner/edge pairs built. A 3x1x1 is always considered as a corner/edge pair built on two opposite corner colors with the same edge, so it's just two corner/edge pairs.

Yes inclusion/exclusion should work just fine as a method to figure out the answer to how many scrambled states have no pairs built. Actually applying it will be very tedious (but also interesting!), but not necessarily extremely difficult.

Chris


----------



## daniel0731ex (Dec 4, 2009)

just exclude plls, ll, f2l, and cross and you are left with the scrambles


----------



## rubiknewbie (Dec 4, 2009)

Quite close to 43 quintillion I guess.


----------



## miniGOINGS (Dec 4, 2009)

rubiknewbie said:


> Quite close to 43 quintillion *I guess*.



Ahem. Although that may be right, I think you should try to figure it out, just so you can prove yourself wrong.


----------



## cmhardw (Dec 4, 2009)

Ok I had a chance to look at it, and although I still think inclusion/exclusion is a viable way to count the number of ways that no corner/edge pair is built, I am getting confused of the setup for the count.

Here are my thoughts so far:
I think it will be easiest to consider corners, and how many of them match with their edges. For example, I would start with the total number of cube states on the cube: 43,252,003,274,489,856,000

Then you will subtract the number of ways that 1 corner can match with exactly one of it's edges (permuting/orienting all other pieces randomly).

From here it gets confusing for me. I am thinking that you adjust the previous overcount by adding back the number of ways that 2 distinct corners can match exactly one of their respective edges. The problem is, where in the count do we consider cases where 1 corner matches exactly two of it's edges? How do we adjust the inclusion exclusion case counting structure to consider such cases? Also, the problem grows more complex when you think about having 4 corners match exactly one of their respective edges, or maybe 2 corners than each match exactly two of their respective edges.

This is an extremely interesting problem! Is there any way this can be done elegantly with pencil and paper, or is it likely that a computer analysis is required here?

Chris


----------



## Tim Major (Dec 4, 2009)

miniGOINGS said:


> rubiknewbie said:
> 
> 
> > Quite close to 43 quintillion *I guess*.
> ...



I am guessing it is nowhere near 43 quintillion. By scrambled, do mean, a non-cuber would say it "looks scrambled" like, has no big blocks, or do you mean any cases that aren't solved. What would happen in a competition, if it turned out a scramble solved itself. Or had the first 2 layers solved? What would be the chances of this? I wish there were more threads like this, as they are the type of thread I like, instead of "do you think an avatar says something about the poster", or whatever that thread was. These are interesting, and I wish there was a cubing site I new of, that just discussed Rubik's cube theory, instead of that type of stupid thread. 
Btw, if you mean scrambled, as in "not solved" then yes, it would be very close to 43 quintillion.


----------



## cmhardw (Dec 4, 2009)

ZB_FTW!!! said:


> I am guessing it is nowhere near 43 quintillion. By scrambled, do mean, a non-cuber would say it "looks scrambled" like, has no big blocks, or do you mean any cases that aren't solved.



I am interpreting it as the following problem: How many possible positions are there where no corner on the cube matches correctly with any of its three adjacent edges?

Chris


----------



## DavidWoner (Dec 4, 2009)

cmhardw said:


> ZB_FTW!!! said:
> 
> 
> > I am guessing it is nowhere near 43 quintillion. By scrambled, do mean, a non-cuber would say it "looks scrambled" like, has no big blocks, or do you mean any cases that aren't solved.
> ...



And also have no corners or edges that are both permuted and oriented.


----------



## Cangurino (Dec 4, 2009)

DavidWoner said:


> And also have no corners or edges that are both permuted and oriented.



It should be possible to figure out this part by itself. For the edge/corner matchups I have no idea yet.


----------



## Tim Major (Dec 4, 2009)

That sounds like quite a small fraction. No pairs, and no edges/corners in the correct position. I am guessing less than half. Still, I'm not going to spend awhile thinking about it, though I may later when I'm off the computer.


----------



## nigtv (Dec 4, 2009)

Cangurino said:


> DavidWoner said:
> 
> 
> > And also have no corners or edges that are both permuted and oriented.
> ...


That's what I'm thinking. I think I'll try to figure this out in my head before thinking of any of that other stuff...:confused:


----------



## LNZ (Dec 4, 2009)

By definition, any state of the 3x3x3 cube that is not the solved state is called a scrambled state, regardless of how much it is scrambled. 

This is important when working out god's algorithm for any puzzle toy.

The solved state is defined by a 3x3x3 that needs no face turns to solve.

To see this, look and solve a 1x1x1 cube. It needs no face rurns to solve and has therfore only 1 possible state, which is the solved state.


----------



## IamWEB (Dec 4, 2009)

What I said (or meant if there was confusion) was referring to cases that:

Have no corner/edge pairs done and have no more than 2 edges correctly oriented and permuted for one layer (i.e. not an easy cross for that color).

I think the latter part will be harder to do...


----------



## AvGalen (Dec 4, 2009)

IamWEB said:


> What I said (or meant if there was confusion) was referring to cases that:
> 
> Have no corner/edge pairs done and have no more than 2 edges correctly oriented and permuted for one layer (i.e. not an easy cross for that color).
> 
> I think the latter part will be harder to do...


Your definition is really weird. I have had many scrambles had have a corner edge pair connected. Sometimes it is even done.

Your second situation of having 2 cross pieces already oriented and permuted (i.e. white-red and white-orange opposite on the white layer) or completely done (i.e. white-red edge and white-orange edge entirely solved) happens quite often and is a great help when you EO-line or cross. Especially when color neutral. But having two edges solved doesn't mean solving cross is always short, it just means an easier inspection so you can probably plan further than just the cross (x-cross?)


----------



## Stefan (Dec 4, 2009)

An estimation for "How many states have no matched corner-edge pairs":

Edges alone are harmless. So all edge states are possible. Then each corner has 3 bad spots out of 24, where it would match an edge (or 1 or 2 bad spots, but not often). So a probability of 21/24 that the corner is at a good spot. And (21/24)^8 is about 34%. This individual treatment of pieces/pairs doesn't provide an accurate answer, but I think it gets close. So I estimate 34% of all cases to have no matched corner-edge pairs.

Edit: Reversing the roles of corners and edges leads to (22/24)^12, about 35%.


----------



## cmhardw (Dec 4, 2009)

StefanPochmann said:


> An estimation for "How many states have no matched corner-edge pairs":
> 
> Edges alone are harmless. So all edge states are possible. Then each corner has 3 bad spots out of 24, where it would match an edge (or 1 or 2 bad spots, but not often). So a probability of 21/24 that the corner is at a good spot. And (21/24)^8 is about 34%. This individual treatment of pieces/pairs doesn't provide an accurate answer, but I think it gets close. So I estimate 34% of all cases to have no matched corner-edge pairs.
> 
> Edit: Reversing the roles of corners and edges leads to (22/24)^12, about 35%.



Stefan, I use an extremely similar approach to estimating the expected number of solved x-centers and t-centers on 5x5x5 after the scramble for BLD (assuming you don't optimize an orientation and solve center points after). We've found it to be fairly accurate in practice, so I think your estimation is probably fairly accurate.

Any ideas on how to set up an inclusion-exclusion case structure/strategy/approach to figure out the exact count? If this would be too tedious to be practical, is there a way computers can aid in finding this count?

I think this question (# of cases with no corner edge pairs built) is a simple to pose question, but a challenging concept to apply!

Chris


----------



## Anthony (Dec 4, 2009)

ZB_FTW!!! said:


> miniGOINGS said:
> 
> 
> > rubiknewbie said:
> ...




You're off by two hundred fifty-two quadrillion, three trillion, two hundred seventy-four billion, four hundred eighty-nine million, eight hundred fifty-five thousand, nine hundred ninety-nine.


----------



## hawkmp4 (Dec 4, 2009)

Yes, you're correct. But when talking about the cube, especially here, I think it's safe to say 43 quintillion is understood to be all the possible states of the cube.


----------



## miniGOINGS (Dec 4, 2009)

Anthony said:


> ZB_FTW!!! said:
> 
> 
> > Btw, if you mean scrambled, as in "not solved" then yes, it would be very close to 43 quintillion.
> ...


----------



## Cangurino (Dec 5, 2009)

A quick probabilistic simulation shows that 56% of all states have no piece in the right spot and oriented correctly.


----------



## Lucas Garron (Dec 6, 2009)

Cangurino said:


> A quick probabilistic simulation shows that 56% of all states have no piece in the right spot and oriented correctly.



Really?

A quick mathematical calculation shows me ≈0.606 for edges, and ≈0.513 for corners, about 0.311 together.


----------



## Stefan (Dec 6, 2009)

Lucas Garron said:


> Cangurino said:
> 
> 
> > A quick probabilistic simulation shows that *56%* of all states have no piece in the right spot and oriented correctly.
> ...


And I estimate (23/24)^20 ≈ *42.7%*.


----------



## meichenl (Dec 6, 2009)

The expected value of the number of corner/edge pairs in a random position (counting a 3x1x1 block as two pairs) is exactly one. This is because any of the 24 possible pairs has a chance 1/24 of occurring in a random scramble. Focusing, for definiteness, on the red/blue/white corner and red/blue edge, once the corner is placed, there is a 1/12 chance that the edge will go in the right slot to make a pair, and a 1/2 chance that once there, it will have the correct orientation.

So, if we sample _n_ random cubes, then each corner edge pair will appear in roughly _n/24_ of them, and since there are 24 possible pairs, the expected number of corner/edge pairs is exactly one.

We can use this calculation to confirm Stefan's estimate earlier in the thread for the number of positions with no corner/edge pairs. If the corner/edge pairings were independent, the odds of no corner edge pairs would be

(23/24)^24 = .360,

which is not far from 1/e = lim n->inf [(n-1)/n]^n = .367

One way to calculate the exact number by hand, which would be rather tedious, is what Chris already suggested.

The number of positions with no corner/edge pairs is the total number of positions minus the number with at least one corner edge pair.

For a given corner edge pair, there are 1802166803103744000 positions that contain it (1/24 of the possible positions). Multiplying by 24, we get the 43 quintillion cases with at least one pair, except that we've double-counted anything that has two pairs, and triple counted anything with three pairs, etc.

So we need to find how many positions have two pairs. We could do this by breaking it down into three cases:


the two pairs have two corners and two edges
the two pairs have two corners and one edge
the two pairs have one corner and two edges

For each of these, it is not too difficult to count the total possibilities. For example, for two corners and one edge, we first note there are twelve such pairings. Each pairing has six free corners and eleven free edges, making
12*6!*11!/2*2^10*3^5 total such positions.

We could continue for the other cases. But in doing this, we triple count positions with three pairs, and 6-fold count positions with four pairs, etc.

So we'd have to count the number of ways to make three pairs, which involves analyzing more topologies, such as three corners three edges, three corners two edges, two corners three edges, etc. 

Eventually, we could analyze everything all the way out to 24 pairs, and cascade our way back.

This sounds tedious enough that I'm not interested in doing it, and makes me think there is probably a better, more clever method possible.


----------



## Lucas Garron (Dec 6, 2009)

StefanPochmann said:


> Lucas Garron said:
> 
> 
> > Cangurino said:
> ...


And *my* quick simulation agrees with Stefan (and so does my brain; I really wasn't expecting my code to work - I was mostly saying I can throw out an unsubstantiated answer easily, too). Cangurino, are you sure you didn't forget to complement your answer?






(Shoulda used KroeneckerDelta, but meh.)


----------



## krazedkat (Dec 6, 2009)

first you must exclude the solved states...


----------



## Muesli (Dec 6, 2009)

krazedkat said:


> first you must exclude the solved states...


You mean all 1?


----------



## Tomk (Dec 7, 2009)

Musli4brekkies said:


> krazedkat said:
> 
> 
> > first you must exclude the solved states...
> ...



Sure, if you look at it closely it has a high percentage impact on the outcome...


----------



## Kirjava (Dec 7, 2009)

Odd definition of 'scramble' you guys have here.


----------



## Yes We Can! (Dec 7, 2009)

daniel0731ex said:


> just exclude plls, ll, f2l, and cross and you are left with the scrambles



Wrong. Just take the center switching alg.


----------



## IamWEB (Dec 9, 2009)

Kirjava said:


> Odd definition of 'scramble' you guys have here.



This isn't based on anyone's perception of the word, but it seemed like a fitting term to use in the title to keep the title a good size.


----------



## JLarsen (Dec 9, 2009)

Scrambles with no corner edge pairs are quite rare for me. I think as a block builder I would notice them more often than cross solvers. If I were to guess I'd say no CE pair scrambles come around maybe 20-30% of the time. Might I point out that no CE scrambles are some of the hardest to solve (longest solutions), and that scrambles with 3 or more CE pairs I'd most likely still call scrambled?


----------



## Cyrus C. (Dec 22, 2009)

chris410 said:


> I stumbled upon this link:
> 
> http://eklhad.net/rubik/enumerat.html
> 
> I confess, I have not reviewed it to check the accuracy but from a quick glance it appears to be a good start.



I think that is talking about positions, not scrambles.


----------



## Stefan (Dec 22, 2009)

chris410 said:


> correct, the article discusses positions. As far as scrambles are concerned, the final number would be dependent on both the length of the scrambles along with the boundaries of turns per movement.


Please actually read this thread, or at least the first post?


----------



## chris410 (Dec 30, 2009)

StefanPochmann said:


> chris410 said:
> 
> 
> > correct, the article discusses positions. As far as scrambles are concerned, the final number would be dependent on both the length of the scrambles along with the boundaries of turns per movement.
> ...



Apologies! (posts removed)


----------

