Sudoku@vtaiwan
|
sudoku@vtaiwan | |
|---|---|
Sudoku@vtaiwan logo | |
无屏保图形 | |
| 开发者 | 台湾国立交通大学 |
| 版本历史 | |
| 运算平台 | 
|
| 项目平台 | BOINC |
| 程序情况 | |
| 任务情况 | |
| 项目状态 | 运行中/开放注册 |
| 项目类别 | 数学类 |
| 优化程序 | 无 |
| 计算特点 | CPU密集： |
| 官方网址 | Sudoku@vtaiwan |
|
[{{{rss}}} 通过 RSS 获取项目新闻] |
sudoku@vtaiwan是V-Taiwan的其中一個計劃，它透過網路將電腦連結起來，一起對數獨題目做運算。您可以透過下載與安裝BOINC程式來參與此計劃。
在這數獨計劃中，我們提出了一些新的演算法並微調了Checker程式(Gary McGuire所撰寫)，我們成功地將原本預計要300,0000年單核運算時間才能解決的問題降低至只需約2400年單核運算時間，因此這個數獨問題就很適合使用志願型計算之BOINC系統來解決。部份新的演算法有寫成論文並投稿至IWCG Workshop of 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程式實作此方法。根據我們的實驗顯示，透過此程式並在配備為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, "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.
