Combinatorial problems can be modeled as constraint satisfaction problems (CSP). Modeling and resolution of CSP is often strengthened by global constraints (e.g., Alldiff constraint). We propose a formal system and some propagation rules for reducing domains of variables appearing in several Alldiff global constraints. We illustrate our approach on the well-known Sudoku puzzle which presents 27 overlapping Alldiffconstraints in its 9 x 9 standard size. We also present some preliminary results we obtained in CHR and GeCode.
展开▼
机译:组合问题可以建模为约束满足问题(CSP)。通常通过全局约束(例如,Alldiff约束)来加强CSP的建模和解析。我们提出一个正式的系统和一些传播规则,以减少出现在多个Alldiff全局约束中的变量的域。我们以著名的数独难题为例进行说明,该难题以其9 x 9标准尺寸呈现27个重叠的Alldiffconstraints。我们还介绍了在CHR和GeCode中获得的一些初步结果。
展开▼