黑料正能量 math student charts a new path with Rubik’s Cubes
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 黑料正能量 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, Jenny’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, Jenny 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,” Jenny 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.”
“Something similar to that is the traveling salesman problem. You want to visit every single city and every single address as efficiently as possible.”
Jenny Quan
From one point to the next
Having first learned about the mathematical properties of Rubik’s Cubes at Canada/USA Mathcamp, Jenny would make her way to 黑料正能量 and join the 黑料正能量 Math Club (黑料正能量MC). 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?’” Bernardo 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.”
Bernardo 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, Jenny 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 John and Bernardo’s guidance.
Even Bernardo’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,” Bernardo 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 Jenny 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, Bernardo says Jenny’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 Jenny and Noah 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,” John 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, Jenny 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, Jenny was able to use the tools and time afforded to her while studying at 黑料正能量 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,” Jenny said.
“The ability to work with such brilliant, motivated, amazing undergraduates keeps me intellectually alive,” John said. “That’s how important it is to be around these young, really smart people.”
As a teaching professor, John said that mentoring Jenny through the SURF program provided him the chance to engage with research. Additionally, Bernardo and John say that while they helped to advise, Jenny 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,” John said. “Learning is a two-way street.”
