Mostrar el registro sencillo del ítem

A hybrid AC3-tabu search algorithm for solving Sudoku puzzles

dc.contributor.authorSoto R.
dc.contributor.authorCrawford B.
dc.contributor.authorGalleguillos C.
dc.contributor.authorMonfroy E.
dc.contributor.authorParedes F.
dc.date.accessioned2020-09-02T22:28:40Z
dc.date.available2020-09-02T22:28:40Z
dc.date.issued2013
dc.identifier10.1016/j.eswa.2013.05.019
dc.identifier.citation40, 15, 5817-5821
dc.identifier.issn09574174
dc.identifier.urihttps://hdl.handle.net/20.500.12728/6301
dc.descriptionThe Sudoku problem consists in filling a n2×n2 grid so that each column, row and each one of the n×n sub-grids contain different digits from 1 to n2. This is a non-trivial problem, known to be NP-complete. The literature reports different incomplete search methods devoted to tackle this problem, genetic computing being the one exhibiting the best results. In this paper, we propose a new hybrid AC3-tabu search algorithm for Sudoku problems. We merge a classic tabu search procedure with an arc-consistency 3 (AC3) algorithm in order to effectively reduce the combinatorial space. The role of AC3 here is do not only acting as a single pre-processing phase, but as a fully integrated procedure that applies at every iteration of the tabu search. This integration leads to a more effective domain filtering and therefore to a faster resolution process. We illustrate experimental evaluations where our approach outperforms the best results reported by using incomplete search methods. © 2013 Elsevier Ltd. All rights reserved.
dc.language.isoen
dc.subjectConstraint satisfaction
dc.subjectMetaheuristics
dc.subjectSudoku
dc.subjectTabu search
dc.subjectConstraint Satisfaction
dc.subjectExperimental evaluation
dc.subjectIncomplete searches
dc.subjectMeta heuristics
dc.subjectResolution process
dc.subjectSearch procedures
dc.subjectSudoku
dc.subjectTabu search algorithms
dc.subjectLearning algorithms
dc.subjectTabu search
dc.subjectIterative methods
dc.titleA hybrid AC3-tabu search algorithm for solving Sudoku puzzles
dc.typeArticle


Ficheros en el ítem

Thumbnail
Nombre:
item_2-s2.0-84878885083.pdf
Tamaño:
2.5Kb
Formato:
PDF
Ver/

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem