NQueens Project：修订间差异
跳转到导航
跳转到搜索
无编辑摘要 |
Zhouxiaobo（留言 | 贡献） 小 已结束。 |
||
| （未显示4个用户的12个中间版本） | |||
| 第1行： | 第1行： | ||
{{ | [[分类:已结束项目]] | ||
| name =NQueens Project | {{Project | ||
| logo | |name=NQueens Project | ||
|logo= | |||
|developer=Universidad de Concepción[[Image:Chile.gif]] | |||
| developer = | |released= | ||
|app={{app/Windows}} / {{app/Linux}} | |||
|platform={{platform/独立}} | |||
| | |subproject= | ||
| | |status=已关闭 | ||
| | |genre={{genre/数学}} | ||
| status = | |website=http://nqueens.ing.udec.cl/ | ||
| genre = | |rss=http://nqueens.ing.udec.cl/rss_main.php | ||
| | |||
| | |||
}} | }} | ||
'''NQueens Projecte'''试图解决象棋中的N皇后问题。你可以在你的计算机上通过下载并且运行免费的程序来参加本项目。 | '''NQueens Projecte'''试图解决象棋中的N皇后问题。你可以在你的计算机上通过下载并且运行免费的程序来参加本项目。 | ||
{{JoinBoincProject | {{JoinBoincProject | ||
|Project=NQueens Project | |Project=NQueens Project | ||
| 第23行： | 第21行： | ||
}} | }} | ||
== | == 项目背景== | ||
=== | ===最初的八皇后问题：=== | ||
最初的八皇后问题就是：尝试找出在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的情况。 | |||
{| class="wikitable" border="1" | {| class="wikitable" border="1" | ||
| 第147行： | 第144行： | ||
== | ==关于本项目== | ||
=== | ===研究对象是什么？=== | ||
本项目是一次探究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 topics}} | {{BOINC topics}} | ||
2017年12月6日 (三) 13:38的最新版本
NQueens Projecte试图解决象棋中的N皇后问题。你可以在你的计算机上通过下载并且运行免费的程序来参加本项目。
如何加入项目
该项目基于 BOINC 平台，简要的加入步骤如下（已完成的步骤可直接跳过）：
- 下载并安装 BOINC 的客户端软件（官方下载页面或程序下载）
- 点击客户端简易视图下的“Add Project”按钮，或高级视图下菜单中的“工具->加入项目”，将显示向导对话框
- 点击下一步后在项目列表中找到并单击选中 NQueens Project 项目（如未显示该项目，则在编辑框中输入项目网址：http://nqueens.ing.udec.cl/ ），然后点击下一步
- 输入您可用的电子邮件地址，并设置您在该项目的登录密码（并非您的电子邮件密码）
- 再次点击下一步，如项目服务器工作正常（并且有适合自身操作系统的计算程序），即已成功加入项目
更详细的加入方法说明，请访问 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框架。
