A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles
Joint Authors
Soto, Ricardo
Paredes, Fernando
Galleguillos, Cristian
Norero, Enrique
Crawford, Broderick
Source
Computational Intelligence and Neuroscience
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-05-20
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
The Sudoku problem is a well-known logic-based puzzle of combinatorial number-placement.
It consists in filling a n2 × n2 grid, composed of n columns, n rows, and n subgrids, each one containing distinct integers from 1 to n2.
Such a puzzle belongs to the NP-complete collection of problems, to which there exist diverse exact and approximate methods able to solve it.
In this paper, we propose a new hybrid algorithm that smartly combines a classic tabu search procedure with the alldifferent global constraint from the constraint programming world.
The alldifferent constraint is known to be efficient for domain filtering in the presence of constraints that must be pairwise different, which are exactly the kind of constraints that Sudokus own.
This ability clearly alleviates the work of the tabu search, resulting in a faster and more robust approach for solving Sudokus.
We illustrate interesting experimental results where our proposed algorithm outperforms the best results previously reported by hybrids and approximate methods.
American Psychological Association (APA)
Soto, Ricardo& Crawford, Broderick& Galleguillos, Cristian& Paredes, Fernando& Norero, Enrique. 2015. A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles. Computational Intelligence and Neuroscience،Vol. 2015, no. 2015, pp.1-10.
https://search.emarefa.net/detail/BIM-1057679
Modern Language Association (MLA)
Soto, Ricardo…[et al.]. A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles. Computational Intelligence and Neuroscience No. 2015 (2015), pp.1-10.
https://search.emarefa.net/detail/BIM-1057679
American Medical Association (AMA)
Soto, Ricardo& Crawford, Broderick& Galleguillos, Cristian& Paredes, Fernando& Norero, Enrique. A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles. Computational Intelligence and Neuroscience. 2015. Vol. 2015, no. 2015, pp.1-10.
https://search.emarefa.net/detail/BIM-1057679
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1057679