Overlapping Alldifferent Constraints and the Sudoku puzzle

TitreOverlapping Alldifferent Constraints and the Sudoku puzzle
Type de publicationCommunication
TypeCommunication avec actes dans un congrès
Date du colloque2008
Titre du colloqueXXXIV Conferencia Latinoamericana de Informatica, CLEI 2008
Titre des actes ou de la revueCLEI 2008 Proceedings
Pagination10 - p.
AuteurLardeux, Frédéric , Monfroy, Eric, Saubion, Frédéric , Crawford, Broderick, Castro, Carlos
VilleSanta Fe
Résumé en anglais

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.


Date du colloque : 09/2008

URL de la noticehttp://okina.univ-angers.fr/publications/ua4477
Lien vers le document en ligne