Just another WordPress site

To do it solving this one optimally using breadth-first search would probably– would definitely– take more than the lifetime of the universe So don’t try seven by seven by seven Leave that to the cubing experts, I guess I think no one will ever solve a seven by seven by seven Rubik’s Cube optimally There are ways to find a solution just not the best one So let me tell you just for fun, as an example This Pocket Cube, which is a two by two by two Rubik’s Cube What we have in mind is called the configuration graph or sometimes configuration space But it’s a graph, so we’ll call it a graph This graph has a vertex for each possible state of the cube So this is a state This is a state This is a state This is a state Now I’m hopelessly lost Anyone want to work on this? Bored? No one? Alright, I’ll leave it unsolved then So all those are vertices There’s actually a lot of vertices There are 264 million vertices or so If you want To the side here Number of vertices is something like 8 factorial times 3 to the 8 And one way to see that is to draw a two by two by two Rubik’s Cube So these are what you might call cubelets, or cubies I think is the standard term in Rubik’s Cube land There’s eight of them in a two by two by two Two cubed You can essentially permute those cubies within the cube however you like That’s 8 factorial And then each of them has three possible twists It could be like this It could be like this Or it could be like this So you’ve got three for each And this is actually an accurate count You’re not over-counting the number of configurations All of those are, at least in principle, conceivable If you take apart the cube, you can reassemble it in each of those states And that number is about 264 million Which is not so bad for computers You could search that Life is a little bit easier You get to divide by 24 because there’s 24 symmetries of the cube Eight times three You can divide by three, also, because only a third of the configuration space is actually reachable If you’re not allowed to take the parts apart, if you have to get there by a motion, you can only get to 1/3 of the two by two by two So it’s a little bit smaller than that, if you’re actually doing a breadth-first search, which is what you’re going to be doing on your problem set But in any case, it’s feasible That was vertices We should talk about edges For every move– every move takes you from one configuration to another You could traverse it in one direction and make that move You could also undo that move Because every move is undoable in a Rubik’s Cube, this graph is undirected Or you can think of it as every edge works in both directions So this is a move It’s called a quarter twist This is a controversy if you will Some people allow a whole half twist as a single move Whether you define that as a single move or a double move is not that big a deal It just changes some of the answers But you’re still exploring essentially the same graph So that’s the graph and you’d like to know some properties about it So let me draw a picture of the graph I’m not going to draw all 264 million vertices But in particular, there’s the solved state– we kind of care about that one, where all the colors are aligned– then there’s all of the configurations you could reach by one move So these are the possible moves from the solved state And then from those configurations, there’s more places you can go Maybe there’s multiple ways to get to the same node