Solving the Minimum Sudoku Poblem

Abstract

It is known that solving the minimum Sudoku problem can be done by checking 5,472,730,538 essentially different Sudoku grids, which can be checked independently or in parallel. However, the program Checker, written by McGuire, requires about 311 thousand years on one-core CPU to check these grids completely, according to our experimental analysis. This paper proposes a new algorithm, named a disjoint minimal unavoidable set (DMUS) algorithm, to help solve the minimum Sudoku problem. Then, incorporate the algorithm into the program and further tuning the program code. In our experiment, the performance was greatly improved by a factor of 128.67. Hence, the improved program by us requires about 2417.4 years only. Thus, it becomes feasible and optimistic to solve this program using a volunteer computing system, such as BOINC.