Coding Adventure: Solving the Rubik's Cube

Added: 2026-05-12

[00:00:00]Hello everyone and welcome to another coding adventure. No doubt you've encountered one of these fish little things before. A perplexing puzzle with quintilions of permutations known as the Rubik's cube. And our quest today is to write a program capable of solving it.

[00:00:16]So let's begin by creating a virtual cube which I've set up three loops in the code here going negative 1 0 positive 1 along each axis which spawns in 26 little cube meshes. And running that now gives us this exciting result.

[00:00:30]The individual blocks here are known as cubies or cublets, but we obviously need to slap some stickers on them still so we can tell them apart.

[00:00:38]I'll refer to these stickers as facelits in the code and create them along each nonzero axis direction. Meaning that corner cubelets get three, edges get two, and the centers just get one.

[00:00:51]This facellet function I'm calling by the way simply spawns in another cube mesh positioned out along the given axis from the cubelet and also scaled along that axis by a thickness parameter.

[00:01:02]Finally, the axis is mapped to an index between 0 and 5. So we can assign a unique color to each of the sides. Okay, let's see how it goes. So I'll bring in the settings and we can try bringing down the scale and thickness values to something not like that. Let me adjust a little. All right, that's looking better for the scale. And I'll bring down the thickness some more. I don't want it to be negative, though. The GP is making some interesting abstract art out of that. Cubism, I suppose. Anyway, let's get some color going. So, I'll set this first face to be green. And let's think of that as the front face of our cube.

[00:01:39]The back face then needs to be blue if we're sticking to convention. And then in between those, I'll put in a red face on the right. paired on the left with orange. And that leaves our final pairing as white on the top and yellow on the bottom. All right, there we have our cute little cube. Now, we just need it to do something. I guess I'll begin with some simple keyboard controls for rotating the left, right, up, down, front, and back faces. For instance, if we press the letter L, we'll want it to start turning the face that's pointed along the negative X-axis. And holding shift can just switch which way around that turn takes. So given some axis, we can loop over every facellet and test if it's pointed in the same direction, which would mean that the cublet it's attached to is one that needs to be tanned. And that information can then be entered into a queue of animations that we need to process. All right, so each frame, we just need to grab whoever's at the front of that queue, increment their animation timer, and use it to calculate the current angle. The cubelets are then rotated by that angle. And finally, once the animation's complete, it gets kicked from the queue. So, let's give it a whirl. I've set up some button controls as well here. And we can try turning the up face, perhaps.

[00:02:55]Okay. Apparently, I didn't quite think that through properly, but we can at least test that the correct cublets are being detected. So, let's try the down side and the front side, the back side, the right side, and the left side. And that's all looking pretty good. All right, I've just been patching up the code quickly. So, it now grabs the state of the cublets at the start of the turn.

[00:03:17]So, we can then have the rotation be relative to that. And the rotations are also centered around the face as a whole rather than the individual centers of each cubelet. Hopefully, that will do the trick. So, I'll try twisting the up face again. And that is turning beautifully now. Also, hold down shift to try the opposite direction, which is working nicely as well. So, let's then try the right face. And uh that was a little less successful. I think it should be an easy fix, though. It's just that I forgot when we're figuring out which facellets are aligned with the axis of rotation that we have to of course account for any rotations that they've already undergone. Essentially just converting the facellet's local axis into world space. So, with that little tweak, let's give it another shot.

[00:04:03]And finally, it seems to be behaving.

[00:04:07]This is a bit of a clunky control scheme though, so I've also started implementing some simple mouse controls.

[00:04:12]But turns out I really am bad at rotations.

[00:04:16]After longer than I'd like to admit, though, I have got them working at last.

[00:04:20]I'm not entirely sure why I bothered actually since we're making this for the computer to solve. I just got carried away, I guess. Anyway, the computer's going to need to search many millions of moves, I imagine. And even bypassing the animations of costs and just applying the 3D rotations directly is still going to be ridiculously inefficient. So this is a nice graphical version for us to see what's going on, but we should make a more compact representation for the computer to enjoy.

[00:04:47]Let's begin by separating the cube out into edges, corners, and center pieces.

[00:04:52]These centers don't really matter, though, because while one can turn them around, doing so is equivalent to just turning both of the adjacent faces the other way. And so we can simplify our lives somewhat by just considering them to be locked in place. All right, back to the edge pieces. Then I want to identify each of these with a number.

[00:05:10]Like maybe starting with the top layer, we can go around in a circle 0 1 2 and 3. And then in the middle layer, we have 4 5 6 and 7. And finally in the bottom 8 9 10 and 11. Now what I'm thinking is that we can pack these 12 numbers up into a 64-bit integer like so. and then rotating the bottom edges like this, for example, would correspond to simply shuffling those bits around to be like this instead.

