Z Wiki B@P


sudoku@vtaiwan jest jednym z projektów V-Taiwan które wykorzystuje komputery podłączone do internetu by wykonywać obliczenia zawiązane z sudoku.

W tym projekcie tworzone są nowe techniki które następnie są wykorzystywane do modyfikacji programu Checker (napisanego przez garry'ego McGuire).

Udało nam się zmniejszyć całkowity oczekiwany czas przetwarzania z 300tys lat per rdzeń do 2417 lat per rdzeń. To pozwala na zastosowanie BOINC do rozwiazywania sudoku. Część z nowych technik jest opisana w dokumencie z warsztatów IWCG z konferencji TAAI 2010.


Sudoku is one of the most popular games nowadays. One important question intriguing to scientists is the minimum number of clues in Sudoku puzzles with unique solutions. As of October 2009, Gordon Royle collected 49151 17-clue puzzles, among which none are isomorphic to one another (by isomorphism, we mean to translate the puzzle by simply rotating, mirroring or digits-switching). However, so far, none successfully found 16-clue puzzles or gave a proof that no 16-clue puzzles exist, which most people believe.

Gary McGuire, Professor of the National University of Ireland, presented a search approach to solve 16-clue puzzles. He also developed a program, called CHECKER, for trying to solve it. According to our experi mental analysis, the program requires about 300,000 years on a one-core computer equipped with CPU, Intel(R) Xeon(R) E5520 @ 2.27GHz. (Note that we will use one core to indicate the computing power.) His final comment was 'We really need a breakthrough in our understanding to make it feasible to search all. We either need to reduce the search space or find a much better algorithm for searching.' (see Scientific American, 2006)

In our recent research, we proposed some new algorithm and also fine-tuned the code to speed up by a factor of 128. Thus, according to our experiments, our new program can solve it with one core in about 2400 years. Thus, it becomes feasible to solve the open problem. For example, if 2400 cores via BOINC are used, the open problem can be solved in one year; and if 24000 cores are used, it can in about 36 days.

Hereb y, we sincerely thank you for donating your computing resources to sudoku@vtaiwan. Your contribution will greatly help solve this open problem.

Let us make the history together!


V-Taiwan or Volunteer-Taiwan is a volunteer computing project financially supported by the National Science Council (NSC) of Taiwan. The project, to be announced over the Internet, is to apply volunteer computing to computer game applications. Currently, we have successfully used volunteer computing to solve many Connect6 openings as reported in the papers below. Among these openings, a popular one was named Mickey Mouse Opening (since the opening looks like a Mickey Mouse face).


   * I-Chen Wu, Chingping Chen, Ping-Hung Lin, Guo-Zhan Huang, Lung-Ping Chen, Der-Johng Sun, Yi-Chih Chan, and Hsin-Yun Tsou, "A Volunteer-Computing-Based Grid Environment for Connect6 Applications", The 12th IEEE International Conference on Computational Science and Engineering (CSE-09), August 29-31, Vancouver, Canada, 2009.
   * I-Chen Wu, H.-H. Lin, P.-H. Lin, D.-J. Sun, Y.-C. Chan and B.-T. Chen, "Job-Level Proof-Number Search for Connect6", The International Conference on Computers and Games (CG 2010), Kanazawa, Japan, September 2010.
   * I-Chen Wu and Ping-Hung Lin, "Relevance-Zone-Oriented Proof Search for Connect6", the IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 3, September 2010.
   * H.-H. Lin, I-Chen Wu, "Solving the Minimum Sudoku Problem", The International Workshop on Computer Games (IWCG 2010), Hsinchu, Taiwan, November 2010.

Przydatne linki

Strona główna projektu

Twoje konto