標題: 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://hdl.handle.net/11536/16203
ISSN: 1389-6911
期刊: ICGA JOURNAL
Volume: 34
Issue: 4
結束頁: 191
顯示於類別:期刊論文