学步园

同行同列好判断。

判断对角线上的时候要注意，因为 成45°，所以斜率 k = ± 1。 又因为 (x - x1 )/ (y - y1) = k

所以有(x -x1)/(y - y1) = ± 1 --> |x -x1|  /  | y - y1| = 1 --> |x - x1|  == | y -y1| 

满足这种情况就是在对角线上

要注意的是 要放满 n 个皇后  

刚开始没注意  在后面又加了个 dfs(x + 1)。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int const MAXN = 20;
int hash1[MAXN][MAXN],s[MAXN];
int sum,cnt;
void Init(){
    memset(hash1,0,sizeof(hash1));
    sum = 0;
    cnt = 0;
}
int Fabs(int x){
    return x > 0 ?x : -x;
}
bool Judge(int x,int y,int n){
    for(int i = 1;i <= n;i++){
        if(hash1[i][y]) return false;
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(Fabs(i - x) == Fabs(j - y)){
                if(hash1[i][j]) return false;
            }
        }
    }
    return true;
}
void Dfs(int x,int n){
    for(int i = 1;i <= n;i++){
        if(cnt == n){
            sum++;
            return ;
        }
        if(x > n) return ;
        if(!hash1[x][i] && Judge(x,i,n)){
            cnt++;
            hash1[x][i] = 1;
            Dfs(x + 1,n);
            cnt--;
            hash1[x][i] = 0;
        }
    }
    //Dfs(x + 1,n);
}
int main(){
    for(int i = 1;i <= 10;i++){
        Init();
        Dfs(1,i);
        s[i] = sum;
    }
    int n;
    while(~scanf("%d",&n),n){
        printf("%d\n",s[n]);
    }
    return 0;
}