Full metadata record
DC FieldValueLanguage
dc.contributor.authorLin, Hung-Hsuanen_US
dc.contributor.authorWu, I-Chenen_US
dc.date.accessioned2018-08-21T05:56:41Z-
dc.date.available2018-08-21T05:56:41Z-
dc.date.issued2010-01-01en_US
dc.identifier.issn2376-6816en_US
dc.identifier.urihttp://dx.doi.org/10.1109/TAAI.2010.77en_US
dc.identifier.urihttp://hdl.handle.net/11536/146523-
dc.description.abstractIt 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.en_US
dc.language.isoen_USen_US
dc.subjectSudokuen_US
dc.subject16-clueen_US
dc.subject17-clueen_US
dc.subjectMinimum Sudokuen_US
dc.subjectCheckeren_US
dc.subjectBOINCen_US
dc.titleSolving the Minimum Sudoku Poblemen_US
dc.typeProceedings Paperen_US
dc.identifier.doi10.1109/TAAI.2010.77en_US
dc.identifier.journalINTERNATIONAL CONFERENCE ON TECHNOLOGIES AND APPLICATIONS OF ARTIFICIAL INTELLIGENCE (TAAI 2010)en_US
dc.citation.spage456en_US
dc.citation.epage461en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000399726300069en_US
Appears in Collections:Conferences Paper