کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
382591 | 660772 | 2013 | 5 صفحه PDF | دانلود رایگان |
• We propose a new hybrid AC3-tabu search algorithm for Sudoku problems.
• We perform experiments considering easy, medium, and hard Sudokus.
• The approach generally outperforms the best results reached by incomplete search.
The Sudoku problem consists in filling a n2×n2n2×n2 grid so that each column, row and each one of the n×nn×n sub-grids contain different digits from 1 to n2n2. 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.
Journal: Expert Systems with Applications - Volume 40, Issue 15, 1 November 2013, Pages 5817–5821