“NQueens Project”的版本间的差异

来自中国分布式计算总站
跳转至: 导航搜索
THE PROJECT
(项目已关闭)
第10行: 第10行:
 
| program info =
 
| program info =
 
| work unit info =
 
| work unit info =
| status =
+
| status =已关闭
 
| genre =
 
| genre =
 
| optimization =无
 
| optimization =无

2010年8月20日 (五) 10:20的版本

NQueens Project


NQueens Project logo
无屏保图形

开发者
版本历史
运算平台 Windows.png
项目平台 BOINC
程序情况
任务情况
项目状态 已关闭
项目类别
优化程序
计算特点 CPU密集:

支持0分享率

支持GPU计算

官方网址 NQueens Project
{{{rss}}} [{{{rss}}} 通过 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 并输入用户登录信息即可加入!

BACKGROUND 项目背景

The original eight queens problem:

最初的八皇后问题:

The original eight queens problem consisted of trying to find a way to place eight queens on a chessboard so that no queen would attack any other queen. An alternate way of expressing the problem is to place eight anythings on an eight by eight grid such that none of them share a common row, column, or diagonal.

最初的八皇后问题就是:尝试找出在8×8格的国际象棋棋盘上放置八个皇后,使得各个皇后不会互相攻击(即不在同一行、同一列或同一斜线上)的摆放方法。

It has long been known that there are 92 solutions to the problem. Of these 92, there are 12 distinct patterns. All of the 92 solutions can be transformed into one of these 12 unique patterns using rotations and reflections.

很久以前人们就发现八皇后问题有92种解决方法。在这些办法中,有12种典型。所有92种解都能通过旋转和倒映转换为12种典型之一。

Expanding the problem to N Queens on an NxN chessboard:

将问题拓展到N个皇后在一个NxN棋盘上的情况

If we increase the size of the chessboard beyond 8 rows/columns, we might want to find how many solutions exist for any arbitrary board size N. For example, if N = 10, then there are 724 solutions. Of these, 92 are distinct.

如果将8横8纵的棋盘延伸出去,我们就想去探究当N为某正整数值时,N皇后问题有多少种解法。比如当N = 10时,该问题就有724种解法,其中有92种典型。

Current Knowledge:

目前所知

To date, it's known that for N = 25 there are 2,207,893,435,808,352 solutions. This result were obtained by two diferent sources:

  • from Objectweb ProActive INRIA Team (proactive(AT)objectweb.org), Jun 11 2005 [Communicated by Alexandre Di Costanzo (Alexandre.Di_Costanzo(AT)sophia.inria.fr)]. This calculation took about 53 years of CPU time.
  • been confirmed by the NTU 25Queen Project at National Taiwan University and Ming Chuan University, led by Yuh-Pyng (Arping) Shieh, Jul 26 2005. This computation took 26613 days CPU time.

I don't know any project trying to solve the N=26 problem.

迄今为止,人们已算出当N = 25时,该问题共有2,207,893,435,808,352种解法。这一结果曾被两次计算出:
1. 2005年6月11日,由Objectweb ProActive INRIA Team算得(代表为Alexandre Di Costanzo)。这次计算花费了相当于大约53年的计算时间。
2. 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 ? ?

THE PROJECT

关于本项目

What's About?

研究对象是什么?

This project it's an attempt to find the results of the NQueen problem using a BOINC framework for board sizes starting from N=19.

本项目是一次探究N皇后问题的尝试。使用BOINC框架。从N=19的情况开始。

How?

如何研究?

In the N Queen problem the number of solutions and the time taken to solve the whole problem increases in order of n!. So doing it on a sigle ordinary PC it's a marathonic problem after N=19.

But, due the nature of the problem, it's a perfect candidate for paralelization. That's done by placing Queens in all different positions of the first Col/Row of the board, and then solve the results problems. The solution of the original problem it's the sum of all solutions of the subproblems.

For example in the 8 Queens problem we have:

That way, you can solve a N sized board as N N-1 boards (N boards with a queen already placed in the first row/col). And keep on doing that until the problem it's small enough to be computed in a PC in a reasonable time.

在对N皇后问题的研究过程中,解法的数量和解题所需时间以阶乘形式(n!)递增,所以在单台PC上解决N=19以后的计算将会是一场超级马拉松。
然而,拜其特性所赐,这个问题非常适合并行计算(即在棋盘的第一纵或横上摆放皇后,然后判断随之而来的情形,每一分步中所获得的结果之和即为所求)。
以8皇后问题为例:
你可以将NxN棋盘视作N个(N—1)x(N—1)棋盘(这些棋盘上已经在一个角落放置了一个皇后)。不断重复该过程,直到问题适合单台PC以合理的时间完成处理。

Crunching

数据处理

For each board, the project send jobs for the first n/2 positions of the first Queen, then the number of solutions must be doubled to get the real solution of the problem. In odd n boards the proccess it's similar, compute (n-1)/2 and for the (n+1)/2 position, the second queen it's placed only in the fisrt half of the board.

Currently, the code runing in the project it's based on the Jeff Somers Code[2], modified to work with subboards, checkpoint, and the BOINC framework.

就每种棋盘而言,本项目发送关于首个皇后附近前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