Dear all volunteers,
We are happy to announce that this BOINC project (sudoku@vtaiwan) ends with no 16-clue Sudoku puzzles found, on September 5, 2013, after running about 2 years and 8 months. The result confirms that obtained by McGuire: The minimum Sudoku problem is solved. We would like to express our gratitude to the community for contribution to this project; we could not finish it without your enthusiasm and support.
The total credit (in BOINC) is 732,404,168, equivalent to 3296.5 core-year, more than our early estimation, 2413 core-year. The difference could be due to the following reasons:
lSome credits were added back, after we encountered a crash on Jan 3, 2011. Note that the project actually started on October 27, 2010. For the crash, we restarted it from January 3rd, 2011.
lSome other overhead.
The total number of registered participants is 31129, and the total number of participants who have contributed is 4378.
lThe accounts "stanleylin", nchcalps, "david", "syhan", "c00ctn00" are from the computing resources of NCHC (National Center for High-performance Computing, Taiwan).
lThe account "Hicloud@cyc" is from the computing resources of HiCloud (Chunghwa Telecom, Taiwan).
After this project ends, we do have plans for our next projects or volunteer projects, e.g., "go@vtaiwan", which aims to solve 7x7 Go or 9x9 Go positions. Note that the game-tree complexities of 7x7 Go are about 1047, between Checkers (1031, solved in 2007) and Othello (1058, not solved yet). However, they are not yet ready at this moment. When ready, we will release details regarding the new project. We would also deeply appreciate your continued support for new projects in advance.
Thank you very much.
The team from sudoku@vtaiwan
(The source code is here.)
As the project is approaching its end (up to 99%), we would like to express our gratitude to the community; we could not have come this far without your enthusiasm and support. From the current progress, it is expected that this project will be finished soon (by the end of this month).
Here are some more points that we would like to address.
First, we would like to thank you all deeply for your contribution to this project.
Second, we would like to report the current statistics of the project.
lNo 16-clue puzzles are found yet.
lThe total credit is 727,026,864, equivalent to 3272.3 core-year.
Our early estimation was 2413 core-year. The difference could be due to the following reasons:
lWe encountered crash Jan 3, 2011. Some credits (before the crash) were added.
lClearly have some other overhead.
lFor the 5.4 billion primitive grids, we split them into 52 groups.
The statistics of them will be reported later.
lThe total number of registered users so far: 29107.
The total number of users who have contributed: 4360.
We will revise the above data again or report more soon after our project is finished.
Third, some of you have asked whether we have next projects and what they are. Yes, we do have plans for our next BOINC projects or volunteer projects. However, they are not yet ready at this moment. When ready, we will release details regarding our new project, which aims to solve 7x7 Go or 9x9 Go positions. Note that the game-tree complexities of 7x7 Go are about 1047, between Checkers (1031, solved in 2007) and Othello (1058, not solved yet).
We would also deeply appreciate your continued support in advance.
Thank you very much again.
The team from sudoku@vtaiwan
Dear all volunteers, our sudoku@vtaiwan system crashed around Jan 3rd, 2011. We would like to apologize to you all for the crash.
We have recovered our system. However, we still lost the login record of volunteers, including account/password, though we backup the credits of all volunteers. Since we cannot but reset the volunteer credit system, we need your help to restore your credits as follows.
1. Detach the old "sudoku@vtaiwan" project entry (in the projects folder), and then
2. attach new project "http://sudoku.nctu.edu.tw" project as a "new user", but remember to use the same name.
As long as you can register with the same name as before, we can restore your credits by adding the current saved credits back to the new system later.
Sorry for any inconvenience. And thank you very much for your continuous support.
sudoku@vtaiwan is one of V-Taiwan projects that uses Internet-connected computers to do research in sudoku. You can participate as a volunteer by downloading and running programs on your computer.
In this project, we develops new techniques and used them to modify the program Checker (written by Gary McGuire). We successfully reduced the total expected computation time from 300,000 years per core to 2,417 years per core. This makes it more feasible and reasonable to use BOINC to solve Sudoku. Some of these new techniques are described in a paper in the IWCG Workshop of TAAI 2010 conference.
SOLVE 16-CLUE SUDOKU OPEN PROBLEM IN ABOUT 2400 YEAR-CORE
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.
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 fined tune the code to speed up by a factor of 128, and the code can be downloaded here. According to our experiments, our new program can solve it with one core in about 2417 years. Thus, it becomes feasible to solve the open problem. For example, if 2417 cores via BOINC are used, the open problem can be solved in one year; and if 24170 cores are used, it can in about 36 days. (Our benchmark can be downloaded here, and here are two sets, 100 grids and 10000 grids, for verification.)
Hereby, we sincerely thank you for donating your computing resources to sudoku@vtaiwan. Your contribution will greatly help solve this open problem.
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.