Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lin, Hung-Hsuan | en_US |
dc.contributor.author | Wu, I-Chen | en_US |
dc.date.accessioned | 2019-04-03T06:36:11Z | - |
dc.date.available | 2019-04-03T06:36:11Z | - |
dc.date.issued | 2011-12-01 | en_US |
dc.identifier.issn | 1389-6911 | en_US |
dc.identifier.uri | http://dx.doi.org/10.3233/ICG-2011-34403 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/16203 | - |
dc.description.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.(2,3) | en_US |
dc.language.iso | en_US | en_US |
dc.title | AN EFFICIENT APPROACH TO SOLVING THE MINIMUM SUDOKU PROBLEM | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.3233/ICG-2011-34403 | en_US |
dc.identifier.journal | ICGA JOURNAL | en_US |
dc.citation.volume | 34 | en_US |
dc.citation.issue | 4 | en_US |
dc.citation.spage | 191 | en_US |
dc.citation.epage | 208 | en_US |
dc.contributor.department | 資訊工程學系 | zh_TW |
dc.contributor.department | Department of Computer Science | en_US |
dc.identifier.wosnumber | WOS:000302737000002 | en_US |
dc.citation.woscount | 4 | en_US |
Appears in Collections: | Articles |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.