Universitat de Lleida
    • English
    • català
    • español
  • català 
    • English
    • català
    • español
  • Inicia la sessió
Repositori Obert UdL
Visualitza l'element 
  •   Inici
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • Visualitza l'element
  •   Inici
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • Visualitza l'element
JavaScript is disabled for your browser. Some features of this site may not work without it.

Generating highly balanced sudoku problems as hard problems

Thumbnail
Visualitza/Obre
Postprint (388.9Kb)
Data de publicació
2011
Autor/a
Ansótegui Gil, Carlos José
Béjar Torres, Ramón
Fernàndez Camon, César
Gomes, Carla
Mateu Piñol, Carles
Citació recomanada
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Gomes, Carla; Mateu Piñol, Carles; . (2011) . Generating highly balanced sudoku problems as hard problems. Journal of Heuristics, 2011, vol. 17, núm. 5, p.589–614. https://doi.org/10.1007/s10732-010-9146-y.
Impacte


Logo de Web of Science    citacions a Web of Science

Logo d'Scopus    citacions a Scopus

Logo de Google Acadèmic  Google Acadèmic
Compartir
Exportar a Mendeley
Metadades
Mostra el registre d'unitat complet
Resum
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 [8, 44, 39, 9]. 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 m rows and n columns with m = n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables – variables with the same value in all the solutions of an instance– and hardness of GSP.
URI
http://hdl.handle.net/10459.1/46629
DOI
https://doi.org/10.1007/s10732-010-9146-y
És part de
Journal of Heuristics, 2011, vol. 17, núm. 5, p.589–614
Projectes de recerca europeus
Col·leccions
  • Articles publicats (Informàtica i Enginyeria Industrial) [933]

Contacteu amb nosaltres | Envia comentaris | Avís legal
© 2022 BiD. Universitat de Lleida
Metadades subjectes a 
 

 

Explora

Tot el repositoriComunitats i col·leccionsPer data d'edicióAutorsTítolsMatèriesAquesta col·leccióPer data d'edicióAutorsTítolsMatèries

Estadístiques

Veure estadístiques d'ús

D'interès

Política institucional d'accés obertDiposita les teves publicacionsDiposita dades de recercaSuport a la recerca

Contacteu amb nosaltres | Envia comentaris | Avís legal
© 2022 BiD. Universitat de Lleida
Metadades subjectes a