Article ID: | iaor20119951 |
Volume: | 17 |
Issue: | 5 |
Start Page Number: | 589 |
End Page Number: | 614 |
Publication Date: | Oct 2011 |
Journal: | Journal of Heuristics |
Authors: | Anstegui Carlos, Bjar Ramn, Fernndez Csar, Gomes Carla, Mateu Carles |
Keywords: | combinatorial optimization, programming: constraints |
Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in Bailey et al. (1990), Morgan (2008) and Vaughan (2009). On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of