↓這題目較為複雜，當延伸閱讀就好

c104: 00167 - The Sultan's Successors (蘇丹的繼承者們)

https://zerojudge.tw/ShowProblem?problemid=c104

內容：

努比亞的蘇丹沒有子女，所以他要從一些有資格的繼承者中挑選一個出來繼承王位。他希望這個繼承者是夠聰明的，所以他決定用一個遊戲來測試這些人。

他準備了一個西洋棋盤，上面的每個格子中均有一個1到99的數字。他又準備了8個皇后棋子。每位參加遊戲的人必須將8個皇后放置到棋盤中，且各皇后 彼此不可互相攻擊。可以想像，這樣有不只一種的放置方式。而蘇丹要挑選的繼承者就是那位可以放置8個皇后，並且放置皇后的8個位置中的數的和為最大的那一 個人。

你的任務就是讀入棋盤上的數，幫蘇丹算出可以放置8個皇后的最大的和是多少。

解題提示：

如果已經解完「a160: 祖靈想要下棋」，那麼這一題也難不倒你，找出所有的92二種解，找出sum最大的那個解就好了。

↓視情況可以移除下面的圖片

#include<iostream>
using namespace std;

const int N=8;
int ans=0;
int sum=0;
int value[N][N] = {0};
int column[N] = {0};        // 同行是否有皇后 ↑↓
int slash[2 * N] = {0};     // 右上至左下是否有皇后？↙
int backSlash[2 * N] = {0}; // 左上至右下是否有皇后 ↘
int queens[N] = {0};

//檢查這一格是否可以放下皇后，可以回傳true
int isVisitable(int y, int x) {
   return !(column[x] || slash[x + y] || backSlash[x - y + N]);
}

//印出棋盤結果
void print() {
    int x, y;
    for(y = 0; y < N; y++) {
        for(x = 0; x < N; x++) {
            cout<<(queens[y] == x ? "Q" : "x");
        }
        cout<<endl;
    }
    cout<<endl;
}

//找尋可以放皇后的格子
void dfs( int y) {//i是第幾隻皇后，同時也是第幾列

    if(y >= N) { //已放好第8隻皇后
        if(sum>ans){
            ans = sum;
        }
        //print(); //印出正解
    }
    else {
        int x;
        for(x = 0; x < N; x++) {

            if(isVisitable(y, x)) { //這格能不能放皇后
                sum+=value[y][x];
                queens[y] = x;
                column[x] = slash[x + y] = backSlash[x - y + N] = 1; //將皇后放下去，所以不能放的地方增加了
                dfs( y + 1 ); //往下一列，繼續尋找皇后的擺放點
                sum-=value[y][x];
                column[x] = slash[x + y] = backSlash[x - y + N] = 0; //將皇后拿起來，所以不能放的地方減少了
            }

        }
    }
}

int main(void) {
    int k;
    while(cin>>k){
        while(k--){
            ans=sum=0;
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    cin>>value[i][j];
                }
            }
            dfs(0); //0代表放了幾隻皇后，每一行都會有一隻，且只能有一隻
            cout<<ans<<endl;
        }
    }
    return 0;
}