Devising an Algorithm for Solving Rubik's Cube

Related Links

• Science Fair Project Guide

Project Summary

Difficulty	9  –  10
Time required	Long (a couple of weeks)
Prerequisites	To do this project you should enjoy solving puzzles and thinking in three dimensions.
Material Availability	Readily available
Cost	Very Low (under $20)
Safety	No issues

Sponsor

Sponsored by a generous grant from Motorola

Objective

The goal of this project is to devise an algorithm for solving Rubik's cube, using three sets of moves that each accomplish a specific function.

Introduction

Rubik's cube is an interesting 3-dimensional puzzle that challenges your spatial imagination and memory. The goal is to arrange the cube so that each side is a solid color, as shown in Figure 1.

Figure 1. Diagram of a solved Rubik's cube. The six sides are named in pairs—up-down, front-back, and left-right. The up (U), front (F), and right (R) sides are visible. The remaining sides—left (L), back (B), and down (D)—are shown by the projected images.

Figure 1 also shows the labels we will be using when referring to sides of the cube. The six sides are named in pairs—up-down, front-back, and left-right. To refer to a specific side, we'll use the one-letter abbreviations shown in Figure 1 (U, D, F, B, L, R).

The cube is built in such a way that each side, row, and column can rotate (see Figure 2). With a few turns, the colors can be thoroughly mixed up. How can you get all of the squares back to their original positions? It's quite a puzzle to get the colors arranged properly again!

Figure 2. Diagram of the core of a Rubik's cube. The core enables each side, row, and column of the cube to rotate.

In this project you'll learn three sequences of moves that accomplish specific rearrangements of the squares on the cube. Can you figure out how to use these three move sequences to solve the cube?

Before we present the moves, we need to introduce some more terminology, so that we can distinguish individual pieces on the cube. Rubik's cube is made of three different types of pieces. We will refer to them as center, corner, and edge pieces. The puzzle has six center pieces, one in the middle of each face. Each center piece has only one visible face. There are eight corner pieces on the puzzle. Each corner piece has three visible faces. The remaining twelve pieces are edge pieces, occupying the middle position along each edge of the cube. Each edge piece has two visible faces.

	Center Piece	Corner Piece	Edge Piece
location
# in entire cube	6	8	12
visible faces	1	3	2

Now we're almost ready to present the move sequences. Remember that each move sequence accomplishes a specific rearrangement of the pieces in the cube. For each move sequence, we'll describe that specific rearrangement both with a diagram and with words. Then we'll describe the move sequence in words and in a shorthand notation. You'll soon find that the shorthand makes it easier to execute the moves quickly and memorize them.

The shorthand notation is easy to learn. There are just five rules you need to know.

1. When a side is rotated clockwise one quarter turn, the shorthand notation for the move is simply the letter of the side. For example, if you're supposed to rotate the right side one quarter turn clockwise, the shorthand would be R.
2. When a side is rotated counterclockwise one quarter turn, the shorthand notation for the move is the letter + an apostrophe ('). For example, if you're supposed to rotate the right side counterclockwise one quarter turn, the shorthand would be R'.
3. When a side is rotated twice (direction does not matter in this case), the shorthand notation for the move is the letter + 2. For example, if you're supposed to rotate the front side twice, the shorthand would be F2.
4. For some of the moves, you will be moving only the center column of a side. For a clockwise rotation of one quarter turn, the shorthand is the letter of the side, followed by 'c' (for center column). For example, if you're supposed to rotate the center column of the front side one quarter turn clockwise, the shorthand would be Fc.
5. Finally, if you're supposed to rotate the center column of a side counterclockwise one turn, just add an apostrophe ('). For example, if you're supposed to rotate the center column of the front side one quarter turn counterclockwise, the shorthand would be Fc'.

Move Sequence #1

The first exchanges the positions of three edge pieces at once, altering nothing else. The three affected edge pieces are all on the center column: the bottom and top edge on the left side, and the opposite edge on the top side (see Figure 5). Repeating this sequence three times will restore the cube to its original configuration.

Figure 5. Move sequence #1: exchanging three consecutive edge pieces in the center 'slice' of the cube (yellow arrows at left). No other pieces are altered by this move sequence. Repeating this sequence three times restores the cube to its original configuration.

Move Sequence #2

The second sequence 'cycles' five corner pieces: the four corners of the front face, plus the upper right corner. It also exchanges the positions of three the front side edge pieces, as shown in Figure 4.

Figure 4. Move sequence #2: 'cycling' the four corner pieces of the front face. This sequence changes the positions of five corner pieces (yellow arrows) and three edge pieces (blue arrows). Compare the before and after pictures carefully. Repeating this sequence fifteen times restores the cube to it's original position.

Move Sequence #3

The third sequence 'flips' each of two opposite edge pieces in the upper layer without altering anything else on the cube, as shown in Figure 5. The two edge pieces wind up back in their original places, but with the original colors 'flipped.' Compare the before and after views to verify that this is true. Note that repeating this sequence twice restores the cube to the original position.

Figure 5. Move sequence #3: 'flipping' two opposite edge pieces (marked by *'s in the 'before' view). The effect of this sequence is to 'flip' each of these two opposite edge pieces, without altering anything else. The two pieces will be in their original positions, but with colors reversed. Repeating this sequence restores the cube to the original position.

