查看“NQueens Project”的源代码

[[分类:已结束项目]]
{{Project
|name=NQueens Project
|logo=
|developer=Universidad de Concepción[[Image:Chile.gif]]
|released=
|app={{app/Windows}} / {{app/Linux}}
|platform={{platform/独立}}
|subproject=
|status=已关闭
|genre={{genre/数学}}
|website=http://nqueens.ing.udec.cl/
|rss=http://nqueens.ing.udec.cl/rss_main.php
}}

'''NQueens Projecte'''试图解决象棋中的N皇后问题。你可以在你的计算机上通过下载并且运行免费的程序来参加本项目。

{{JoinBoincProject
|Project=NQueens Project
|URL=http://nqueens.ing.udec.cl/
}}

== 项目背景==

===最初的八皇后问题：===

最初的八皇后问题就是：尝试找出在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"
|-
|  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 topics}}