“NQueens Project”的版本间差异
（项目已关闭，顺便更新翻译） |
小 （更新开发者信息） |
||
| 第2行： | 第2行： | ||
| name =NQueens Project | | name =NQueens Project | ||
| logo = | | logo = | ||
| − | | screenshot = | + | | screenshot = |
| − | | caption = | + | | caption =无屏保图形 |
| − | | developer = | + | | developer =Universidad de Concepción[[Image:Chile.gif]] |
| released = | | released = | ||
| − | | operating system =[[Image:Windows.png]] | + | | operating system =[[Image:Windows.png]] / [[Image:Linux.png]][[Image:64bits.png]] |
| platform =BOINC | | platform =BOINC | ||
| program info = | | program info = | ||
| − | | work unit info = | + | | work unit info =10日任务期限 |
| status =已关闭 | | status =已关闭 | ||
| genre = | | genre = | ||
2010年9月3日 (五) 17:02的版本
|
NQueens Project | |
|---|---|
NQueens Project logo | |
无屏保图形 | |
| 开发者 | Universidad de Concepción
|
| 版本历史 | |
| 运算平台 |  /  
|
| 项目平台 | BOINC |
| 程序情况 | |
| 任务情况 | 10日任务期限 |
| 项目状态 | 已关闭 |
| 项目类别 | |
| 优化程序 | 无 |
| 计算特点 | CPU密集： |
| 官方网址 | NQueens Project |
|
[{{{rss}}} 通过 RSS 获取项目新闻] |
NQueens Projecte试图解决象棋中的N皇后问题。你可以在你的计算机上通过下载并且运行免费的程序来参加本项目。
如何加入项目
该项目基于 BOINC 平台，简要的加入步骤如下（已完成的步骤可直接跳过）：
- 下载并安装 BOINC 的客户端软件（官方下载页面或程序下载）
- 点击客户端简易视图下的“Add Project”按钮，或高级视图下菜单中的“工具->加入项目”，将显示向导对话框
- 点击下一步后在项目列表中找到并单击选中 NQueens Project 项目（如未显示该项目，则在编辑框中输入项目网址：http://nqueens.ing.udec.cl/ ），然后点击下一步
- 输入您可用的电子邮件地址，并设置您在该项目的登录密码（并非您的电子邮件密码）
- 再次点击下一步，如项目服务器工作正常（并且有适合自身操作系统的计算程序），即已成功加入项目
更详细的加入方法说明，请访问 BOINC 新手指南 或 BOINC 使用教程。
本站推荐您加入 Team China 团队，请访问项目官方网站的 团队检索页面，搜索（Search）并进入 Team China 的团队页面，点击页面中的 Join 并输入用户登录信息即可加入！
BACKGROUND 项目背景
最初的八皇后问题：
最初的八皇后问题就是：尝试找出在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框架。
