Euclidea Solver is a brute force search program aimed to search for short solutions of straightedge and compass construction problems in Euclidea. It performs searches by traveling the whole sensible search space with depth-first search.
euclidea-solver [-p] [-l level] [-t thread] [-v version] chapter_number problem_number
chapter number and problem number refers to corresponding problems in the website. version refers to E or L goal of a problem, the default is E. Sequential search is used by default.
Flag -p turns on parallel searching. Flag -l refers to the level in DFS, on which the go routines will be spawned in parallel mode. The number of go routines spawned will grow with level but
is not fully predictable. Flag -t limits the number of go routines running simultaneously, preventing the large overhead if too many go routines are spawned when level is deep.
All the problems should be manually coded into problem package, I've only added a few examples (all examples are tested to be solvable),
but I believe you can figure out how to describe a problem by looking at them. Don't forget to add the function name to problem.go
after adding a custom function. A detailed guide may be added later.
The current search algorithm does not include optimization or branch pruning of any kind. If you have any good ideas for a certain problem, just include them in the problem statement, and that will greatly reduce the search time.
Here is an example to solve problem 15.10: Angle of 3 Degree. This experiment is run on a 48-core Xeon E5-2695v2 server, the search time may be much larger on a personal computer.
$./euclidea-solver -p -l=4 15 10
13 go routines deployed.
13 go routines deployed.
3 go routines deployed.
22 go routines deployed.
8 go routines deployed.
Solution found!
Number of boards searched: 112902489
Took 2m27.098416518s
A folder 15.10 Angle of 3 Degree_E_1561528019 is created, with the following images inside:
