Labeling and variable/value ordering

Several predicates are provided for choosing variables, and for assigning values to variables.

• indomain(V): V is instantiated to a value in the domain. Upon backtracking, the domain variable is instantiated to the next value in the domain.

• indomain_down(V): This is the same as indomain(V), but the largest value in the domain is used first.

• indomain_updown(V): This is the same as indomain(V), but the value that is closest to the middle of the domain is used first.

• labeling(Options,Vars): Labels the variables Vars that are under control by the list of search options, where Options may contain the following:
  • Variable selection options
    • backward: The list of variables is reversed first.
    • constr: Variables are ordered first by the number of constraints that are attached.
    • degree: Variables are ordered first by degree, i.e., the number of connected variables.
    • ff: The first-fail principle is used: the leftmost variable with the smallest domain is selected.
    • ffc: This is the same as the two options: ff and constr.
    • ffd: This is the same as the two options: ff and degree.
    • forward: Chooses variables in the given order from left to right.
    • inout: The variables are reordered in an inside-out fashion. For example, the variable list [X1,X2,X3,X4,X5] is rearranged into the list [X3,X2,X4,X1,X5].
    • leftmost: This is the same as forward.
    • max: First selects a variable whose domain has the largest upper bound, breaking ties by selecting a variable with the smallest domain.
    • min: First selects a variable whose domain has the smallest lower bound, breaking ties by selecting a variable with the smallest domain.

  • Value selection options
    • down: Values are assigned to variables by using indomain_down.
    • updown: Values are assigned to variables by using indomain_updown.
    • split: Bisects the variable's domain, excluding the upper half first.
    • reverse_split: Bisects the variable's domain, excluding the lower half first.

  • Other options
    • maximize(Exp): Maximizes the expression Exp. Exp must become ground after all of the variables are labeled.
    • minimize(Exp): Minimizes the expression Exp.
    • time_out(Time,Result): This option imposes a time limit for labeling the variables. With this option, the labeling(Options,Vars) is equivalent to time_out(labeling(Options1,Vars),Time,Result), where Options1 is the same as Options, except that Options1 does not have a time_out option.
    • time_out(Time): This is the same as time_out(Time,_)

• deleteff(V,Vars,Rest): First chooses first a domain variable V from Vars with the minimum domain. Rest is a list of domain variables without V.

• deleteffc(V,Vars,Rest): First chooses a variable that has the smallest domain and the largest degree (i.e., the largest number of connected variables in the constraint network). Note that the degrees of variables are not memorized; instead, they are computed each time that deleteffc is called.

• labeling(Vars):
• fd_labeling(Vars): This is the same as labeling([],Vars).

• labeling_ff(Vars):
• fd_labeling_ff(Vars): This is the same as labeling([ff],Vars).

• labeling_ffc(Vars):
• fd_labeling_ffc(Vars): This is the same as labeling([ffc],Vars).