Note: move sequence #3 is much easier to remember (and can be done more quickly) if you move the center column of the front side (a center 'slice' of the cube) rather than moving the left and right sides. Try this out with your own cube and verify that it does the same thing. (Unfortunately, the Java applet used for the animated diagrams does not provide for movements of center slices, so we can't show you this alternate sequence with an animated diagram.) Here is the move sequence in shorthand, using center slice moves (Fc means to rotate the center slice 'up' and Fc' means to rotate the center slice 'down'):
Alternate shorthand: [Fc U'] 3 times, then [U' Fc'] 3 times, then U2.

Can you figure out how to solve Rubik's cube using only these three sequences of moves?

Terms, Concepts and Questions to Start Background Research

To do this project, you should do research that enables you to understand the following terms and concepts:

• Rubik's cube:
  • how it moves,
  • terminology:
    • corner pieces (8),
    • edge pieces (12),
    • center pieces (aka side pieces, 6);
• algorithm.

Questions

• How many visible faces does an edge piece have? A center piece? A corner piece?
• Which move sequences don't alter other pieces?
• Are the three move sequences presented sufficient to solve the puzzle?

Bibliography

• This project is based on the following article:
  Cao, C., 2002. "A Simple Complexity," illumin 3(2), Fall, 2002 [accessed December 19, 2006] http://illumin.usc.edu/article.php?articleID=11.
• For information on algorithms, see:
  Wikipedia contributors, 2006. "Algorithm," Wikipedia, The Free Encyclopedia [accessed December 19, 2006] http://en.wikipedia.org/w/index.php?title=Algorithm&oldid=96361172.
• Potential spoiler alert! Here are some other ways to solve the cube, with step-by-step instructions. Consult these only if you're stuck. They may give you some ideas on alternative strategies:
  • Beust, C., 2003. "A Rubik's Cube Solution That Is Easy to Memorize," [accessed December 19, 2006] http://beust.com/rubik/.
  • Lee, J., 2004. "Beginner Solution to the Rubik's Cube," [accessed December 19, 2006] http://www.geocities.com/jasmine_ellen/RubiksCubeSolution.html.
  • Petrus, L. 1997. "Solving Rubik's Cube for Speed," [accessed December 19, 2006] http://lar5.com/cube/index.html.
• The Java applet used to illustrate the move sequences in this project is called "Caesar," and was written by Karl Hšrnell, Lars Petrus, and Matthew Smith. For instructions on using the applet, see the first link below. To download a copy of the applet, see the second link:
  • Petrus, L., date unknown. "The Java Cubes: How to Use the Cube Illustrations," [accessed December 19, 2006] http://lar5.com/cube/javacube.html,
  • Petrus, and Smith, 1996. "'Caesar' Rubik's Cube Applet (download page)," [accessed December 19, 2006] http://lar5.com/cube/downloads.html.

Materials and Equipment

To do this experiment you will need the following materials and equipment:

• a Rubik's cube,
• timer.

Experimental Procedure

1. Do your background research so that you are familiar with the terms, concepts, and questions, above.
2. If you can already solve Rubik's cube before doing this project, your first step should be to measure your average solution time. Time yourself for each of 5–10 trials, and calculate your average solution time. The cube should be well-randomized for each trial.
3. Study the three sets of moves covered in the Introduction.
4. Practice using each set of moves on your Rubik's cube.
   1. Verify that each sequence works as described.
   2. Become familiar enough with each set of moves so that you can step through the sequence in your imagination, without having the cube in your hands or within sight.
5. Figure out a logical sequence for applying these three sets of moves in order to solve the cube systematically. In other words, use the three sets of moves as the basis for developing an algorithm to solve Rubik's cube.
   1. During this step, it is important to determine whether the three move sequences presented in the Introduction are sufficient to solve the cube. In other words, is it possible to solve the cube with only these three move sequences, or do you need additional move sequences?
   2. If you determine that additional move sequences are needed, be prepared to show why they are needed. Develop one or more move sequences to fill in the missing rearrangements needed to solve the cube.
6. Once you have developed your algorithm, time yourself for 10 or more trials and see how long it takes you, on average, to solve the puzzle. The cube should be well randomized for each trial.
7. If you could solve the puzzle before you started the project, did your average solution time improve?

Variations

• For a more basic Rubik's cube experiment, see the Science Buddies project, What's the Fastest Way to Solve Rubik's Cube?
• Can naive Rubik's cube players use your algorithm to solve the puzzle? Find volunteers with no experience solving Rubik's cube. See if they can solve the puzzle on their own. Record how long it takes them to solve the puzzle, or to give up. Teach them your algorithm, give them some time to practice it, and time them again. Do this for at least five volunteers. Did their solution times improve? By how much, on average?
• Advanced. Are there even faster ways to solve Rubik's cube? Practice on your own, or do some investigation online. How much can you improve your average solution time?
• Advanced. If you have skills in computer programming, learn how to use the Java applet to demonstrate how your algorithm works. The Java applet used to illustrate the moves in this project was written by Karl Hšrnell, Lars Petrus, and Matthew Smith. It can be obtained from: http://lar5.com/cube/downloads.html.

• For more science project ideas in this area of science, see Pure Mathematics Project Ideas

Credits

Andrew Olson, Ph.D., Science Buddies

Sources

This project is based on:

• Cao, C., 2002. "A Simple Complexity," illumin 3(2), Fall, 2002 [accessed December 19, 2006] http://illumin.usc.edu/article.php?articleID=11.
• The Java applet used to illustrate the moves in this project was written by Karl Hšrnell, Lars Petrus, and Matthew Smith. It can be obtained from: http://lar5.com/cube/downloads.html.

Last edit date: 2007-02-13 22:00:00