A hybrid AC3-tabu search algorithm for solving Sudoku puzzles

RICARDO JAVIER SOTO DE GIORGIS, BRODERICK CRAWFORD LABRIN, Cristian Galleguillos, Eric Monfroy, Fernando Paredes

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

The 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.

Original languageEnglish
Pages (from-to)5817-5821
Number of pages5
JournalExpert Systems with Applications
Volume40
Issue number15
DOIs
StatePublished - 17 Jun 2013

Keywords

  • Constraint satisfaction
  • Metaheuristics
  • Sudoku
  • Tabu search

Fingerprint Dive into the research topics of 'A hybrid AC3-tabu search algorithm for solving Sudoku puzzles'. Together they form a unique fingerprint.

Cite this