Hidden Variable Encoding

In our first empirical study we investigated the performance of two MAC algorithms that operate in the HVE, and compared them to MGAC-2001, their counterpart in the non-binary representation. The two MAC algorithms for the HVE are MHAC-2001, which stands for MAC in the HVE that only instantiates original variables, and MHAC-2001-$full$ which is a MAC algorithm that may instantiate any variable (dual or original) according to the heuristic choice. As stated by their names, all three algorithms use AC-2001 (GAC-2001) to enforce AC. Although we also run experiments with the various versions of FC, we do not include any results since these algorithms are inefficient on hard problems (especially on hard crossword puzzles). However, the qualitative comparison between FC-based algorithms for the HVE and the non-binary representation is similar to the comparison regarding MAC-based algorithms.