最新消息

參與者您好，我們的 sudoku@vtaiwan 系統在 2011年1月3日左右當掉了。我們為這次的當機深感抱歉。

我們已經將系統做回復，儘管我們備份了所有參與者的credit資料，我們仍失去了參與者的登入記錄，其中包含帳號與密碼等等。我們不得不將志願型系統重設，因此我們需要透過您以下的幫忙來回復您的credit資料：

1. 先退出"sudoku@vtaiwan" 計劃，然後
2. 再次加入計劃 "http://sudoku.nctu.edu.tw"，並做為一名新使用者註冊，但記得請使用相同的名字。

若您能用與以前相同的名字做註冊，則我們能將舊有您的credit資料回復至您新的帳號上。

對於造成不便深感歉意。同時也感謝您的繼續支持。

Sudoku@vtaiwan 團隊，2011年1月14日。

SUDOKU@VTAIWAN 計劃

sudoku@vtaiwan 是 V-Taiwan 的其中一個計劃，它透過網路將電腦連結起來，一起對數獨做運算。您可以透過下載與安裝 BOINC 程式來當一個志願者參與此計劃。

在這數獨計劃中，我們提出了一些新的演算法並微調了 Checker 程式(由 Gary McGuire 所撰寫)，我們成功地將原本預計要300,0000年單核運算時間才能解決的數獨問題降至只需2417年的運算時間，因此這個數獨問題很適合使用 BOINC 系統來解決。部份新的演算法有寫成論文投稿至 IWCG Workshop of TAAI 2010 conference。

在2417年運算時間內解決數獨之最小提示數的問題

數獨是目前許多最受歡迎的遊戲之一，在科學的角度上，數獨有一個很重要的問題是：在所有合法的數獨初始盤面中，所具有的最小提示數為何？ 在2009年10月的時候，Gordon Royle 已收集了49151組提示數為17的數獨初始盤面，這49151組是已經去掉彼此重複的盤面(重複盤面指的是可以經由旋轉、對稱及數字對換所產生出來的盤面)。然而到目前為止，尚沒有人能找到提示數為16的合法數獨初始盤面，也沒有人能證明不存在此種盤面，大部份人則相信不存在提示數為16的合法數獨初始盤面。

Gary McGuire 為愛爾蘭大學的教授，提供了一個解決數獨最小提示數問題的方法，並實作出 CHECKER 程式實作此方法。根據我們的實驗顯示，此程式在配備為 Intel(R) Xeon(R) E5520 @ 2.27GHz 的單核 CPU 運算下需要30萬年的 CPU 時間才能解決數獨最小提示數的問題。他在2006年被科學人雜誌訪問時曾提到：「我們實在必須在理論上有所突破，做搜尋才比較有可能。要嘛我們得縮減搜尋的空間，不然就需要更棒的搜尋算則。」(來源：科學人雜誌2006年7月號)

最近我們的研究提出了一些新的演算法並微調了 CHECKER 程式，最後達到了比原程式快128倍的效率，改善後的程式碼可由此下載。根據我們的實驗數據顯示，我們修改過後的程式可以在 2417 年單核運算時間內解決數獨最小提示數的問題，因此這個問題將有機會被解決。比如說，若透過 BOINC 系統有2417核 CPU 在幫我們做運算，則我們可以用一年的時間解掉此問題。而若是有24170核 CPU 幫我們做運算，則可以在36天內解掉它。 (我們的測試資料可由此下載)

在這裡我們要感謝捐出 CPU 資源給sudoku@vtaiwan的人們。
您的貢獻對解決此問題是一個很大的幫助！

V-TAIWAN 計劃

V-Taiwan 或稱為 Volunteer-Taiwan 是一個志願型計算的計劃，其經費來源是由台灣國家科學委員會(NCS)所支持。 這個即將發表的計劃是用志願型計算來幫對局程式做運算。截至目前為止我們已經成功地用志願型計算解決了許多六子棋的開局問題，其中包括了有名的米老鼠開局(因像米老鼠的臉而得名)，相關細節可參考底下的參考文獻。

相關文獻

• 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.