Sudoku@vtaiwan

来自中国分布式计算总站
Sudoku@vtaiwan
[[Image:|220px|Sudoku@vtaiwan logo]]
Sudoku@vtaiwan logo
无屏保图形
无屏保图形
开发者 台湾国立交通大学
版本历史
计算程序 WindowsLinuxMac OS X
子项目
项目平台 BOINC 平台
项目类别 数学
项目状态 已结束
官方网址 Sudoku@vtaiwan
项目文献 分类:Sudoku@vtaiwan 相关文献
http://sudoku.nctu.edu.tw/rss_main.php 通过 RSS 获取项目新闻


Sudoku@vtaiwan是V-Taiwan的其中一个计划,它透过网路将电脑连结起来,一起对数独题目做运算。您可以透过下载与安装BOINC程式来参与此计划

在这数独计划中,我们提出了一些新的演算法并微调了Checker程式(Gary McGuire所撰写),我们成功地将原本预计要300,0000年单核运算时间才能解决的问题降低至只需约2400年单核运算时间,因此这个数独问题就很适合使用志愿型计算之BOINC系统来解决。部份新的演算法有写成论文并投稿至IWCG Workshop of nctu.edu.tw/ TAAI 2010 conference.


如何加入项目

该项目基于 BOINC 平台,简要的加入步骤如下(已完成的步骤可直接跳过):

  1. 下载并安装 BOINC 的客户端软件(官方下载页面程序下载
  2. 点击客户端简易视图下的“Add Project”按钮,或高级视图下菜单中的“工具->加入项目”,将显示向导对话框
  3. 点击下一步后在项目列表中找到并单击选中 Sudoku@vtaiwan 项目(如未显示该项目,则在编辑框中输入项目网址:http://sudoku.nctu.edu.tw/ ),然后点击下一步
  4. 输入您可用的电子邮件地址,并设置您在该项目的登录密码(并非您的电子邮件密码)
  5. 再次点击下一步,如项目服务器工作正常(并且有适合自身操作系统的计算程序),即已成功加入项目

更详细的加入方法说明,请访问 BOINC 新手指南BOINC 使用教程

本站推荐您加入 Team China 团队,请访问项目官方网站的 团队检索页面,搜索(Search)并进入 Team China 的团队页面,点击页面中的 Join 并输入用户登录信息即可加入!

在约2400年单核运算时间内解决数独之最小提示数的问题

数独是目前许多最受欢迎的游戏之一。从科学的角度,数独有一个很重要的问题是:在所有合法的数独初始盘面中,所具有的最小提示数为何?在2009年10月的时候,Gordon Royle已收集了49151组提示数为17的数独初始盘面,这49151组是已经去掉彼此重复的盘面(重复盘面指的是可以经由旋转、对称及数字对换所产生出来的盘面)。然而到目前为止,尚没有人能找到提示数为16的合法数独初始盘面,也没有人能证明不存在此种盘面,纵然大部份人相信这种盘面并不存在。这成为科学界的一项悬案。

Gary McGuire为爱尔兰大学的教授,提供了一个解决数独最小提示数问题的方法,并实作出checker.html CHECKER程式实作此方法。根据我们的实验显示,透过此程式并在配备为Intel(R) Xeon(R) E5520 @ 2.27GHz的单核CPU运算下需要30万年的CPU时间才能解决数独最小提示数的问题。他在2006年被科学人杂志访问时曾提到:「我们实在必须在理论上有所突破,才比较有可能搜寻出。我们必须缩减搜寻的空间,或是需要更棒的搜寻算则。」(来源:科学人杂志2006年7月号)

最近我们的研究提出了一些新的演算法并微调了CHECKER程式,最后达到了比原程式快128倍的效率。根据我们的实验数据显示,我们修改过后的程式可以在约2400年单核运算时间内解决数独最小提示数的问题,因此这个问题就更有机会达成解出的任务。比如说,若透过BOINC系统有2400核CPU在帮我们做运算,则我们可以用一年的时间解掉此问题。而若是有24000核CPU帮我们做运算,则可以在36天内解掉它。


在这里我们欢迎大家共同来参与解决此数独悬案,感谢您捐出电脑多余的CPU计算资源给sudoku@vtaiwan,您的贡献对解决此问题是一个很大的帮助!

让我们一起创造历史吧!


V-TAIWAN 计划

V-Taiwan (或称为Volunteer computing in Taiwan) 是一个志愿型计算的计划,其经费来源是由台湾国家科学委员会(NSC)所支持。这个计划是用志愿型计算来帮对局程式做运算。截至目前为止我们已经成功地用志愿型计算解决了许多六子棋的开局问题,其中包括了有名的米老鼠开局(因像米老鼠的脸而得名),相关细节可参考底下的参考文献。


相关文献

Boinc Icon.png伯克利开放式网络计算平台BOINC
· ·
生命科学类项目 Computational Structural Biology · DrugDiscovery@Home · GPUGRID · Malariacontrol.net · RALPH@home (Alpha内测项目)· RNA World · Rosetta@home · The Lattice Project
地球科学类项目 Climateprediction.net · Quake-Catcher Network Seismic Monitoring
人工智能类项目 MindModeling@Home
天文学项目 Astropulse · Cosmology@Home · MilkyWay@home · SETI@home · SETI@home/AstroPulse Beta (Beta公测项目)· Asteroids@home
物理化学类项目 Einstein@Home · Hydrogen@Home · Leiden Classical · LHC@home · QMC@Home
数学类项目 Collatz Conjecture · NFS@Home · primaboinca · PrimeGrid · SZTAKI Desktop Grid · WEP-M+2 Project
密码类项目 Enigma@Home · Moo! Wrapper
艺术类项目 BURP
多种应用的项目 CAS@home · World Community Grid · Yoyo@home
与 BOINC 平台相关的项目 BOINC Alpha Test · Pirates@home · WUProp@Home
已结束/暂停/合并的项目 ABC@home · AlmereGrid Boinc Grid · APS@Home · AQUA@home · BBC Climate Change Experiment · Biochemical Library · BRaTS@Home · Cels@Home · Chess960@Home · CPDN Beta · DepSpid · DistrRTgen · DNA@home · DNETC@HOME · Docking@Home · Drug@Home · DynaPing · EDGeS@Home · eOn: Long timescale dynamics · Evo@home · Eternity2.fr · FreeHAL@home · Goldbach's Conjecture Project · Ibercivis · Magnetism@home · Mersenne@home · Mopac@home · MilestoneRSA · MFluids@Home · Nano-Hive@home · NQueens Project · Orbit@Home · Open Rendering Environment · POEM@HOME · PicEvolvr.com] · Predictor@home · QuantumFIRE alpha · Ramsey@Home ·RamseyX · Rectilinear Crossing Number · Renderfarm.fi · RSA Lattice Siever (2.0) · Seasonal Attribution Project · SHA-1 Collision Search Graz · SIMAP · SLinCA@Home · Spinhenge@home · Sudoku@vtaiwan · Superlink@Technion · TANPAKU · Virtual Prairie · Virus Respiratorio Sincitial · XtremLab · Zivis
BOINC 相关的工具 BOINCstats BAM! · BOINC Translation Services · BOINC TThrottle