Sunday, April 14, 2013

What the _heck_ did I just say? Or, All Your Combinations Belong to Us

So, I'm at the bank the other day, and another person tells me "A Rubik's Cube? I haven't seen one of those for a while." Between all the 80's specials on TV, that Will Smith movie, and the fact that cubers can warrant coverage on NPR now, I'm not sure if people really mean that when they say it or if they're attempting to make conversation. Having recently re-read Penn & Teller's How To Play With Your Food, I explain my situation with the cube to the guy at the bank much like Penn Jillette explains the concept and inherent risks and rewards of a person being associated with a specific thing. The example Mr. Jillette gives in the introduction of the book is of a person that shows up at the local tourist hangout with a parrot all the time subsequently being referred to as "the Parrot Guy". I explain to the guy at the bank that sometimes if I forget to bring a cube with me, the only question I am likely to be asked is where my cube is. (I decided to skip the part about not being recognized at my high school reunion by some people when I did not have a cube visibly on my person.)

So, while he decides to get out of line from his place in front of me and fill out some other slip he forgot to fill out on the first go-round, I polish off a quick solve before he can really even turn around and look. He then asks me "So you know all the combinations?" I said yes, and went on with the rest of my bank business, but by the time I was back in my car again I felt like I had given the laziest answer possible. I realize that not answering "Yes" would not be particularly helpful at that moment, since there was no reason I needed to lecture the poor gentleman merely trying to make conversation about how many combinations there really are and why you didn't need to know all of them. This post is merely me trying to make amends for my incredibly lazy answer to that question.

Let's start with the obvious (well, obvious to me) part. I do not, and can not know all the combinations. I say that I can not know all the combinations because there are a little over 43 quintillion combinations. If I had a second apiece to learn each one it would take more than a trillion years. As it turns out, however, it is not necessary to know all the combinations - it is only necessary to know all the combinations of smaller, well-defined groups. For example, if you had completed one face of a cube and wanted to put in the edges of the middle layer, let's look at the possibilities. At this point, there would only be eight edges unsolved, as the four on the first face would already be in their correct places. Since I'm old school, we'll call the solved layer the Up, or U face. As you look for edges to place in the middle layer, and you look at each one in turn, they would be:
  1. In the middle layer already, correctly placed and oriented,
  2. In the middle layer already, correctly placed but not correctly oriented,
  3. In the middle layer already but not correctly placed,
  4. In the Down (D) layer such that the color of the edge piece on the D face is to the left of its eventual location in the middle layer, or
  5. In the Down (D) layer such that the color of the edge piece on the D face is to the right of its eventual location in the middle layer.
So, instead of dealing with 8! (8 factorial, or 8*7*6*5*4*3*2*1=40320) possible locations of the last eight edges at that point, we look at the same 5 possibilities 4 times in a row. This is the basic mechanism of every cube solution. At each step, deal with only a subset of the pieces, limit the number of choices you have to make, and craft algorithms to solve the specific cases that don't disturb the work already done in previous steps and don't concern themselves with pieces yet to be solved.

Of course, I could have explained all this to the guy that I was talking to in line at the bank and he could have said, "Yeah, that's what I meant."