标题: | 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 |
文件中的档案:
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.