Solving the minimum Sudoku poblem

Hung Hsuan Lin*, I-Chen Wu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010
Pages456-461
Number of pages6
DOIs
StatePublished - 1 Dec 2010
Event2010 15th Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010 - Hsinchu, Taiwan
Duration: 18 Nov 201020 Nov 2010

Publication series

NameProceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010

Conference

Conference2010 15th Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010
CountryTaiwan
CityHsinchu
Period18/11/1020/11/10

Keywords

  • 16-clue
  • 17-clue
  • BOINC
  • Checker
  • Minimum Sudoku
  • Sudoku

Fingerprint Dive into the research topics of 'Solving the minimum Sudoku poblem'. Together they form a unique fingerprint.

Cite this