2016 UESTC Training for Search Algorithm & String A – Xiper的奇妙历险(1) 八皇后问题、dfs

Source

2016 UESTC Training for Search Algorithm & String

My Solution

八皇后问题

这里是九个皇后
逐行放置，则皇后肯定不会横向攻击，只需要检查纵向和两个斜向攻击即可
其中用 cur - C[cur] == j - C[j] || cur + C[cur] == j + C[j] 来判断是否有斜向攻击
用 C[cur] == C[j] 检查纵向攻击
然后每次 cur == n 的时候这一钟情况就完成了， 把这个C[0~n-1] 存储到ans[tot][i]里
最后全部返回了 就得到了所有答案
然后for for 打印即可

#include 
#include 
using namespace std;

int n, tot, C[16];
// n == 9, tot == 352
int ans[352+8][9];

void _search(int cur)
{
    if(cur == n){
        tot++;
        for(int i = 0; i < n; i++){
            ans[tot][i] = C[i];
        }
    }
    else{
        for(int i = 1; i <= n; i++){        //!行数的表示用 1 ~ n, 下标还是 0 ~ n-1
            int ok = 1;
            C[cur] = i;                     //把第cur行的皇后放在第C[cur] = i列
            for(int j = 0; j < cur; j++){   //检查是否冲突
                if(C[cur] == C[j] || cur - C[cur] == j - C[j] || cur + C[cur] == j + C[j]){
                    ok = 0; break;
                }
            }
            if(ok) _search(cur+1);
        }
    }
}
//!HInt 每个方案最后一个数字后面要多输出一个空格再换行
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "w", stdout);
    #endif // LOCAL
    tot = 0;
    scanf("%d", &n);
    _search(0);
    printf("%dn", tot);
    for(int i = 1; i <= tot; i++){
        for(int j = 0; j < n; j++){
            printf("%d ", ans[i][j]);
        }
        printf("n");
    }
    return 0;
}