Computer Science: An Optimal Rubik's Cube Solver

Hey guys, this is mackheid01 with a different kind of video than what we usually make. Um, so today in this video, I'm going to be explaining an artificial intelligence concept that makes it possible for a program to optimally solve a Rubik's Cube.

So if you're not familiar with what a Rubik's Cube does, it's basically just 20 pieces and six center pieces which rotate along several different faces. After doing a few rotations, it actually becomes very difficult to put back into a solved state with all the colors on the same side. So I recently wrote a program which is capable of pretty quickly finding optimal solutions to a cube. If the cube is randomly scrambled, it'll take a couple of days, but if it's something that you're looking for a solution to, a neat pattern, it'll usually find the solution relatively instantly.

So I'm going to be explaining how the concepts behind this play out, how they work. This can obviously be applied to things different than the Rubik's Cube, but the Rubik's Cube will be our primary example.

The basic idea, which you would use to solve any puzzle if you weren't going to optimize it, is just to brute force the solution. The act of brute forcing is your program has some kind of internal representation of the Rubik's Cube. The way it tries to solve it is first it does maybe a top turn and then a top counterclockwise turn, and then a right turn and a left turn, then a down turn. If none of those solve the cube, then it tries a top turn, a right turn, a top turn, a left turn, a top turn, a down turn, and it basically tries every single possibility.

So it tries all the one-move solutions, the two-move solutions, etc., etc. That's basically how it works. A slight modification to this would be to use something called a search tree. Just using a search by itself is still kind of brute forcing, but the general picture, as I have right here, is that you start out with your scrambled state up here. Then you try making an R, you try making a U, and you get all these cubes, these different configurations out from doing that.

From each of those configurations, you expand one of these to then make an R and a D. This is just the brute force model we've seen. You might keep on expanding it and expanding it, trying more and more nodes down until you finally get to a solved cube. Then you just trace your way back, see what you did to get there, and you can print out the solution that you had to have used to get to the solved state.

So, pretty obviously, this will find an optimal solution because first it will go through all the one-move solutions, then the two-move solutions, until it's possible for the cube to be solved. However, after about seven or eight moves, it will take a long, long time to find a solution. For a random scramble of a Rubik's Cube, it can usually take between 16 to 18 moves to actually solve a random scramble.

So the problem becomes figuring out how to take this brute force model and still utilize the idea of brute force, or of just like searching, in order to find a solution. But at the same time, you have to make it so you can eliminate some stuff that you're searching for. Because, as it is, if there are 18 different ways you can turn a cube, counting double turns as a turn, then there's like 18 to the eighth power possibilities if you're doing eight turns. That's already too many for a computer to go through and do very quickly.

So the solution to this is using different teeny small sub-problems of the cube to reduce the number of moves it will take. The way you basically do this is, for instance, let's say I took this cube and I'll solve it real quick. You take the cube and you look at the corners alone. If you just look at the eight corners and ignore the edges, you still, if the cube is solved, all the eight corners will be solved. But if all the eight corners are solved, that doesn't necessarily mean the cube is solved. However, it takes 11 moves maximum to solve all the corners.

I know this after having written my program. You shouldn't necessarily know that, but the reason why it's important that it takes 11 moves is that that's actually something that's accessible to a computer. 11 moves, okay, maybe it would take a while to solve the corners without any optimization, but it would certainly be possible, and it would only take a couple of days if you are still on a decent computer.

So the way you utilize this aspect to solve a Rubik's Cube optimally is you have a program or, in this case, I wrote a program that I ran on an Amazon server for a couple of days. You could run it on your computer or do whatever. What the program will do is it will keep on messing up a cube. So it will do an R, then a U, then an R, then an L, then an L, then a U. You know, try it; messes up cubes again and again, records the configuration of the corners, and records how many moves it took to get the corners into that configuration.

After running this program for a couple of days, I got a giant—well, it was actually like half a day to a day—but I wrote a couple of different programs for a couple of different sub-problems like this, but the corners is the example I'm going to be using. After running this program, you'll get a little database, and this database will have all the different corner configurations and it'll say how many moves it would take to just solve the corners.

Now, it would have to take at least that many moves to solve the entire cube. So if I gave you a random scramble and you saw that the corners took seven moves to solve, you would know that it would take at least seven moves to solve that cube from that messed up state.

Now, why is this useful? Well, if you recall our search model here, which I have in front of us, you'll realize that let's say I'm searching for a one-move solution. So I make all these one moves—not much I can do there to optimize it. But now let's say I'm looking for a ten-move solution, right? I make two moves here, and I'm at this scramble—that's the scramble. Then I did an R and then I did an L, right?

So I managed to get to this scramble, and now I have eight moves left that I can make in order for this solution to be ten moves. Well, if I look at the corners and the corners take nine moves to solve, then I know that I don't have to look any further past this node, and I can just eliminate it.

So here's a slightly more complicated graph of just what it might look like. Let's say I'm looking for a ten-move solution because my program's gotten up to ten moves; it knows that it's no less than ten moves because it's tried all the nine moves already.

So it goes and it does an A, B, and then it does A, B, U. Let's say after it does A, B, U, it realizes, "Hey, this is gonna take nine more moves, and I've already done two moves." So that's too many, so I don't have to search this. Well, suddenly, I don't have to look at this node, and I don't have to look at anything branching off of it. So it can just vanish, and it simplifies the graph and lowers the work that the computer has to do.

Usually, this will happen a lot—like here, the R plus D might be more than ten moves, so it can get eliminated too. As it makes a third move, more things will get eliminated, and more and more stuff, and eventually, it will have looked for all the ten-move solutions by using this method. Then it'll move on to eleven-move solutions after that.

Some of the stuff that didn't get eliminated before won't necessarily get eliminated right away the next time. But so using this corners database, you can essentially, like, prune the search trees—what the actual term is. You can cut back nodes that you no longer have to search.

When I actually wrote my optimization for my program, I have a corners database, then I have a database with six edges and six other edges. Then I have a database that keeps track of edge orientations, which is something that people who solve a cube a lot will be familiar with, but people who don't won't. So I won't go into great depths explaining this.

Basically, it makes it so that the program can eliminate lots of stuff that it's searching, and we'll be able to find a solution that maybe is 18 moves, but it will be able to do it really quickly because it can eliminate nodes. You know, it only has to search things that are like minute possibilities.

This was just a little introduction to how some artificial intelligence searches work. So if you found that interesting, maybe you'll consider taking computer science; I don't know. But this is basically what artificial intelligence is all about.

Thanks for watching mac 101. Subscribe, and goodbye!