Algorithms for the Hidden Variable Encoding

In this section we discuss specialized algorithms for the HVE. We first describe a simple AC algorithm for the HVE that has the same worst-case time complexity as an optimal GAC algorithm for the non-binary representation. In Appendix A, we also show that for any arc consistent CSP the proposed AC algorithm performs exactly the same number of consistency checks as the corresponding GAC algorithm. For arc inconsistent problems we show that the AC algorithm for the HVE can detect the inconsistency earlier and thus perform fewer consistency checks than the GAC algorithm.

We also consider search algorithms for the HVE that maintain local consistencies during search. We show that, like maintaining arc consistency, the generalizations of forward checking to non-binary CSPs can be emulated by corresponding binary forward checking algorithms in the HVE that only instantiate original variables.