We want to redefine Coef to be Rational32. However, we want to be
able to build linear expressions as easily as before. We will do this
by retaining the overloads with i32, and introduce new overloads for
operations with Rational32s.
This constraint unifies two variables. This is done by substituting
one variable for another in all of the current constraints, resulting
a new set of constraints.
We would like to make the equality constraint perform the more general
substitution: "coef1 var1 -> coef2 var2 + constant". While this
constraint is less general, it can be used when the variables are not
integer quantities.
Separate the list of puzzle constraints from the puzzle structure.
This allows different stages of the puzzle solution search to have
different constraints.
Functions to manipulate candidates during the solution search now
always return a Result instead of sometimes returning a bool, and
other times returning an Option.
We opted to use Result over Option mainly to (ab)use the try! macro.
In addition, it also makes it emit a warning when we forget to handle
the result. (We tend to assume people don't just ignore the result
and continue as normal, instead of putting the puzzle in a special
contradiction detected state.)
Constraints must now implement the substitution of "from" with "to".
The implementations can be sanity checked when we come to build the
list of constraints that each variable wakes up.
In the future, we would like to make the more general substitution:
from -> scale * to + constant.
We will implement unification by substituting one variable for
another, creating a new set of constraints. Only the affected
constraints need to perform the substitution, the others can simply be
cloned. As such, we will store constraints using reference counting.
This function takes a LHS and RHS only to give the illusion of an
equality. It simply subtracts one from the other because our
equations are all in the form: coef_i var_i + constant == 0.
This is a very simple equality constraint. It only assigns a variable
when all other variables in the equation have been assigned. Possible
improvements:
- We can find the min and max range by considering the coefficients
and the max and min values of the other variables in the equation.
- When there are only 2 variables remaining, we can eliminate the
incompatible candidates and then substitute one variable for the
other in other constraints.
While these functions can be found in rational number libraries,
support for rational numbers is an extra complexity that we do not
wish to tackle at this stage. We'll use these to keep things simple.
This allows one to easily build linear constraint equations by writing
equations with the tokens.
Note that variables will always take integer values, but coefficients
may be generalised to support rationals.