[00:05:41]There is something still missing from this picture though, which is the orientation of the edges. Like if we take edge zero over here, it currently has its white side facing up, but with a little maneuvering, it could land in the same spot, only the white side's now facing forward instead. So we need some sort of system for defining which of the two orientations an edge is in. And one way we could approach it is by assigning a ranking of sorts to each pair of sides on the cube. Like perhaps the top and bottom or white and yellow could be ranked highest followed by the front and back faces which we made green and blue and then left and right obviously last.

[00:06:19]With that defined, we can then look at an edge like say this one here, which has a yellow face lit on the left side and green on the front side. Of those two colors, we ranked yellow higher than green. But of those two sides, we ranked the front higher than the left. And that means that lowly green is enjoying the superior accommodation, which let's call the unoriented case. If we look at this edge up here though, blue is ranked higher than orange and it's on the top side, which is ranked higher than the left. So the hierarchy is being followed this time making it the oriented case.

[00:06:54]All right, back to our big binary number. Then we can insert an extra bit for each edge which let's say should be zero if the edge is oriented and one if not. I think that's a nice compact way of describing the cube. Although we're still missing the corners of course. So let's quickly speed through the same process for those. So, I'll assign IDs 0 1 2 3 in the top layer and 4 5 6 7 in the bottom. Six is in hiding currently, but there he is, of course. Now, we need to think about orientation again since corners have three facellets, meaning three possible orientations. But every corner has either white or yellow on it, meaning we can always just focus on what side that sticker appears. So here, for instance, yellow is on the top side, which is the highest rank. And so, we can call that case zero. But if it were on the front instead, that's ranked in the middle. So let's call it case one.

[00:07:46]And finally, if it's on the left or right side, that would be case two. So we can back these corners into a single integer as well. Though this time we need only three bits for the ids, but two bits for the orientations in the code. Then we have this cube state structure to store our edge and corner values. And we can also create constants for what those values will be in their starting configurations.

[00:08:10]meaning that testing if a cube is solved is as simple as comparing two numbers.

[00:08:15]Now for the fiddly bit which is actually updating the cube state when a turn is made. So there are 18 total turns we need to account for and that's if we don't include the so-called slice turns which affect the centers as we discussed and if we count clockwise and counterclockwise quarter turns as well as half turns all as their own individual moves. I mean, we could simplify by saying that only clockwise quarter turns exist and you have to do them twice to go halfway round and thrice to go counterclockwise, but that feels a little weird to me. So, anyway, I've set up a quick test here to make each of those 18 turns on the cube just for some visual verification. And in case you care, the move index is being converted into the axis and turn direction we need for actually doing the rotation with this little helper function here. Okay. So, let's try running it and just make sure that it's doing what it's supposed to be doing.

[00:09:15]All right, that checks out. So now, if we consider those IDs we assigned to edges and corners again, we can also think of them as describing fixed locations on the cube. Like corner zero when it's solved is in location zero.

[00:09:28]But if we twist the face now, corner three has moved into location zero instead. Meanwhile, corner zero has gone to location one, and so on. So, it'd be handy to have a map of where the cublets in each location get transported by each of the turns. And that's exactly what this little function is for. It just makes each of the 18 turns to see what goes where and then prints that out for us. So, let's run it quickly.

[00:09:55]And now we have this map of start and end locations for each turn. The reason I've printed this out, by the way, is that I actually want to paste the raw data into the code rather than generating it at startup. Not because of speed. It's essentially instant, but rather to isolate our pure cube solving code from all the dirty 3D graphic stuff. It doesn't really matter. It just feels nice. Okay, so now if we're told to move whatever bits are in location zero over to location 4, for instance, we can do that by taking a copy of the value and shifting it over 20 places to the right. And then we just have to make a mask for that location so that we can clear out the bits we don't want to move and an inverse of that mask to also clear out whatever old data is in that location. Finally, the two values can then just be ordered together to combine them. All right. So over here I've created this move class now to hold the masks and shift counts for the four edge and corner cublets that are affected by the move. Some of these can maybe be combined. I'm not sure. But I already feel I'm over complicating things. So let's just get it working fast. By the way though, the data is being generated with this little function here using that mapping of start and end locations we extracted a moment ago.

[00:11:11]Now to actually perform a move on our sort of abstract cube. I've just been working on this make move function which simply returns a new cube state with modified edge and corner values. And those modifications are being done over here like we talked about. One minor detail though is that some bits need to go to the right rather than the left of course and so we have to shift both ways. Okay, we're almost done with this part of the journey. We just need to update the orientations as well. Edges are super simple. Based on our rules, only front and back quarter turns will flip the orientation of an edge. All other turns leave them intact. So, I've generated another mask for each move, simply saying which bits need to be flipped. And we can use the exclusive or operation to execute that flip over here. If you find all this bit manipulation stuff very mysterious, by the way, you might be interested in my still work in progress series on digital logic because I've certainly found playing around with that stuff to be very helpful. In any case, corners are a little more intricate to deal with.

