Online Rubik's Cube solver: how do solver apps work?

What does a solver app do with your cube?

Every 3x3 solver app goes through the same four steps:

1. It takes in the colours. You pick a colour for each of the 54 stickers on a flat picture of the cube, or hold each face up to the camera so the app can read the colours itself.
2. It checks them. The app works out whether those 54 stickers make a real Rubik's Cube that can be solved.
3. It finds a solution. An algorithm searches for a short list of moves that brings the cube to its solved state.
4. It shows each move. The app shows the moves one at a time, usually with an animation, so you can follow along on your real cube.

Here is a real example. Hold a solved cube with white on top and green at the front, then scramble it with these 12 moves: D B2 U' L2 F2 D R2 U2 L U' F R'. If you entered this cube's colours into an app, one valid solution is these 12 moves: R F' U L' U2 R2 D' F2 L2 U B2 D'. The picture on the left is the scrambled cube, and the picture on the right is the cube after those 12 moves.

1. You start with (input)
3. After the formula

This example is kept short so it is easy to follow. With a properly scrambled cube, the solution the computer finds is usually close to 20 moves (more on that below).

The algorithm inside the app

A 3x3 Rubik's Cube has 43,252,003,274,489,856,000 possible states (Wikipedia). No computer can try them one by one. So most apps split the problem into smaller parts, using a method published by the German mathematician Herbert Kociemba, called the two-phase algorithm.

Phase 1: get the cube into the "easy group"

Kociemba noticed a special group of states: the ones you can reach from a solved cube using only turns of the top (U) and bottom (D) faces, plus half turns (180 degrees) of the four side faces. On Kociemba's own site this group is called G1, generated by U, D, R2, L2, F2, B2 (Kociemba).

In G1, every piece is "the right way round": the top and bottom faces only have white and yellow stickers, and the four edges of the middle layer sit in the middle layer (though they may have swapped places with each other). Phase 1 looks for a short list of moves that takes the scrambled cube to a state like that. In the example above, the first 4 moves of the solution do exactly this.

Phase 2: finish using only "easy" moves

From G1, the computer only uses U, D and half turns of the side faces. With fewer choices, the search is far quicker. Here is the example cube after the first 4 moves, R F' U L': notice that the top face is all white and yellow. The remaining 8 moves, U2 R2 D' F2 L2 U B2 D', solve it without a single quarter turn of a side face.

1. You start with (input)
3. After the formula

Once it has a first solution, the computer usually keeps trying other ways through phase 1 to find a shorter total. According to Wikipedia, this approach usually solves a randomly scrambled cube in under a second with 20 moves or fewer, but it does not guarantee the shortest possible solution (Wikipedia).

The shortest solution and "God's Number"

Some programs always find the shortest solution, such as the one by Richard Korf, but they are much slower (Wikipedia). So how short can it get? In July 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge proved that every state can be solved in 20 moves or fewer (counting each turn of a face, including a 180-degree turn, as one move). That number 20 is called "God's Number". The proof took about 35 CPU-years on computers lent by Google (cube20.org).

In other words, a 20-move solution from an app is already very close to the best possible.

How to enter the colours correctly

Most mistakes with online solvers come from entering the colours, not from the algorithm. A few rules will help you get it right the first time:

• Centres never move. On a 3x3, the six centres always stay in the same positions relative to each other. The colour of the centre tells you which face it is (Wikipedia).
• Hold the cube the same way from start to finish. For example, white on top and green at the front. When you scan the side faces, only turn the whole cube in the direction the app asks for.
• Count the colours. Each colour must have exactly 9 stickers. If a colour has 10, you have definitely entered one sticker wrong.
• Be careful with red and orange. Phone cameras often mix up these two colours under yellow light. Scan somewhere with white light, avoid shadows, and check the result before you press solve.
• Standard cube colours: white is opposite yellow, green is opposite blue, red is opposite orange (Wikipedia). With white on top and green at the front, red is on the right.

Why does the cube not come out solved when you follow the moves?

A solution only works for the way you were holding the cube when you entered the colours. With the example cube above, if you accidentally hold it upside down (yellow on top) and do all 12 moves, the cube will not come out solved, even if you do not get a single move wrong: held upside down, R now turns the face that was on the left when you entered the colours, and U turns the face that was on the bottom.

Other common reasons: turning a move the wrong way (R instead of R'), missing a move when you are going fast, or entering one sticker wrong while the app still finds a solution for that "wrong" cube. If you get lost halfway, the quickest fix is to enter the colours of the cube as it is now and solve it again from the start.

Why does the app say "invalid cube"?

If you take a cube apart and put it back together at random, only 1 in 12 ways of putting it together can be solved by turning (Wikipedia). That is because turning the faces can never produce these three situations:

• One edge flipped in place, with everything else correct.
• One corner twisted in place, with everything else correct.
• Only two pieces swapped with each other, with everything else correct.

The app checks for exactly these things. When it reports an error, there are two possibilities:

1. You entered a colour wrong. This is the most common case. Check each face again, especially the red and orange stickers.
2. The cube itself was put together wrong. A piece may have popped out and gone back the wrong way round, or someone may have peeled off and re-stuck the stickers. In that case, no solution can work: you need to take that piece out and put it back the right way round.

Reading the solution: what do R, U' and F2 mean?

Apps write solutions in standard international notation. Each letter is a face: R (right), L (left), U (up, the top), D (down, the bottom), F (front), B (back). A letter on its own means turning that face a quarter turn clockwise, as you look straight at that face. An apostrophe (') means turning it anticlockwise, and a 2 means a half turn.

For example, the move R turns the right face a quarter turn. The picture on the left is before the turn and the picture on the right is after it; only the pieces this move shifts are coloured in.

1. You start with (input)
3. After the formula

The move U' turns the top face a quarter turn anticlockwise:

The post on Rubik's Cube notation for beginners and the notation page have an animation for each move. A tip for following an app: say each move out loud, go slowly, and do not change how you hold the cube partway through.

When should you use a solver app?

A solver app is really useful when:

• You have bought a new cube, tried turning it, and want it solved again straight away.
• You are getting the hang of solving, you are stuck on a step, and you need the cube back to solved so you can practise again.
• You are curious what a short solution for a particular state looks like.

But following 20 moves from a computer will not help you solve the cube yourself next time. A two-phase solution does not go layer by layer, so it is very hard to remember or understand. And every new scramble gives you a completely different list of moves.

If you want to solve it yourself, a beginner method only needs a few short algorithms and works on every cube. EasyRubic's 7-step guide starts with the white cross:

Start at step 1, see the whole route on the guides page, or read the post on how to solve a 3x3 Rubik's Cube for beginners. Once you can solve it, you can time yourself with the 3x3 timer and read about CFOP to solve faster.

The EasyRubic phone app, coming soon to the App Store and Google Play, will also be able to scan the cube in your hand and show you each next move, along with the 7-step guide so you can gradually go from relying on a computer to solving it yourself.