“Sudoku@vtaiwan”的版本间差异
Zhouxiaobo（讨论 | 贡献） 小 （已结束。） |
Zhouxiaobo（讨论 | 贡献） 小 （已结束。） |
||
| 第7行： | 第7行： | ||
|platform={{platform/BOINC}} | |platform={{platform/BOINC}} | ||
|subproject= | |subproject= | ||
| − | |status= | + | |status=已结束 |
|genre={{genre/数学}} | |genre={{genre/数学}} | ||
|website=http://sudoku.nctu.edu.tw/ | |website=http://sudoku.nctu.edu.tw/ | ||
2017年12月6日 (三) 13:40的最新版本
Sudoku@vtaiwan是V-Taiwan的其中一个计划，它透过网路将电脑连结起来，一起对数独题目做运算。您可以透过下载与安装BOINC程式来参与此计划。
在这数独计划中，我们提出了一些新的演算法并微调了Checker程式(Gary McGuire所撰写)，我们成功地将原本预计要300,0000年单核运算时间才能解决的问题降低至只需约2400年单核运算时间，因此这个数独问题就很适合使用志愿型计算之BOINC系统来解决。部份新的演算法有写成论文并投稿至IWCG Workshop of nctu.edu.tw/ TAAI 2010 conference.
如何加入项目
该项目基于 BOINC 平台，简要的加入步骤如下（已完成的步骤可直接跳过）：
- 下载并安装 BOINC 的客户端软件（官方下载页面或程序下载）
- 点击客户端简易视图下的“Add Project”按钮，或高级视图下菜单中的“工具->加入项目”，将显示向导对话框
- 点击下一步后在项目列表中找到并单击选中 Sudoku@vtaiwan 项目（如未显示该项目，则在编辑框中输入项目网址：http://sudoku.nctu.edu.tw/ ），然后点击下一步
- 输入您可用的电子邮件地址，并设置您在该项目的登录密码（并非您的电子邮件密码）
- 再次点击下一步，如项目服务器工作正常（并且有适合自身操作系统的计算程序），即已成功加入项目
更详细的加入方法说明，请访问 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)所支持。这个计划是用志愿型计算来帮对局程式做运算。截至目前为止我们已经成功地用志愿型计算解决了许多六子棋的开局问题，其中包括了有名的米老鼠开局(因像米老鼠的脸而得名)，相关细节可参考底下的参考文献。
相关文献
- I-Chen Wu, Chingping Chen, Ping-Hung Lin, Guo-Zhan Huang, Lung-Ping Chen, Der-Johng Sun, Yi-Chih Chan, and Hsin-Yun Tsou, "edu.tw/papers/CSE2009_proceedings.pdf 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, ".edu.tw/papers/JL-PNS-final-4.pdf 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.
