NQueens Project

來自中國分布式計算總站
跳轉至: 導航搜索


NQueens Project
[[Image:|220px|NQueens Project logo]]
NQueens Project logo
無屏保圖形
無屏保圖形
開發者 Universidad de ConcepciónChile.gif
版本歷史
計算程序 Windows / Linux
子項目
項目平臺 獨立平臺
項目類別 數學
項目狀態 已關閉
官方網址 NQueens Project
項目文獻 分類:NQueens Project 相關文獻
http://nqueens.ing.udec.cl/rss_main.php 通過 RSS 獲取項目新聞


NQueens Projecte試圖解決象棋中的N皇后問題。你可以在你的計算機上通過下載并且運行免費的程序來參加本項目。


如何加入項目

該項目基于 BOINC 平臺,簡要的加入步驟如下(已完成的步驟可直接跳過):

  1. 下載并安裝 BOINC 的客戶端軟件(官方下載頁面程序下載
  2. 點擊客戶端簡易視圖下的“Add Project”按鈕,或高級視圖下菜單中的“工具->加入項目”,將顯示向導對話框
  3. 點擊下一步后在項目列表中找到并單擊選中 NQueens Project 項目(如未顯示該項目,則在編輯框中輸入項目網址:http://nqueens.ing.udec.cl/ ),然后點擊下一步
  4. 輸入您可用的電子郵件地址,并設置您在該項目的登錄密碼(并非您的電子郵件密碼)
  5. 再次點擊下一步,如項目服務器工作正常(并且有適合自身操作系統的計算程序),即已成功加入項目

更詳細的加入方法說明,請訪問 BOINC 新手指南BOINC 使用教程

本站推薦您加入 Team China 團隊,請訪問項目官方網站的 團隊檢索頁面,搜索(Search)并進入 Team China 的團隊頁面,點擊頁面中的 Join 并輸入用戶登錄信息即可加入!

項目背景

最初的八皇后問題:

最初的八皇后問題就是:嘗試找出在8×8格的國際象棋棋盤上放置八個皇后,使得各個皇后不會互相攻擊(即不在同一行、同一列或同一斜線上)的擺放方法。

很久以前人們就發現八皇后問題有92種解決方法。在這些辦法中,有12種典型。所有92種解都能通過旋轉和倒映轉換為12種典型之一。

將問題拓展到N個皇后在一個NxN棋盤上的情況:

如果將8橫8縱的棋盤延伸出去,我們就想去探究當N為某正整數值時,N皇后問題有多少種解法。比如當N = 10時,該問題就有724種解法,其中有92種典型。

目前所知:

迄今為止,人們已算出當N = 25時,該問題共有2,207,893,435,808,352種解法。這一結果曾被兩次計算出:

  • 2005年6月11日,由Objectweb ProActive INRIA Team算得(代表為Alexandre Di Costanzo)。這次計算花費了相當于大約53年的計算時間。
  • 2005年7月26日,NTU 25Queen小組進行驗算,該小組由國立臺灣大學和銘傳大學建立,由謝育平(Arping Shieh)教授領導。花費約26613天計算時間(73年)。

原作者目前尚未獲知有任何項目嘗試計算N = 26的情況。

Board Solutions Time Board Solutions Time (h:m:s)
1 1 14 365 596 00:00:01
2 0 < 0 s 15 2 279 184 00:00:04
3 0 < 0 s 16 14 772 512 00:00:23
4 2 < 0 s 17 95 815 104 00:02:38
5 10 < 0 s 18 666 090 624 00:19:26
6 4 < 0 s 19 4 968 057 848 02:31:24
7 40 < 0 s 20 39 029 188 884 20:35:06
8 92 < 0 s 21 314 666 222 712 174:53:45
9 352 < 0 s 22 2 691 008 701 644 ?
10 724 < 0 s 23 24 233 937 684 440 ?
11 2 680 < 0 s 24 227 514 171 973 736 ?
12 14 200 < 0 s 25 2 207 893 435 808 352 ?
13 73 712 < 0 s 26 ? ?


關于本項目

研究對象是什么?

本項目是一次探究N皇后問題的嘗試。使用BOINC框架。從N=19的情況開始。

如何研究?

在對N皇后問題的研究過程中,解法的數量和解題所需時間以階乘形式(n!)遞增,所以在單臺PC上解決N=19以后的計算將會是一場超級馬拉松。

然而,拜其特性所賜,這個問題非常適合并行計算(即在棋盤的第一縱或橫上擺放皇后,然后判斷隨之而來的情形,每一分步中所獲得的結果之和即為所求)。

以8皇后問題為例:

你可以將NxN棋盤視作N個(N—1)x(N—1)棋盤(這些棋盤上已經在一個角落放置了一個皇后)。不斷重復該過程,直到問題適合單臺PC以合理的時間完成處理。

數據處理

就每種棋盤而言,本項目發送關于首個皇后附近前n / 2個位置的任務包,所以所得結果為真實結果的一半。對格子數為奇數的棋盤也一樣,先計算首個皇后附近的(n-1)/2,然后是剩下的(n+1)/2,第二個皇后只放置在離首個皇后較近的一半位置。

目前,本項目所用代碼以Jeff Somers Code為基礎,并加以修改以適應BOINC框架。

Boinc Icon.png伯克利開放式網絡計算平臺BOINC
· ·
生命科學類項目 Computational Structural Biology · [email protected] · GPUGRID · Malariacontrol.net · [email protected] (Alpha內測項目)· RNA World · [email protected] · The Lattice Project
地球科學類項目 Climateprediction.net · Quake-Catcher Network Seismic Monitoring
人工智能類項目 [email protected]
天文學項目 Astropulse · [email protected] · [email protected] · [email protected] · [email protected]/AstroPulse Beta (Beta公測項目)· [email protected]
物理化學類項目 [email protected] · [email protected] · Leiden Classical · [email protected] · [email protected]
數學類項目 Collatz Conjecture · [email protected] · primaboinca · PrimeGrid · SZTAKI Desktop Grid · WEP-M+2 Project
密碼類項目 [email protected] · Moo! Wrapper
藝術類項目 BURP
多種應用的項目 [email protected] · World Community Grid · [email protected]
與 BOINC 平臺相關的項目 BOINC Alpha Test · [email protected] · [email protected]
已結束/暫停/合并的項目 [email protected] · AlmereGrid Boinc Grid · [email protected] · [email protected] · BBC Climate Change Experiment · Biochemical Library · [email protected] · [email protected] · [email protected] · CPDN Beta · DepSpid · DistrRTgen · [email protected] · [email protected] · [email protected] · [email protected] · DynaPing · [email protected] · eOn: Long timescale dynamics · [email protected] · Eternity2.fr · [email protected] · Goldbach's Conjecture Project · Ibercivis · [email protected] · [email protected] · [email protected] · MilestoneRSA · [email protected] · [email protected] · NQueens Project · [email protected] · Open Rendering Environment · [email protected] · PicEvolvr.com] · [email protected] · QuantumFIRE alpha · [email protected] ·RamseyX · Rectilinear Crossing Number · Renderfarm.fi · RSA Lattice Siever (2.0) · Seasonal Attribution Project · SHA-1 Collision Search Graz · SIMAP · [email protected] · [email protected] · [email protected] · [email protected] · TANPAKU · Virtual Prairie · Virus Respiratorio Sincitial · XtremLab · Zivis
BOINC 相關的工具 BOINCstats BAM! · BOINC Translation Services · BOINC TThrottle