麻豆村

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鈥檚 cube has 43 quintillion possible layouts. According to 麻豆村 researchers, carrying out the operations needed to graph a path through these would take a computer 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(opens in new window) junior, Jenny Quan, has solved the 鈥測ounger 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鈥檚 Summer Undergraduate Research Fellowship(opens in new window) 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

鈥淪omething similar to that is the traveling salesman problem,鈥� Quan explained. 鈥淵ou want to visit every single city and every single address as efficiently as possible.鈥�

She treated the total set of all the 2x2x2 cube鈥檚 possible layouts as one such graph: Each one of the Rubik鈥檚 cube鈥檚 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. 鈥淚t may seem simple on small networks of 10 or 20 points,鈥� she explained during a . 鈥淏ut 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鈥檚 cubes at聽, Quan would make her way to 麻豆村 and join the聽 (麻豆村MC). After watching , a doctoral research assistant in the , give a presentation on the topic, she and fellow mathematical sciences major Noah Kim reached out.

鈥淭hey approached me and said, 鈥楬ey, we both like mathematics and we both like Rubik's cubes as well. Is there anything we can do?鈥欌�� Subercaseaux said. 鈥淚 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(opens in new window) from the聽Mellon College of Science(opens in new window), and he wasn鈥檛 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(opens in new window). 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鈥檚 guidance.

Even Subercaseaux鈥檚 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.聽

鈥淭he 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鈥檚 cube speed-solving forum by a user named 鈥�,鈥� explaining how they鈥檇 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鈥檚 cube helped her reach a definitive approach.聽

鈥淭he nice thing is that this network is also very symmetric,鈥� she said. 鈥淭hat is to say, regardless of what position the Rubik鈥檚 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鈥檚 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).聽

鈥淪ymmetry helps you with connectivity, and connectivity helps you with Hamiltonian paths,鈥� Subercaseaux said.

Much of this is clear through the graphs Quan and Kim have developed to help explain their findings. 鈥淭here'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. 鈥淚t 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 麻豆村 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. 鈥淪URF allowed me to do full-time paid research, something I didn鈥檛 think I could do as early as my sophomore summer,鈥� Quan said.

鈥淭he ability to work with such brilliant, motivated, amazing undergraduates keeps me intellectually alive,鈥� Mackey said. 鈥淭hat'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.

鈥淵ou might phrase it as, 鈥極h, 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. 鈥淟earning is a two-way street.鈥