iBo32

RubiksPathFinder

Finding the optimal path between two states on a

Rubik's Cube using a breadth-ﬁrst search algorithm.

Introduction

Solving a Rubik’s Cube is easier than most people would think.

Even with zero prior knowledge of the cube, a simple 20 minute YouTube video is all you

need to get started with your cubing journey.

But what is hard is solving the cube optimally, meaning in the absolute least amount of

moves possible. Doing so is essentially impossible for humans, but computers aren’t

subject to such limitations.

As such, my goal for this project was to build a program capable of ﬁnding the shortest

(optimal) path between any two states on a 2x2 Rubik’s Cube.

Background

On the cube, there are six diﬀerent principal moves you can make:

Let’s visualize these moves as diﬀerent possible choices starting from a solved state:

Now, this graph displays all possible sequences if you decide to do only one move. But let’s

say you wanted to do two moves instead.

Well you could start with an F move as your ﬁrst move, then you could pick R, U, L, B, D, or

F again as a second move. So every ﬁrst move has 6 new possibilities for a second move.

Graphing this observation would look like this:

So as you can now see, for every move we decide to add, the number of possible

permutations increases dramatically. The number of permutations can be found using:

where n is the number of moves to choose from, and r is the number of moves to choose.

I know I said there are only 6 principal moves on the cube, but that’s not entirely true. Let’s

think of an R move, meaning turning the right face clockwise. You could also turn the face

counterclockwise (R’), or twice (R2). This leads to a total of 18 moves you could make.

Also, for this program, we will be excluding B moves for a few reasons , resulting in a

possible 15 moves to choose from (n = 15):

B moves are slower to execute by a human solver, plus they are generally unnecessary.

Now, using the previous formula, here is a table depicting the number of possible

sequences of moves of a given length with n=15:

As you can see, there are an incomprehensible amount of possible move sequences if you

choose to make 8 diﬀerent moves, for example.

So how can we manage this enormous set of data?

The most feasible way is to use a search algorithm, which is a way computers can navigate

large sets of data and obtain certain desired info (such as paths between states). In this

case, a search algorithm can be used to traverse through sequences of moves on the cube. It’s

basically a way to test diﬀerent move sequences and see if they solve the cube.

First and foremost, I had to choose a search algorithm. The two most practical ones are a

breadth-ﬁrst search algorithm and a depth-ﬁrst search algorithm. To understand the

meaning of these phrases, a diagram is the best bet.

A breadth-ﬁrst search algorithm explores all nodes at one depth before moving on to the

nodes at the next depth.

A depth-ﬁrst search algorithm simply explores as far down as possible within a branch, and

then searches down a diﬀerent branch.

For my program, I chose to use a breadth-ﬁrst search. A depth-ﬁrst search would work,

however, as it searches down a branch, it’s possible it will ﬁnd a solution of depth 7 when a

solution of depth 4 may be available. A breadth-ﬁrst search is guaranteed to ﬁnd the

shortest solution.

Now that we have all the graph theory and preliminary work covered, I can get to writing

the program.

Part 1: Storing the Cube in Memory

A 3x3 cube is made up of three important parts:

It’s probably common knowledge that a 2x2 cube is only made up of corners, with no edges

or centers. So all I need for this program is a way to store the corners. As such, I decided to

store the colors of each sticker on the cube in a single array.

To do so, I would need to deﬁne a set order of inputting the colors of the cube:

As you can see, there are 24 stickers on a cube. So I start by simply deﬁning an array of size

24. But we also need to store the state we desire the cube to be in. So I make another

similar array as well.

Following the diagram, a solved cube is read as WWWWOOOOGGGGRRRRBBBBYYYY.

Now we can store the initial state of the cube, and our desired end state. Now what? Well,

we can ﬁnally get to the solving algorithm.

Well, a good ﬁrst step is to check if the cube is already in the desired state:

But how do we check if the beginning and desired states are equal???

We use the StatesEqual() function:

Let’s break this down a bit. This function takes two arguments: the initial state and desired

state of the cube. We use a for loop to iterate through each sticker, checking if each sticker

on the initial cube state matches each sticker on the desired cube state. If even one does

not match, the cube is clearly not in its desired state.

Also, I have designated the character x to mean the color of that sticker does not matter in

the end. For example, I could input my desired state as WWWWxxxxxxxxxxxxxxxxxxxx,

which means you only want the top face of the cube to be all white, every other sticker can

be any color.

So if we are looping through the cube’s stickers and realize our desired state has an x in

that sticker position, we do not even check that sticker’s solvedness, since an x means it

doesn’t even matter.

THE FUN STUFF

So now we can get to the actual search algorithm.

Line 1: Simple enough. While the cube is not in its desired state, we want to keep going

