New Solver Algorithm (CURRENT VERSION)

The above algorithm was a previous algorithm to check the operation of an iterative analyzer. It was a redundant algorithm, so, we design a new algorithm more effective and optimized in solving geometric problems.

Once analyzed the functioning of the class Solver and Analyzer, we have focused on two key points for best results.

  • In creating the construction plan.
  • And in an Iterative Analyzer (which uses decompositors with backtraking) that in case of error, it can find the next valid solution.

The construction plan will always be created

A Solver object has three attributes: a Analyzer, a Selector and a Constructor. As explained in previous sections, each object represents a step in the resolution of the geometric problem.

To do the new algorithm or operation of Solver, we have focused on the Analyzer object, this object is responsible for constructing plan if everything is correct (the problem is complete). If not, the Constructor returns a null contruction plan and it can not resolve the problem.

The Analyzer will not build a construction plan if the problem does not have all the necessary constraints. When the Analyzer performs the evaluation of the problem, it is decomposed into a tree (creating a construction plan). When evaluation reaches a leaf node, this node should be composed of two elements (points or lines) and a restriction (for example one distance), if not the construction plan will be missed and will returned as null.

So, our idea will be an Analyzer that it can build always the construction plan, and if we find a leaf that lacks a restriction, automatically our Analyzer will insert a temporal constraint to be consistent and keep building the construction plan.

The Decompositor with Backtracking

In the following section, we can find a good explanation about the Backtracking algorithm.