Rubik's Cube Solver

Rubik’s Cube Solver

For many, solving the scrambled Rubik’s Cube gathering dust on a shelf seems an impossible challenge, so why not add a completely unnecessary layer of complexity and try to solve it as quickly as possible?

Let us design and build two high-performance Rubik’s Cube sovlers; one finds the fewest possible moves, and the other finds a solution in as little time as possible.

Check out the demo below. The UI is incomplete, so it is not particularly easy or pleasant to use, so read through the documentation for information on the controls. It is also worth noting that the solver is single-threaded on the web and is nowhere near as efficient as a native build, so for the best performance, build the solver yourself and run it locally.

Introduction

While a seemingly simple construction, there are over $4.325\times {10}^{19}$ distinct permutations of a three-by-three Rubik’s Cube, which is far too many to search in any sensible amount of time without some clever heuristics and optimisations.

One way to simplify the problem is to state it as finding a valid solve for the cube, as opposed to finding a solve that uses the fewest possible moves. This simplification allows us to exploit some interesting invariants of some subsets of possible moves at the expense of requiring more moves solve.

Finding a provably minimally short solution is, ultimately, a very clever brute-force search through the graph of cube states. Thus, the minimal-length solver can still take several minutes to find a solution for a difficult scramble.

Cube Definition and Naming Conventions

We will focus on a standard three-by-three Rubik’s Cube and use the same conventions as described by David Singmaster[1].