[00:12:12]Firstly, top and bottom turns cause what we called orientation zero to remain zero, but orientation one gets turned into two and orientation two gets turned into one. Then for left and right turns, zero becomes one, one becomes zero and two remains two. While for the front and back, zero becomes two, one remains one, and two becomes zero. This will be on the test. The best I managed to come up with for handling this is a little switch over those three types of turns with some more bit manipulations to transform each orientation to its target value. I definitely feel like I'm missing something more elegant, though, so I'd love to hear if you have better ideas. All right, I've been spending some time just twisting things around and making sure all the bits are in their proper places. There was some misbehavior at first and I had to track down a few sneaky bugs, but I'll spare you the details of that tedious process.

[00:13:00]As far as I can tell, it's working correctly now. And that means we can finally start trying to solve this thing. So, I've begun by writing a recursive function here that simply explores every possible path of moves up to a given depth limit and tests if a solution has been found at any point.

[00:13:18]Let's just see how far we can go with this. It's been proven that the cube can always be solved in 20 moves or fewer.

[00:13:25]So, if we can reach that, we're essentially done already. But I'm not overly optimistic. All right, let's see, though. Depth one takes 0 milliseconds and visits a total of 19 nodes. So, that's the start state and then the state after each of the 18 moves. At depth two, the time is still zero. And same story at depth three, but at depth four, we finally get a millisecond on the clock. After that, depth 5 takes 20 milliseconds. Depth 6 takes 380. Depth 7 leaps up to seven whole seconds. And depth 8 then takes a whopping 2 minutes, visiting about 11 billion nodes on the way. So, we're not getting to depth 20 in any reasonable amount of time like this, unfortunately. So, for now, let's instead think about what moves we might be able to cut out entirely. Like an obvious one for instance is that if you turn a face, there's no purpose to then immediately turning that same face again. So I've stored the face index in the move object, allowing us to compare it to the previous move made inside the search and prune that path if they match. Trying the depth 8 search again, then this takes us from 2 minutes down to 36 seconds. Then there's at least one more redundancy we can easily prune which involves turning one face and then the opposite face. These moves don't affect one another and so it doesn't matter what order they're done in.

[00:14:48]Therefore, in the code, we can detect that case and make sure we only explore one of the parts. All right, that's taken us down to about 16 seconds for the search. Now, I'm not sure what else we could easily optimize, though. So, let's just spread the work out among multiple threads. I'll take a very simple approach where we have a searcher class that allows us to explore a given first move. So, it makes that move here and then begins searching. The idea now is to create 18 of these little searches, each starting from a different one of the 18 possible moves, of course, and set them to run in parallel.

[00:15:23]Let's see how it goes. And depth 8 is completing in about 3 seconds. Now, I guess that's progress, but depth 20 still remains hopelessly out of reach.

[00:15:34]So, let's give up on solving the cube in the fewest possible moves for today at least. And instead, I've been writing this evaluation function, allowing the solver to aim for the highest scoring position, rather than expecting it to see the entire solution right away. The obvious thought I had here is to simply count the number of cublets that are in their solved locations and orientations.

[00:15:55]That way, the maximum scores, of course, when all of them are solved. I am also subtracting the number of moves taken to reach this position by the way so that it knows to prefer shorter paths. Okay.

[00:16:06]Now after running our search threads, we can check which one found the highest score and return that thread starting move as the next move in our work in progress solution. This will all then be run again and again until hopefully it succeeds in solving the entire thing. I also thought we could start the search out at depth six for faster computation, but allow it to increase to a maximum of eight if it can't find a way to improve the previous score. If it fails at eight, though, that's too bad. I'm not waiting for a depth 9 search. All right, now I'll scramble up the cube with a 100 or so random moves and just wait for that to finish.

[00:16:45]And then let's hold thumbs and run the silver.

[00:17:03]Wait, did that actually work? I was not expecting that. All right. Well, what I want to do then is just run it a thousand times, let's say, with different scramles, of course, and gather some statistics about the solves.

[00:17:17]I'm going to name this the greedy solver since it tries to accumulate correct cubits as quickly as it can without any real care for the future. And the statistics are in. It is taking on average 44 moves to solve the cube with about 10 seconds of computation time.

[00:17:32]However, it only actually succeeds in solving the cube in a measly 9.6% of attempts. So, we got pretty lucky with that first attempt, I guess. Much more commonly, what happens is it gets itself into a position like this, where the cube is mostly done, but it just can't see far enough ahead to fix the last few pieces without messing up the rest.

