Note: [1] Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan. Email: stanleylin@java.csie.nctu.edu.tw, icwu@csie.nctu.edu.tw.
Abstract: 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.
DOI: 10.3233/ICG-2011-34403
Journal: ICGA Journal, vol. 34, no. 4, pp. 191-208, 2011
