CMU Math Student Charts a New Path with Rubik’s Cubes
Cassia Crogan
- Director of Media Relations, Carnegie Mellon University
- Email ccrogan@andrew.cmu.edu
Heidi Opdyke
- Associate Dean of Marketing and Communications, MCS
- Email opdyke@andrew.cmu.edu
- Phone 412-268-9982
Rubik's cubes are great for fun, fast-paced problem solving, but they also have a rich mathematical structure involving ideas of symmetry and connectivity. A 3x3x3 Rubik’s cube has 43 quintillion possible layouts. For a computer, graphing a path through these would take longer than the amount of time the universe has existed.
Since the design of the cube also allows for endless loops of moves (for instance, spinning one side infinitely), mathematicians at Carnegie Mellon University are exploring just how large and slow the path to solving it can be. One mathematical sciences junior, Jenny Quan, has solved the “younger brother” case of the 2x2x2 cube and its 4 million states, opening up the possibility for the larger puzzle to be investigated someday.
Instead of solving a 2x2x2 cube in the fewest possible moves, Quan’s Summer Undergraduate Research Fellowship focused on a different kind of efficiency: finding the longest possible path to a solution without repeating a position and solving the cube as slowly as possible.
Through independent research, Quan has led the charge to solve this problem of previously untackled scope, bringing the maximal possibilities of the puzzle into reality.
Solving the unsolved
Her research viewed the task through the lens of the Hamiltonian path problem, which tests the possibility of getting from one point on a graph to another, touching every other point without repeating any.
“Something similar to that is the traveling salesman problem,” Quan explained. “You want to visit every single city and every single address as efficiently as possible.”
She treated the total set of all the 2x2x2 cube’s possible layouts as one such graph: Each one of the Rubik’s cube’s possible layouts as a distinct point, and the shortest possible turn from each one to a neighboring layout as a line.
However, because even these smaller cubes are so rich in potential combinations, this meant the full graph would have millions of points, making it impossible to assess at once. “It may seem simple on small networks of 10 or 20 points,” she explained during a three-minute thesis presentation. “But as we get to larger networks with thousands of points, even computer programs can struggle to find Hamiltonian paths.”
From one point to the next
Having first learned about the mathematical properties of Rubik’s cubes at Canada/USA Mathcamp, Quan would make her way to CMU and join the Carnegie Mellon University Math Club (CMUMC). After watching Bernardo Subercaseaux, a doctoral research assistant in the School of Computer Science, give a presentation on the topic, she and fellow mathematical sciences major Noah Kim reached out.
“They approached me and said, ‘Hey, we both like mathematics and we both like Rubik's cubes as well. Is there anything we can do?’” Subercaseaux said. “I was obviously very excited, because that's a bit of a dream: Some motivated students that come to you and say they want to work with you, do some of the work for you.”
Subercaseaux connected them with Computer Science and Math Teaching Professor John Mackey from the Mellon College of Science, and he wasn’t sure what the solution to the problem would look like when he handed it off to them.
Kim kicked off the project in the winter with a Summer Undergraduate Research Apprenticeship. With less free time to work on it during the school year, Quan later applied for the SURF project to continue their work over the summer, and was approved to do 8-10 weeks of paid research on the subject with Mackey and Subercaseaux’s guidance.
Even Subercaseaux’s own background research required him to tap into the findings of hobbyists and non-academic sources. Humanity's knowledge of the Rubik's Cube, he explained, has advanced through mailing lists and forums more than through academic papers.
“The people that generally have made significant improvements in our knowledge of the cube have not been professional mathematicians,” Subercaseaux said.
He recalled finding a forum post from 2011 on a Rubik’s cube speed-solving forum by a user named ‘cuBerBruce,’ explaining how they’d discovered a Hamiltonian path through the cube.
However, figuring out whether a Hamiltonian path existed for every starting point was a much more intensive task. In this case, it required Quan to break the challenge down into smaller, more manageable tasks. She developed her own code with logical boundaries, making sure to exclude impossible configurations of the cube.
Certain properties inherent to the Rubik’s cube helped her reach a definitive approach.
“The nice thing is that this network is also very symmetric,” she said. “That is to say, regardless of what position the Rubik’s cube is in, the moves available to us are always the same. So locally, the shape of this network looks the same around every point.”
This symmetry allowed her to split the network up into smaller, more manageable graphs of equal length. It also helped her discover which configurations of the cube have a Hamiltonian path that ends in a solved state. In that way, Subercaseaux says Quan’s research is helping to unveil the important connection between the concepts of symmetry and connectivity in graph theory.
The ability to move in any of the six available directions from any position on the cube prevents bottlenecking, a problem found in fields from civil engineering to architecture (the original field of study of Ernő Rubik, the inventor of the cube).
“Symmetry helps you with connectivity, and connectivity helps you with Hamiltonian paths,” he said.
Much of this is clear through the graphs Quan and Kim have developed to help explain their findings. “There's a way to write this stuff down using syntax and sentences, but the pictures that they made are just really beautiful and compelling,” Mackey said. “It made me realize that there's an interplay between mathematics, art and computer science, which is really powerful.”
The question still remains as to whether or not the same principles and findings would apply to a 3x3x3 cube. As an immediate next step, Quan is hoping to present her mathematical research to a conference in recreational mathematics.
Classes like Fundamentals of Programming and Great Ideas in Theoretical Computer Science provided the groundwork for the coding, while the courses in her math major helped her discover exactly which questions to ask and principles to use to answer them.
Self-motivation through SURF
By pulling on threads of independent knowledge, Quan was able to use the tools and time afforded to her while studying at CMU to identify a specific issue and accomplish her own goal.
For her, the chance to work with faculty and graduate students is something she attributes to the SURF program. “SURF allowed me to do full-time paid research, something I didn’t think I could do as early as my sophomore summer,” Quan said.
“The ability to work with such brilliant, motivated, amazing undergraduates keeps me intellectually alive,” Mackey said. “That's how important it is to be around these young, really smart people.”
As a teaching professor, Mackey said that mentoring Quan through the SURF program provided him the chance to engage with research. Additionally, Subercaseaux and Mackey say that while they helped to advise, Quan made most of the progress on the research on her own and deserves recognition for it.
“You might phrase it as, ‘Oh, you were walking Jenny through the process.’ But she's walking me through the process of figuring out how you can teach and learn,” Mackey said. “Learning is a two-way street.”
