标题: AN EFFICIENT APPROACH TO SOLVING THE MINIMUM SUDOKU PROBLEM
作者: Lin, Hung-Hsuan
Wu, I-Chen
资讯工程学系
Department of Computer Science
公开日期: 1-十二月-2011
摘要: Since Sudoku was invented, it has been an open problem to find the minimum-clue Sudoku puzzles, also commonly called the minimum Sudoku problem. Solving the problem can be done by checking 5,472,730,538 essentially different Sudoku grids independently or in parallel. In the past, the program CHECKER, written by McGuire, required about 311 thousand years on one-core CPU to check these grids completely, according to our experimental analysis. This paper is to propose a more efficient approach to solving this problem. We design a new algorithm, named disjoint minimal unavoidable set (DMUS) algorithm, to help solve the minimum Sudoku problem more efficiently. After incorporating the algorithm into the program and further tuning the program code, our experiments showed that the performance was greatly improved by a factor of 128.67. Hence, it is estimated that it only takes about 2417 years to solve the problem. Thus, it becomes feasible and optimistic to solve this problem by using a volunteer computing system, such as BOINC.(2,3)
URI: http://dx.doi.org/10.3233/ICG-2011-34403
http://hdl.handle.net/11536/16203
ISSN: 1389-6911
DOI: 10.3233/ICG-2011-34403
期刊: ICGA JOURNAL
Volume: 34
Issue: 4
起始页: 191
结束页: 208
显示于类别:Articles


文件中的档案:

  1. ef19eb00710c1da51eed5cc362193358.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.