How Researchers found Gods Number[Technique Tuesdays]

A fun journey into Math, Programming, and Rubiks Cubes

Nov 22, 2023

Hey, it’s your favorite cult leader here 🦹‍♂️🦹‍♂️

On Tuesdays, I will cover problem-solving techniques that show up in software engineering, computer science, and Leetcode Style Questions📚📚📝📝.

To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!

Help me buy chocolate milk

p.s. you can learn more about the paid plan here.

Before we begin, a quick reminder- we’re planning meetups, networking events, and other cool IRL events. If you’d like to stay on top of things, join the discord for our cult here. Also, I am moving from Denver to NYC for the next few months. If you’re around the area, holla at your boy.

God’s Algorithm refers to any algorithm which produces a solution having the fewest possible moves. This refers to all kinds of combinatorial games and puzzles (most notably the Rubik’s Cube). Researchers have been trying to find the worst-case God’s Number for a while now. Today, we will be going over the procedure used to discover God’s Number for Rubik’s Cubes. This is a pretty light way to come across some of the techniques that are used in structural analysis and advanced combinatorics. If any of you pursue Math/Theoretical Computer Science in greater depth, you’ll definitely come across some of these ideas in more detail.

PS- Keep in mind that Rubik’s Cubes have 43,252,003,274,489,856,000 positions. Think about how you will approach solving such problems before continuing

With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves. We consider any twist of any face to be one move (this is known as the half-turn metric.)
Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube. One algorithm might use a sequence of moves to solve the top face, then another sequence of moves to position the middle edges, and so on. There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves.
-We’ll be referring to the excellent “God's Number is 20” for this writeup

Finding Gods Number

Partitioning- When we have a giant set of possibilities like this, it is wise to divide and conquer. “We broke the problem down into 2,217,093,120 smaller problems, each comprising 19,508,428,800 different positions. Each of these subproblems was small enough to fit in the memory of a modern PC, and the way we broke it down … allowed us to solve each set rapidly.” To those of you who didn’t study Group Theory, the term Coset in the source might be confusing. For our purposes, when we decompose a group into equally sized disjointed subsets, each of the subsets is a coset. These are a super important part of group theory, and I would recommend looking into generating Cosets by using a subgroup if you have any mathematical inclination.
Using Symmetry- This was my favorite part of the solution. Exploiting the symmetry of structures is a great way to cut down on the amount of work you need to do. When taught in school, we often use symmetric shapes to extrapolate a bigger shape from a smaller one. We can apply a similar principle- solve a portion of the problem and then use symmetry to extrapolate.
Image Source
In this case, “If you take a scrambled Cube and turn it upside down, you have not made it any more difficult; it will still take the same number of moves to solve. Instead of solving both of these positions, you can simply solve one, and then turn the solution upside down for the other. There are 24 different ways you can orient the Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving. Using similar symmetry arguments and by finding a solution to a large "set cover" problem, we were able to reduce the number of sets that needed solving from 2,217,093,120 down to 55,882,296.”
Dropping Optimality- Prior to this research, it was already established that the lower bound for God’s Number was 20. Thus, the researchers only needed to find the upper bound. They weren’t looking for the best solution for every sequence, just to find a solution of 20 moves or less for any given sequence. This made their life much easier.
Coding- After all this setup, they had reduced the search space for the solution dramatically. The only thing left was to code things up. The code has two components: solve one coset; and distribute all the cosets onto the machines offered by Google. The code took a few weeks to finish execution.

The usage of Cosets for partitioning and symmetry for cutting down search spaces are both great tools to add to your arsenal as you develop your own solutions. Would highly recommend adding them into your operations.

That is it for this piece. I appreciate your time. As always, if you’re interested in working with me or checking out my other work, my links will be at the end of this email/post. If you like my writing, I would really appreciate an anonymous testimonial. You can drop it here. And if you found value in this write-up, I would appreciate you sharing it with more people. It is word-of-mouth referrals like yours that help me grow.

Save the time, energy, and money you would burn by going through all those videos, courses, products, and ‘coaches’ and easily find all your needs met in one place at ‘Tech Made Simple’! Stay ahead of the curve in AI, software engineering, and the tech industry with expert insights, tips, and resources. 20% off for new subscribers by clicking this link. Subscribe now and simplify your tech journey!

Using this discount will drop the prices-

800 INR (10 USD) → 640 INR (8 USD) per Month

8000 INR (100 USD) → 6400INR (80 USD) per year (533 INR /month)

Get 20% off for 1 year