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 · 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
多种应用的项目 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