Automation of Triangle Ruler-and-Compass Constructions Using Constraint Solvers

Milan Banković
(Faculty of Mathematics, University of Belgrade, Serbia)

In this paper, we present an approach to automated solving of triangle ruler-and-compass construction problems using finite-domain constraint solvers. The constraint model is described in the MiniZinc modeling language, and is based on the automated planning. The main benefit of using general constraint solvers for such purpose, instead of developing dedicated tools, is that we can rely on the efficient search that is already implemented within the solver, enabling us to focus on geometric aspects of the problem. We may also use the solver's built-in optimization capabilities to search for the shortest possible constructions. We evaluate our approach on 74 solvable problems from the Wernick's list, and compare it to the dedicated triangle construction solver ArgoTriCS. The results show that our approach is comparable to dedicated tools, while it requires much less effort to implement. Also, our model often finds shorter constructions, thanks to the optimization capabilities offered by the constraint solvers.

In Pedro Quaresma and Zoltán Kovács: Proceedings 14th International Conference on Automated Deduction in Geometry (ADG 2023), Belgrade, Serbia, 20-22th September 2023, Electronic Proceedings in Theoretical Computer Science 398, pp. 62–72.
Published: 22nd January 2024.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: