“Sudoku@vtaiwan”的版本间的差异

来自中国分布式计算总站
跳转至: 导航搜索
(新建条目)
 
(已结束。)
 
(未显示3个用户的5个中间版本)
第1行: 第1行:
{{Infobox Project
+
{{Project
| name =sudoku@vtaiwan
+
|name=Sudoku@vtaiwan
| logo =
+
|logo=
| screenshot =
+
|developer=[http://www.nctu.edu.tw/ 台湾国立交通大学]
| caption =无屏保图形
+
|released=
| developer =[http://www.nctu.edu.tw/ 台湾国立交通大学]
+
|app={{app/Windows}}{{app/Linux}}{{app/Mac}}
| released =
+
|platform={{platform/BOINC}}
| operating system =[[Image:Windows.png]]
+
|subproject=
| platform =[[BOINC]]
+
|status=已结束
| program info =
+
|genre={{genre/数学}}
| work unit info =
+
|website=http://sudoku.nctu.edu.tw/
| status =运行中/开放注册
+
|rss=http://sudoku.nctu.edu.tw/rss_main.php
| genre =数学类
 
| optimization =
 
| website =http://sudoku.nctu.edu.tw/
 
 
}}
 
}}
[[sudoku@vtaiwan]]是V-Taiwan的其中一個計劃,它透過網路將電腦連結起來,一起對數獨題目做運算。您可以透過[http://sudokuathome.nctu.edu.tw/joomla/index.php?option=com_content&view=article&id=48&Itemid=57&lang=tw 下載與安裝BOINC程式來參與此計劃]。
 
  
在這數獨計劃中,我們提出了一些新的演算法並微調了[http://www.math.ie/checker.html Checker]程式([http://www.math.ie/checker.html Gary McGuire]所撰寫),我們成功地將原本預計要300,0000年單核運算時間才能解決的問題降低至只需約2400年單核運算時間,因此這個數獨問題就很適合使用志願型計算之[http://boinc.berkeley.edu/ BOINC]系統來解決。部份新的演算法有寫成論文並投稿至[http://taai2010.nctu.edu.tw/index.php?option=com_content&view=article&id=56&Itemid=74 IWCG Workshop] of [http://taai2010.nctu.edu.tw/ TAAI 2010 conference].
+
[[Sudoku@vtaiwan]]是V-Taiwan的其中一个计划,它透过网路将电脑连结起来,一起对数独题目做运算。您可以透过[http://sudokuathome.nctu.edu.tw/joomla/index.php?option=com_content&view=article&id=48&Itemid=57&lang=tw 下载与安装BOINC程式来参与此计划]。
 +
 
 +
在这数独计划中,我们提出了一些新的演算法并微调了[http://www.math.ie/checker.html Checker]程式([http://www.math.ie/checker.html Gary McGuire]所撰写),我们成功地将原本预计要300,0000年单核运算时间才能解决的问题降低至只需约2400年单核运算时间,因此这个数独问题就很适合使用志愿型计算之[http://boinc.berkeley.edu/ BOINC]系统来解决。部份新的演算法有写成论文并投稿至[http://taai2010.nctu.edu.tw/index.php?option=com_content&view=article&id=56&Itemid=74 IWCG Workshop] of [http://taai2010. nctu.edu.tw/ TAAI 2010 conference].
  
 
{{JoinBoincProject
 
{{JoinBoincProject
|Project=sudoku@vtaiwan
+
|Project=Sudoku@vtaiwan
 
|URL=http://sudoku.nctu.edu.tw/
 
|URL=http://sudoku.nctu.edu.tw/
 
}}
 
}}
  
==在約2400年單核運算時間內解決數獨之最小提示數的問題==
+
==在约2400年单核运算时间内解决数独之最小提示数的问题==
  
數獨是目前許多最受歡迎的遊戲之一。從科學的角度,數獨有一個很重要的問題是:在所有合法的數獨初始盤面中,所具有的最小提示數為何? 在2009年10月的時候,[http://mapleta.maths.uwa.edu.au/~gordon/sudokupat.php Gordon Royle]已收集了49151組提示數為17的數獨初始盤面,這49151組是已經去掉彼此重複的盤面(重複盤面指的是可以經由旋轉、對稱及數字對換所產生出來的盤面)。然而到目前為止,尚沒有人能找到提示數為16的合法數獨初始盤面,也沒有人能證明不存在此種盤面,縱然大部份人相信這種盤面並不存在。這成為科學界的一項懸案。
+
数独是目前许多最受欢迎的游戏之一。从科学的角度,数独有一个很重要的问题是:在所有合法的数独初始盘面中,所具有的最小提示数为何?在2009年10月的时候,[http://mapleta.maths.uwa.edu.au/~gordon/sudokupat.php Gordon Royle]已收集了49151组提示数为17的数独初始盘面,这49151组是已经去掉彼此重复的盘面(重复盘面指的是可以经由旋转、对称及数字对换所产生出来的盘面)。然而到目前为止,尚没有人能找到提示数为16的合法数独初始盘面,也没有人能证明不存在此种盘面,纵然大部份人相信这种盘面并不存在。这成为科学界的一项悬案。
  
[http://www.math.ie/checker.html Gary McGuire]為愛爾蘭大學的教授,提供了一個解決數獨最小提示數問題的方法,並實作出[http://www.math.ie/checker.html CHECKER]程式實作此方法。根據我們的實驗顯示,透過此程式並在配備為Intel(R) Xeon(R) E5520 @ 2.27GHz的單核CPU運算下需要30萬年的CPU時間才能解決數獨最小提示數的問題。他在2006年被[http://www.scientificamerican.com/ 科學人雜誌]訪問時曾提到:「我們實在必須在理論上有所突破,才比較有可能搜尋出。我們必須縮減搜尋的空間,或是需要更棒的搜尋算則。」(來源:[http://www.scientificamerican.com/ 科學人雜誌]2006年7月號)
+
[http://www.math.ie/checker.html Gary McGuire]为爱尔兰大学的教授,提供了一个解决数独最小提示数问题的方法,并实作出[http://www.math.ie/ checker.html CHECKER]程式实作此方法。根据我们的实验显示,透过此程式并在配备为Intel(R) Xeon(R) E5520 @ 2.27GHz的单核CPU运算下需要30万年的CPU时间才能解决数独最小提示数的问题。他在2006年被[http://www.scientificamerican.com/ 科学人杂志]访问时曾提到:「我们实在必须在理论上有所突破,才比较有可能搜寻出。我们必须缩减搜寻的空间,或是需要更棒的搜寻算则。」(来源:[http://www.scientificamerican.com/ 科学人杂志]2006年7月号)
  
最近我們的研究提出了一些新的演算法並微調了[http://www.math.ie/checker.html CHECKER]程式,最後達到了比原程式快128倍的效率。根據我們的實驗數據顯示,我們修改過後的程式可以在約2400年單核運算時間內解決數獨最小提示數的問題,因此這個問題就更有機會達成解出的任務。比如說,若透過BOINC系統有2400核CPU在幫我們做運算,則我們可以用一年的時間解掉此問題。而若是有24000核CPU幫我們做運算,則可以在36天內解掉它。
+
最近我们的研究提出了一些新的演算法并微调了[http://www.math.ie/checker.html CHECKER]程式,最后达到了比原程式快128倍的效率。根据我们的实验数据显示,我们修改过后的程式可以在约2400年单核运算时间内解决数独最小提示数的问题,因此这个问题就更有机会达成解出的任务。比如说,若透过BOINC系统有2400核CPU在帮我们做运算,则我们可以用一年的时间解掉此问题。而若是有24000核CPU帮我们做运算,则可以在36天内解掉它。
  
  
在這裡我們歡迎大家共同來參與解決此數獨懸案,感謝您捐出電腦多餘的CPU計算資源給sudoku@vtaiwan,您的貢獻對解決此問題是一個很大的幫助!
+
在这里我们欢迎大家共同来参与解决此数独悬案,感谢您捐出电脑多余的CPU计算资源给sudoku@vtaiwan,您的贡献对解决此问题是一个很大的帮助!
  
'''讓我們一起創造歷史吧!'''
+
'''让我们一起创造历史吧!'''
  
  
==V-TAIWAN 計劃==
+
==V-TAIWAN 计划==
V-Taiwan (或稱為 Volunteer computing in Taiwan) 是一個志願型計算的計劃,其經費來源是由[http://web1.nsc.gov.tw/ 台灣國家科學委員會](NSC)所支持。 這個計劃是用志願型計算來幫對局程式做運算。截至目前為止我們已經成功地用志願型計算解決了許多[http://www.connect6.org/web/index.php?lang=en 六子棋]的開局問題,其中包括了有名的米老鼠開局(因像米老鼠的臉而得名),相關細節可參考底下的參考文獻。
+
V-Taiwan (或称为Volunteer computing in Taiwan) 是一个志愿型计算的计划,其经费来源是由[http://web1.nsc.gov.tw/ 台湾国家科学委员会](NSC)所支持。这个计划是用志愿型计算来帮对局程式做运算。截至目前为止我们已经成功地用志愿型计算解决了许多[http://www.connect6.org/web/index.php?lang=en 六子棋]的开局问题,其中包括了有名的米老鼠开局(因像米老鼠的脸而得名),相关细节可参考底下的参考文献。
  
 
   
 
   
==相關文獻==
+
==相关文献==
* I-Chen Wu, Chingping Chen, Ping-Hung Lin, Guo-Zhan Huang, Lung-Ping Chen, Der-Johng Sun, Yi-Chih Chan, and Hsin-Yun Tsou, "[http://sudoku.nctu.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, Chingping Chen, Ping-Hung Lin, Guo-Zhan Huang, Lung-Ping Chen, Der-Johng Sun, Yi-Chih Chan, and Hsin-Yun Tsou, "[http://sudoku.nctu. 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, "[http://sudoku.nctu.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, H.-H. Lin, P.-H. Lin, D.-J. Sun, Y.-C. Chan and B.-T. Chen, "[http://sudoku.nctu .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, "[http://sudoku.nctu.edu.tw/papers/TCIAIG-05518405-rzone.pdf Relevance-Zone-Oriented Proof Search for Connect6]", the IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 3, September 2010.
 
* I-Chen Wu and Ping-Hung Lin, "[http://sudoku.nctu.edu.tw/papers/TCIAIG-05518405-rzone.pdf 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.
 
* H.-H. Lin, I-Chen Wu, "Solving the Minimum Sudoku Problem", The International Workshop on Computer Games (IWCG 2010), Hsinchu, Taiwan, November 2010.
  
 
{{BOINC topics}}
 
{{BOINC topics}}
 
+
[[Category:以结束项目]]
 
 
[[Category:分布式计算项目]][[Category:数学类项目]][[Category:BOINC 平台上的项目]]
 

2017年12月6日 (三) 13:40的最新版本

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
游戏类项目 Minecraft@Home
多种应用的项目 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