On forward checking for non-binary constraint satisfaction

Abstract. Solving non-binary constraint satisfaction problems, a cru-cial challenge for the next years, can be tackled in two dierent ways: translating the non-binary problem into an equivalent binary one, or ex-tending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend denitions written for the binary case. This paper focuses on the well-known for-ward checking algorithm, and shows that it can be generalized to several non-binary versions, all tting its binary denition. The classical version, proposed by Van Hentenryck, is only one of these generalizations.