NQueens Project

出自中国分布式计算总站

跳转到: 导航, 搜索
50px 当前页面或段落需要更新
当前页面或段落提供了过时的信息,可能误导读者,希望了解相关内容的Wiki用户协助编辑。
用户 cuihao 给出的意见是:关了? 。
其他用户若有异议,请前往讨论:NQueens Project发表见解。
欢迎无wiki账号的用户到论坛Wiki系统讨论区注册)参与讨论。
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 · DNA@home · DrugDiscovery@Home · GeneticLife@Home · GPUGRID · Malariacontrol.net · Malaria Control Test Project · POEM@HOME · RALPH@home (Alpha内测项目)· RNA World · Rosetta@home · SciLink · SIMAP · Superlink@Technion · The Lattice Project · UH Second Computing · Virus Respiratorio Sincitial · Drug@Home(测试项目)
地球科学类项目 Climateprediction.net · Quake-Catcher Network Seismic Monitoring · Seasonal Attribution Project · Virtual Prairie · CPDN Beta(Beta公测项目)
人工智能类项目 Intelligence Realm · MindModeling@Home
天文学项目 Astropulse · BRaTS@Home · Cosmology@Home · MilkyWay@home · Orbit@Home · SETI@home · SETI@home/AstroPulse Beta (Beta公测项目)· Asteroids@home
物理化学类项目 EDGeS@Home · Einstein@Home · eOn: Long timescale dynamics · Hydrogen@Home · Leiden Classical · LHC@home · Magnetism@home · Mopac@home · QMC@Home · QuantumFIRE alpha · SLinCA@Home · Spinhenge@home · μFluids@Home
网络与计算机类项目 Biochemical Library ·DynaPing · Luxrenderfarm@home
数学类项目 Collatz Conjecture · Goldbach's Conjecture Project · Mersenne@home · NFS@Home · primaboinca · PrimeGrid · Ramsey@Home · Ramsey@Home Test · Rectilinear Crossing Number · RSA Lattice Siever (2.0) · SZTAKI Desktop Grid · WEP-M+2 Project
密码类项目 Enigma@Home · MilestoneRSA · Moo! Wrapper · SHA-1 Collision Search Graz
艺术类项目 BURP · Open Rendering Environment · PicEvolvr.com · Renderfarm.fi
游戏类项目 Chess960@Home · Eternity@Home
多种应用的项目 CAS@home · Gerasim@Home · Ibercivis · World Community Grid · Yoyo@home
与 BOINC 平台相关的项目 AlmereGrid Boinc Grid · AlmereGrid TestGrid - Boinc · BOINC Alpha Test · Pirates@home · WUProp@Home
其他 CzechNationalTeam project · Distributed Data Mining · Steiner@Home
规划中的项目
已结束/暂停的项目 3x+1@home · ABC@home · ABC@home beta · Anansi · APS@Home · AQUA@home · Artificial Intelligence · BBC Climate Change Experiment · BCL@Home · Cels@Home · Cels@Home test2 · Cels@Home (old) · DepSpid · DistrRTgen · DNETC@HOME · Docking@Home · EAPS@HOME · Evo@home ·Eternity2.fr · FreeHAL@home · HashClash · LHC Alpha · Nano-Hive@home · pPot Tables · NQueens Project · Predictor@home · Project Neuron · RND@home · Sudoku@vtaiwan · TANPAKU · TMRL DRTG · TSP · XtremLab · Zivis
BOINC 相关的工具 BOINCstats BAM! · BOINC Translation Services · BOINC TThrottle · BoincTasks · Boinc.NET · OGM (Organizational Grid Manager)