Decoding the Eternity Puzzle: A Journey with Dr. Garvie
Embarking on a journey through the captivating realm of puzzles, Dr. Marcus Garvie transforms the enigmatic Eternity Puzzle into a thrilling adventure of mathematical ingenuity. Leveraging the power of integer linear programming (ILP), a field deeply intertwined with computational geometry, he not only tackles this challenging puzzle but also illuminates a path for solving similar perplexities. The complicated dance of numbers and shapes reveals a story not just of complexity, but also of the potential for real-world applications, making this research a beacon in the vast expanse of tiling puzzles. The ILP approach he utilized has potential applications in various fields, including archaeology for reassembling broken two-dimensional objects and DNA nanotechnology for designing complex nanostructures. "Our research has relevance to a broad spectrum of exact cover problems, opening doors for others to apply our methods to solve different puzzles and challenges," Garvie highlighted.
Unraveling the Eternity Puzzle
The Eternity Puzzle has been a source of amazement and fascination since its creation in 1999. It consists of 209 polygonal pieces that are meant to fit within an almost-regular dodecagon, presenting a combinatorial challenge that was eventually solved, claiming the £1,000,000 prize for the clever individuals who cracked it. Garvie and Burkardt saw the puzzle as a unique opportunity to showcase the potential of computational geometry and linear programming. Their aim was to carve out an innovative path to resolution, demonstrating the versatility of his field in solving complex puzzles in new ways.
The Approach: A New Perspective
With a background in linear programming methods for tiling finite regions of the plane using polyominoes, Garvie decided to tackle the Eternity Puzzle using integer linear programming. "We focused on developing a flexible mathematical model that could not only address the Eternity Puzzle but could also be adapted for a wide range of similar tiling problems," Garvie shared.
The journey to solve the Eternity Puzzle was not without its challenges. The complexity of the puzzle's geometry required an innovative approach, and Garvie and Burkardt found the solution by combining MATLAB programming and the high-performance optimization package CPLEX. MATLAB is a programming platform specifically designed for engineers and scientists, allowing them to analyze data, develop algorithms, and create models with ease. CPLEX, on the other hand, is a high-performance optimization software that excels in solving linear programming problems, where you need to find the best outcome under a given set of constraints. "We transformed the Eternity Puzzle into a rigorously defined mathematical model, allowing us to apply advanced computational techniques to solve it," explained Garvie.
Applications and Future Endeavors
In the domain of computational geometry and tiling puzzles, Dr. Garvie stands as an innovator, blending mathematical rigor with computational tools to unravel the complexities of the Eternity Puzzle. His dedication and novel approach not only set a precedent for aspiring mathematicians and computer scientists but also highlighted the transformative potential of integer linear programming in tackling intricate tiling challenges. By diving into this elaborate world of exact cover problems – where one must cover a given set with subsets, ensuring every element is covered without any overlap – Garvie and Burkardt have not just charted a course toward solving the Eternity Puzzle but has also unlocked new possibilities for addressing similar challenges across diverse disciplines. This story, rich in mathematical achievement and computational proficiency, serves as both a journey of discovery and a foundation for future explorations, encouraging the next generation to think creatively, innovate, and solve the apparently unsolvable.
This story was written by Mehran Bozorgi as part of the Science Communicators: Research @ CEPS initiative. Mehran is a PhD candidate in the School of Engineering under Drs. Syeda Humaira Tasnim and Shohel Mahmud. His research focus is on the development of solar-assisted cooling systems to achieve thermal comfort conditions in buildings in different climate conditions.
Funding Acknowledgement: The research of M. Garvie was supported by NSERC Discovery Grant # 400159.
Reference: J. Burkardt and M. R. Garvie, “An integer linear programming approach to solving the Eternity Puzzle,” Theor. Comput. Sci., vol. 975, p. 114138, 2023, doi: 10.1016/j.tcs.2023.114138.