Name
Abstract | ||
|---|---|---|
The Sudoku problem consists in filling a n^2xn^2 grid so that each column, row and each one of the nxn sub-grids contain different digits from 1 to n^2. 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1155/2015/286354 | Computational Intelligence and Neuroscience |
Keywords | Field | DocType |
tabu search,integrated procedure,non-trivial problem,sudoku problem,different incomplete search method,classic tabu search procedure,best result,ac3-tabu search algorithm,sudoku puzzle,different digit,incomplete search method | Row,Integer,Pairwise comparison,Hybrid algorithm,Computer science,Constraint programming,Filter (signal processing),Algorithm,Artificial intelligence,Grid,Tabu search,Machine learning | Journal |
Volume | ISSN | Citations |
2015 | 1687-5265 | 15 |
PageRank | References | Authors |
0.96 | 24 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ricardo Soto | 1 | 194 | 47.59 |
| Broderick Crawford | 2 | 446 | 73.74 |
| Cristian Galleguillos | 3 | 30 | 5.96 |
| Eric Monfroy | 4 | 579 | 63.05 |
| Fernando Paredes | 5 | 230 | 27.21 |