八皇后問題（8クイーンの問題）

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;
}