SETI.USA Forums - Sudoku@vtaiwan
  • Sudoku@vtaiwan

    by Published on 09-03-11 06:02 AM  Number of Views: 206 



    Description: 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. Thus, 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.)


    Institution: National Chiao Tung University Taiwan.


    Official Launch: 21-10-2010.


    Project Status: Active.


    Home Page: http://sudoku.nctu.edu.tw/joomla/


    Cliant Programs: The project supports the following Applications.
    Windows 32 and 64bits.
    Linux 32 and 64 bits.
    Mac OS.


    Statistics View Detailed Information and statistics on Team SETI.USA Here


    Current Team Scores:

  • Calendar

    October   2014
    Su Mo Tu We Th Fr Sa
    1 2 3 4
    5 6 7 8 9 10 11
    12 13 14 15 16 17 18
    19 20 21 22 23 24 25
    26 27 28 29 30 31