until we get to its desired state. That’s the goal of the program after all :)

Line 6: I am using a library called Combinatorics which is capable of generating a set of

permutations for a given array of possible moves to apply to the cube:

In this case, a variation is basically just a permutation, but with an upper bound of length.

This is crucial, since we want to generate all combinations of a certain depth, not every

possible permutation (since this would take forever). So essentially, this Combinatorics

Library enables us to generate all possible move sequences of a certain depth to apply to

the cube.

Essentially, our plan from here is to follow a breadth-ﬁrst search algorithm. So we start by

generating all move sequences of depth=1 (R, R’, L, L’, etc.) and check them all to see if they

bring us to our desired state. If not, we increase the depth by one, re-generate our possible

move sequences with this new depth, and keep testing them. We repeat until we ﬁnd a

sequence of moves that brings us to our desired state.

An example of my program’s testing sequence could look like this:

R, R’, R2, L, L’, L2, U, U’, U2, D, D’, D2, F, F’, F2, R L, R L’, R L2, R U, R U’, …and so on

SInce we always start at depth=1, and don’t increase the depth until we check every

possible move sequence of that depth, we are guaranteed to ﬁnd the shortest path

to our end state of the cube.

THE CODE:

This snippet of code basically describes the above procedure. We have two nested foreach

loops. The outer one loops through each possible sequence of moves of a depth, and then

inner one loops through each move in that sequence. manipulate(move) takes a move,

and using hardcoded swaps, interchanges the stickers in our corner_init array to apply the

move to our cube.

For example, in a U move, the color in corner_init[0] gets moved to corner_init[1],

corner_init[1] gets moved to corner_init[2], and so on.

The swaps are performed by taking what’s in corner_init[0] and putting it into a temp array

new_cube[1], and so on with all swaps. Then the changes are written back into the

corner_init array from the new_cube array. This temp-array method is basically the

standard procedure for swapping values of arrays around.

Now that we applied all of the moves of our ﬁrst move sequence candidate, we check if

they solved the cube into our desired state:

If so, congrats, we run solved(); which prints the move sequence and exits the program.

Otherwise, we restore our corner_init array (since remember, we applied moves to it, so

it’s changed from its original). Smartly, we stored the cube’s original state in

corner_backup, so it’s just a matter of overwriting all values in corner_init with their

original values.

From here, the rest of the search process is simple. We continue looping through all

generated possible move sequences of depth=1, checking if any of them solve the cube into

our desired position. If none of them do, we increase the depth and keep trying. This gets

repeated until we ﬁnd a solution. The connection to a breadth-ﬁrst search algorithm should

now be apparent, and ﬁnally, this results in ﬁnding the shortest (aka optimal) path to any

state on a 2x2 cube.

THE MAIN LOGIC

Now, let’s put it all together. Combining all the aforementioned steps, we can outline the

main logic of this program:

So there we go!

Now that we’re completed designing this process, we can now ﬁnd the optimal path to any

state on a 2x2 cube! But, a question arises. How eﬀective is this algorithm?

PERFORMANCE EVALUATION AND LIMITATIONS

For this performance evaluation, I began by generating random cube states (generated

with CSTimer), and set the end state as having the ﬁrst layer solved, and a Sune CLL on the

top face (http://www.cyotheking.com/cll2-2). Graphing the time to solution as a function of

the number of branches searched, we have:

Average Search

Depth

Average States

Searched

Average Solution

Time

Average States per

Second

6.692307692

98621050.28

358731.7692

328399.5996

Clearly, the solve time increases linearly with an increase in searched branches. On

average, the program has to search 98,621,050 states before it ﬁnds a solution. So at

328,399 states per second, the average solve time is therefore about 358 seconds.

However, it’s worth noting that MOST cubes are solved in way less time. The average solve

time is skewed because of the few scrambles that take 8+ moves to solve. In reality, most

scrambles did not require 8 moves (more like 6-7), and so the realistic solve time is faster

than 358 seconds by a good margin.

The main performance constraints in this program come from a few factors, however two

of the main ones are the language it's written in, and poor programming decisions. First, I

am conﬁdent that a rewrite in C++ or a similar language would result in performance gains.

Secondly, I can ﬁx my bad code and make it more eﬃcient.

Besides these two issues, one other performance ﬁx comes to mind: Pruning. Basically,

pruning involves shaving oﬀ unnecessary branch visits by eliminating paths we logically

don’t need to take. For example, if it’s possible to deduce I do not need to begin with an “R”

move to reach my desired state, I can shave oﬀ 1/5 the search space by skipping all

branches beginning with “R”. As the largest performance-limiting factor is this program’s

astronomical search space, shaving oﬀ branches will absolutely result in massive

performance gains.