a160: 祖靈想要下棋!!!!!!!!

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

http://hoyusun.blogspot.tw/2013/01/a160.html

#include <cstdio>
void DFS(int now, int deep);
bool Judge(int x, int y);
int T, Ans, map[12][12]={};
int main()
{
    int first = 0;
    while(scanf("%d", &T) && T){
        if(first)
            puts("");
        first = 1;
        if(T == 2 || T == 3){
            puts("0");
            continue;
        }
        Ans = 0;
        DFS(0, T);
        printf("%d\n", Ans);
    }
    return 0;
}
void DFS(int now, int deep){
    if(now == deep){
        for(int i = 0; i < now; i++){
            for(int j = 0; j < now; j++)
                printf("%c", map[i][j]?'Q':'x');
            puts("");
        }
        Ans++;
        puts("");
    }
    for(int i = 0; i < deep; i++){
        if(Judge(i, now)){
            map[now][i] = 1;
            DFS(now+1, deep);
            map[now][i] = 0;
        }
    }
}
bool Judge(int x, int y){
    int sum = 0;
    for(int i = 0; i < T; i++)
        sum += map[i][x] + map[y][i];
    int x1 = x, y1 = y, x2 = x, y2 = y;
    int x3 = x, y3 = y, x4 = x, y4 = y;
    while(x1 >= 0 && y1 >= 0){
        sum += map[y1][x1];
        x1--, y1--;
    }
    while(x2 < T && y2 < T){
        sum += map[y2][x2];
        x2++, y2++;
    }
    while(x3 < T && y3 >= 0){
        sum += map[y3][x3];
        x3++, y3--;
    }
    while(x4 >= 0 && y4 < T){
        sum += map[y4][x4];
        x4--, y4++;
    }
    return sum?false:true;
}

/*
Wrote by Lily, it's still WA, but I don't know why
Time's late, then I went to sleep, 
I trust it will be better tomorrow
*/
#include <iostream>
#include <stdlib.h>
using namespace std;

int map[12][12], x[12], y[12], used[12];
int n,s = 0;

int check(int a, int b, int idx) {
    int i;
    for(i = 0; i < idx; i++)
        if(abs(x[i]-a) == abs(y[i]-b))
            return 0;
    return 1;
}

void queenDFS(int idx, int sum) { // idx為已放的皇后數量, sum解答數量
    if(idx == n) {
        // 印出最終結果
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j] == 1) {
                    cout << "Q";
                }else {
                    cout << "x";
                }
            }
            cout << endl;
        }
        cout << endl;
        s = sum;
        return;
    }

    for(int i = 0; i < n; i++) {
        if(used[i] == 0 && check(idx, i, idx) != 0) {
            used[i] = 1;
            x[idx] = idx, y[idx] = i;
            map[idx][i] = 1; //放皇后
            queenDFS(idx+1, sum++);
            map[idx][i] = 0; //拿走皇后
            used[i] = 0;
        }
    }
}


int main() {
    while(cin >> n && n != 0) {
        if(n == 1) { //輸入1的時候直接印出答案
            cout << "Q" << endl << 1;
        }else if(n == 2 || n == 3) { //輸入 2 或 3 的時候直接印出答案
            cout << 0;
        }else {
            queenDFS(0, 0); //從第一格開始...
            cout << s; //總共s種解
        }
        cout << endl;
    }
}

Allen版 AC

#include<iostream>
using namespace std;

const int MAX_N=12;
int N = MAX_N;
int ansNum; //有幾種解
int column[MAX_N] = {0};        // 同行是否有皇后 ↑↓
int slash[2 * MAX_N] = {0};     // 右上至左下是否有皇后？↙
int backSlash[2 * MAX_N] = {0}; // 左上至右下是否有皇后 ↘
int queens[MAX_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隻皇后
        print(); //印出正解
        ansNum++;
    }
    else {
        int x;
        for(x = 0; x < N; x++) {

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

        }
    }
}

int main(void) {

    while(cin>>N&&N!=0){
        ansNum = 0;
        dfs(0); //0代表放了幾隻皇后，每一行都會有一隻，且只能有一隻
        cout<<ansNum<<endl;
    }
    return 0;
}