Wiki對八皇后問題的定義如下：
八皇后問題是一個以西洋棋為背景的問題：如何能夠在 8×8 的西洋棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處於同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變為n×n，而皇后個數也變成n。若且唯若 n = 1 或 n ≥ 4 時問題有解。
寫程式求解，最方便的方法便是窮舉法，也因為這個問題是算是所有的解的個數，所以是一個counting problem，如果以上下限來探究這個問題，這個問題比EXP成長的還要快。所以目前為止沒有很有效率的解法，有的只是少算一半或是少算1/4或1/8，但大家都知道，這對算法本身是一樣的時間的order。
最主要的步驟在於如何檢驗棋盤中的[i, j]是不是能放一個queen，一般檢察都是以"米"字方法檢驗，但是因為我們是由上而下擺放，故下方所有的檢驗可以不做，又因為位於任一row上面的第i個column上若有一個皇后，也等同於在第n-i column上的解(鏡射方法)，所以我們只要對第一個row求出n/2個column的解就完成了(total的解的個數當然要*2)。如果是奇數也不用擔心先把前面n/2求A個解再求一個n/2+1有B個解，total解法就是2A+B。
在我的電腦裡算出的時間如下 (P4 D 3.4G CPU)：
n = 1 ~ 11, 0秒
n = 12, 1秒 (14200解)
n = 13, 3秒 (73712解)
n = 14, 18秒 (365596解)
n = 15, 134秒 (2279184解)
n = 16, 909秒 (14772512解)
n = 17, 7312秒 (95815104解) <=快破億了
有沒有辦法再加快呢？答案是有的，程式部分我並沒有做最佳化，而且compiler也沒打開最佳化，另外所有的variables都改為global也會變快，減少for的週算次數也很重要，也可以再調整一下檢驗的順序。經過實驗，這個解比起Wiki提供的還要快，因為少算了一半吧。
程式如下：
// NQueen.cpp : Defines the entry point for the console application.
//
#include "NQueen.h"
#include <iostream>
#include <time.h>
using namespace std;
int *boardMap;
int queenCount = 0;
int totalSolution = 0;
int main(int argc, char* argv[], char* envp[])
{
if(argc != 2) {
cout << "Please input a number..." << endl;
return 0;
}
makeMap((queenCount = atoi(argv[1])));
time_t start,end;
double dif;
time (&start);
specialCount();
time (&end);
dif = difftime(end,start);
printf("It takes %.2f seconds to count %ld queens' solutions...\n", dif, queenCount);
cout << "Total solution: " << totalSolution << endl;
return 0;
}
void makeMap(int n) {
boardMap = new int[n];
for(int i = 0; i < n; ++i) {
boardMap[i] = -1;
}
}
void deleteMap() {
delete [] boardMap;
}
void count2(int row, int i) {
for(register int j = 0; j < queenCount; ++j) {
if(check8Directions2(row, j)) {
boardMap[row] = j;
if(row != queenCount-1) {
count2(row+1, 0);
} else {
totalSolution ++;
}
}
boardMap[row] = -1;
}
}
void specialCount() {
if(queenCount == 1) {
totalSolution = 1;
return;
}
for(int i = 0; i < queenCount / 2; ++i) {
boardMap[0] = i;
count2(1, 0);
}
int currentTotalCount = totalSolution;
totalSolution = 0;
if(queenCount % 2 == 1) {
boardMap[0] = queenCount / 2;
count2(1, 0);
}
totalSolution = totalSolution + currentTotalCount * 2;
}
bool check8Directions2(int row, int j) {
register int i = 0;
for(i = 0; i <= row; ++i) {
if((boardMap[i] == j))
return false;
}
for(i = 1; i <= row; ++i) {
if((boardMap[row-i] == j-i) || (boardMap[row-i] == j+i))
return false;
}
return true;
}
