完整後設資料紀錄
DC 欄位語言
dc.contributor.authorLin, Hung-Hsuanen_US
dc.contributor.authorWu, I-Chenen_US
dc.date.accessioned2019-04-03T06:36:11Z-
dc.date.available2019-04-03T06:36:11Z-
dc.date.issued2011-12-01en_US
dc.identifier.issn1389-6911en_US
dc.identifier.urihttp://dx.doi.org/10.3233/ICG-2011-34403en_US
dc.identifier.urihttp://hdl.handle.net/11536/16203-
dc.description.abstractSince 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.isoen_USen_US
dc.titleAN EFFICIENT APPROACH TO SOLVING THE MINIMUM SUDOKU PROBLEMen_US
dc.typeArticleen_US
dc.identifier.doi10.3233/ICG-2011-34403en_US
dc.identifier.journalICGA JOURNALen_US
dc.citation.volume34en_US
dc.citation.issue4en_US
dc.citation.spage191en_US
dc.citation.epage208en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000302737000002en_US
dc.citation.woscount4en_US
顯示於類別:期刊論文


文件中的檔案:

  1. ef19eb00710c1da51eed5cc362193358.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。