NQueens Project

WiZarD811

很久以前人们就发现八皇后问题有92种解决方法。在这些办法中，有12种典型。（原句：“Of these 92, there are 12 distinct patterns.”，有疑问）所有92种解都能通过旋转和倒映转换为12种典型之一。


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

目前所知
迄今为止，人们已算出当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的研究情况。

关于本项目

研究对象是什么？
本项目是一次探究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框架。

WiZarD811

跳过了已翻译部分