19-06-2012, 12:53 PM
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.
INTRODUCTION
Sudoku is a popular puzzle game invented by Harold
Garns (cf. [9]) in 1979 and has been popular and printed in
daily newspapers, magazines, and websites since 2005. A
Sudoku puzzle is played on a 9