查看“NQueens Project”的源代码

{{Infobox Project
| name =NQueens Project
| logo =
| screenshot =无屏保图形
| caption =
| developer =
| released =
| operating system =[[Image:Windows.png]]
| platform =BOINC
| program info =
| work unit info =
| status =
| genre =
| optimization =无
| website =http://nqueens.ing.udec.cl/
}}
[[NQueens Projecte]]试图解决象棋中的N皇后问题。你可以在你的计算机上通过下载并且运行免费的程序来参加本项目。

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

==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. 

===Expanding the problem to N Queens on an NxN chessboard:===

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. 

===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.

{| 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
|  ?
|  ?  
|}


==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. 

===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. 

===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. 



{{BOINC topics}}

[[Category:分布式计算项目]][[Category:BOINC 平台上的项目]][[Category:待翻译]]