How fast can you solve the Rubik’s cube? In 2016, Feliks Zemdegs set a world record for solving a 3×3 Rubik’s cube in just 4.73 seconds. “I can’t compete with that,” explains the narrator of the Polylog YouTube channel, “but maybe my computer could if we redefine ‘fast’ a little bit.”
“Instead of time, let’s measure the number of moves it takes to solve a cube and let’s find an algorithm that will help us solve any cube the fastest, thereby, in a way, beating Feliks Zemdegs.”
“You’ll see that the algorithm will lead us to a surprisingly general technique that can also be used for completely different things such as breaking ciphers.”
That technique is called Meet in the Middle.
Much like Six Degrees of Separation—the premise that any two people in the world are connected to each other by no more than six intermediate relationships or acquaintances—Meet in the Middle looks to connect two states via the shortest path, and starts at both states to get there instead of starting at one and ending at the other.
“Now, we could run this algorithm for other graphs, not just the Rubik’s cube graph, but for it to work, it’s really crucial that the number of explored nodes grows exponentially in the number of steps. That ensures that if we walk half the distance we only see a tiny fraction of the nodes.”
The last third of the video, starting around 9m40s, focuses on the DES (Data Encryption Standard) algorithm and how this Meet in the Middle approach can break ciphers.
Related reading: Every position of Rubik’s Cube can be solved in fewer than twenty moves.
Related videos on TKSST include:
• Why are algorithms called algorithms?
• What’s the fastest way to alphabetize your bookshelf?
• The Graceful Tree Problem
• 2ⁿ, a story of the power of numbers from the 1961 Mathematica exhibit
• How many LEGO combinations can be made with 6 standard bricks?
Bonus videos: Solving a Rubik’s Cube in 0.38 seconds and Is this the largest Rubik’s Cube in the world?
via Kottke.
Curated, kid-friendly, independently-published. Support this mission by becoming a sustaining member today.