[00:17:54]Okay, 90% failure is not good enough. We desperately need to search deeper. But we've seen the exponential explosion that occurs. So rather than increasing the depth, how about we do a second search that goes backwards from the solved position and see if the two searches overlap at any point, which would of course mean that we've found a path to victory.

[00:18:16]So I've just duplicated our search code to make this version here that simply stores all the states it encounters in a big list along with the number of moves taken to reach each of them.

[00:18:27]Once that's been run, starting from the solved state, we can then transform the lists from each thread into a giant dictionary that allows us to look up a cube state and see how many moves away from solved it is. Okay. I've then also been modifying the greedy solver quickly to incorporate this lookup in its evaluation. So, if it finds the current position in the dictionary, then it knows for sure that it's on the right track. These lookups are fairly fast, but we're doing so many that it does add up very quickly. So, I've also added this cheaper lookup first, which only tells us if the state might be in the dictionary. Additionally, I've kept the size of it very small, only exploring five moves backwards, which uses about 10 megab of memory. Going one move more jumps up to 150 megabytes, and unfortunately slows the search down quite significantly.

[00:19:15]All right, with that done, let's scramble up another cube here and see how our new solver fares.

[00:19:26]Okay, there may have been a few little bugs in my initial implementation, but I spent some time patching those up. So, let's try this again.

[00:19:46]Nice. It seems to be working. Just for fun, let's try another scramble. And this time I'll make the cube sort of see-through so we can get some sort of sense for how it all comes together.

[00:19:56]We're also going to need a name for this new version. And since it uses a so-called meet in the middle approach, let's call it the sandwich solver.

[00:20:07]Taking a look at its statistics from a thousand solves, it has an average move count of 39, a computation time averaging 7 seconds, and a success rate of 72%. So, a big improvement up from 10% to be sure, but I wouldn't say I'm satisfied with the sandwich. I don't really know what to try next, though.

[00:20:26]So, I've just been browsing this overview of existing techniques, and it talks about things like write co-et spaces and iterative deepening AAR, which all sounds intriguing, but that's definitely going to require some research. What has caught my eye as something simple we could try today though is just this concept of using a restricted move set for part of the solution. So remember how the orientation we defined for edges is only affected by front and back tons. And in case that didn't make sense earlier, let me show this on an actual cube quickly.

[00:20:57]Like say we want this white green edge here to be flipped so that white is on the top instead. We can twist the top and right and bottom and left faces as much as we want. That's never going to happen. As you can see, we're obligated to turn the front face or back face in order to get there. Corners, on the other hand, if we check our notes here, can get to and from any orientation without front or back moves. For example, let's take this red, blue, white corner over here, and see how we're able to cycle through its three orientations with just right and top turns. For instance, the significance of all this is just that once all edges are correctly oriented, we know then that front and back tans are no longer necessary to solve the cube. And so that's where this evaluation function aims to get us simply by counting up the number of oriented edges and returning that as the score. Again, taking move count into consideration as well. Of course, if we run this now from a random scramble, we can see it takes just a handful of moves to get the job done. So, this will be the first phase of our silver. But as soon as we detect that the score for all 12 oriented edges has been achieved, we can switch to phase two, the sandwich phase, in which front and back tens are eliminated from the move set. That means there just 12 possible moves now instead of 18. And this allows us to search an extra two moves deeper in roughly the same amount of time. And we can increase the lookup depth by two as well without too much impact on performance. Finally, the evaluation function for this phase I've just left exactly the same as our previous sandwich solver. Simply checking if the position exists in the lookup. And if not, then falling back to the greedy evaluator. All right, let's grab a scramble cube and see how it goes.

[00:22:56]Okay, looking good. And let's try another scramble on the see-through cube while we decide on a name for this version. I suppose its full name would be the edgeoriented greedy sandwich solver, but that's a bit of a mouthful, so let's call it the oriented solver simply.

[00:23:13]I've been running it now on a thousand random scrambles like the others, and the stats are in with an average move count of 40, an average duration of 8 seconds, and a success rate this time of 99.8.

[00:23:27]So, our little solver is almost perfectly consistent, but clearly there are some edge cases where it manages to elude the lookup and still fall into the same trap we saw with the purely greedy solver. Nevertheless, I feel like we've made a pretty good start for today. In the future, I'd obviously like to get the success rate up to 100 and also work on bringing the move count down since we know that all scrambles are solvable within 20 moves and our solver currently averages twice that number which feels quite extravagant. So, I would love to hear any ideas you might have for improving this approach or for something different we could try. That is all for now though. So, until next time, thanks for watching.