Show simple item record

dc.contributor.authorAnsótegui Gil, Carlos José
dc.contributor.authorBéjar Torres, Ramón
dc.contributor.authorFernàndez Camon, César
dc.contributor.authorGomes, Carla
dc.contributor.authorMateu Piñol, Carles
dc.date.accessioned2013-09-16T14:08:20Z
dc.date.available2013-09-16T14:08:20Z
dc.date.issued2006
dc.identifier.isbn9781577352815
dc.identifier.urihttp://hdl.handle.net/10459.1/46638
dc.description.abstractRandom problem distributions have played a key role in the study and design of algorithms for constraint satisfaction and Boolean satisfiability, as well as in ourunderstanding of problem hardness, beyond standard worst-case complexity. We consider random problem distributions from a highly structured problem domain that generalizes the Quasigroup Completion problem (QCP) and Quasigroup with Holes (QWH), a widely used domain that captures the structure underlying a range of real-world applications. Our problem domain is also a generalization of the well-known Sudoku puz- zle: we consider Sudoku instances of arbitrary order, with the additional generalization that the block regions can have rectangular shape, in addition to the standard square shape. We evaluate the computational hardness of Generalized Sudoku instances, for different parameter settings. Our experimental hardness results show that we can generate instances that are considerably harder than QCP/QWH instances of the same size. More interestingly, we show the impact of different balancing strategies on problem hardness. We also provide insights into backbone variables in Generalized Sudoku instances and how they correlate to problem hardness.ca_ES
dc.language.isoengca_ES
dc.publisherAssociation for the Advancement of Artificial Intelligence
dc.relation.isformatofVersió postprint del document publicat a: http://www.aaai.orgca_ES
dc.relation.ispartofProceedings of the twenty-first National Conference on Artificial Intelligence, 2006, p. 10-15ca_ES
dc.rights(c) Association for the Advancement of Artificial Intelligence, 2006
dc.subject.otherTecnologia Innovacionsca_ES
dc.subject.otherIntel·ligència artificial
dc.subject.otherSudoku
dc.titleThe impact of balancing on problem hardness in a highly structured domainca_ES
dc.typearticleca_ES
dc.identifier.idgrec010547
dc.type.versionacceptedVersionca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessca_ES


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record