Monday, September 24, 2012

Solving the Rubik's Cube, Part 1: Introduction

I was given a 4x4x4 and 5x5x5 Rubik’s cube as a bachelor gift (“should be easier to figure out than your wife”) and recently began working on the smaller one. I was taught the algorithm for solving the original 3x3x3 cube as a teenager, and somewhat regret not having the chance to solve it completely myself.  Since then I have solved a few other puzzle cubes. As it turns out, there are a number of phases of solving Rubik-style puzzles, and the techniques are actually quite generalizable and are very mathematical. I thought it might be interesting to document the solution process in a blog series, from the point of view of one who has never solved this cube before, and on the way we'll explore the various concepts that arise.  I will not be providing a thorough solution, and will try to warn about specific spoilers, in case anyone wants to solve it themselves.

To get started, we’ll first look at the anatomy of a cube. As everyone should remember from geometry, all polyhedra have vertices, edges, and faces. In a standard Rubik’s cube, this gives us three distinct types of blocks: corner blocks, edge blocks, and face blocks. Note that this is not the only possible mapping: the Skewb (pictured left) has only two types of blocks—corner and face—due to its diagonal cuts. The importance of recognizing the component blocks is that no operation will ever exchange (for example) a corner block with an edge block, or any other mismatch. Even more importantly, it is critical to see the cube as an arrangement of blocks, and not just stickers. Every operation moves and reorients whole blocks: stickers do not move independently.

In the 4x4x4 cube, we have four face blocks on each of six faces, giving us 24 face blocks with four-fold degeneracy (degeneracy simply means that we can’t tell the difference if the “degenerate” blocks are exchanged: the cube is still solved if these are “out of place” from where they started). We have two blocks on each of 12 edges, giving us 24 edge blocks with two-fold degeneracy and two different possible orientations (conversely, the cube is not solved if a block is in the correct location but the wrong orientation). Finally, there are eight unique corner blocks, each of which has three different orientations. Thus the total number of distinguishable configurations is ostensibly
(24!/(4!)6)×(24!/(2!)12×224)×(8!×38)/48 ≈ 4.5×1049,
although a large number of these are impossible to actually achieve without disassembling and reassembling the cube. So the puzzle space is actually several orders of magnitude smaller.

In the next installment we'll look at some initial explorations of cube operations, and define some notation for referring to the different blocks and rotations.

No comments: