首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles
  • 本地全文:下载
  • 作者:Ricardo Soto ; Broderick Crawford ; Cristian Galleguillos
  • 期刊名称:Computational Intelligence and Neuroscience
  • 印刷版ISSN:1687-5265
  • 电子版ISSN:1687-5273
  • 出版年度:2015
  • 卷号:2015
  • DOI:10.1155/2015/286354
  • 出版社:Hindawi Publishing Corporation
  • 摘要:The Sudoku problem is a well-known logic-based puzzle of combinatorial number-placement. It consists in filling a grid, composed of columns, rows, and subgrids, each one containing distinct integers from 1 to . 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.
国家哲学社会科学文献中心版权所有