Figure 1: Architecture of the constraint solver system
The textual problem specification is handed to the constraint solver
which translates the constraints into a graph, and, as described
solves them by graph reductions.
The solver capabilities are the consequence of certain
that have been implemented.
If a particular constraint problem can be solved using these
steps, then our solver will find a solution.
Where the construction steps involve ruler-and-compass constructions, only
quadratic equations need to be solved.
But some construction steps are permitted that are not
ruler-and-compass, and in those situations the roots of a univariate
polynomial are found numerically.
This polynomial has been precomputed except for
the coefficients which are functions of specific constraint
A well-constrained geometric problem can have exponentially many solutions in the number of constraints. This is because the solutions correspond to the algebraic set of a zero-dimensional ideal whose generating polynomials are nonlinear. Our solver can determine all possible solutions. But doing so every time would waste time and overwhelm the user. So, certain heuristics narrow down the solutions to a final configuration that corresponds to the intended solution with high probability. In case a different solution is wanted, the solver can be redirected to the intended solution interactively.