题解 | #N皇后问题#

//solution表示解决方案有多少种
int solution=0;
//queen[10]的含义为：queen数组下标代表是第几行，（queen[0]置空，方便对齐）
//queen数组元素的值代表该行元素所在列的下标（如queen[2]=3，表示第2行皇后在第3列）
int queen[10];//1<=n<=9，最多9行，由于queen[0]置空，所以需要10个长度


//check函数用于检查该位置能否放入皇后。参数说明：row:行；col：列
int check(int row,int col)
{
    //由于check要检查之前放入的皇后是否能攻击该次要让入的，所以i<=row，可以理解为行数就是已经放入过的皇后数
    for(int i=1;i<=row;i++)
    {    
        if(queen[i]==col){return 0;}//该列已经有皇后放入，不可放入
        if((queen[i]+i)==(row+col)){return 0;}//该副对角线上已经有皇后放入，不可放入
        if((i-queen[i])==(row-col)){return 0;}//该主对角线上已经有皇后放入，不可放入
    }
    //当满足列、主对角线、副对角线都不在攻击范围内，便可以放入
    return 1;
}

//回溯递归过程。参数说明：row：当前讨论皇后放入的行数；n：皇后数（列数）
void backtrack(int row,int n)
{   //如果行数达到n+1,即已经放入了所有皇后，解决方案+1。然后开始回溯。
    if(row==n+1)
    {
        solution++;
        return;
    }
    //未达到底部时
    else 
    {   //用check函数讨论该行每一列是否可以放入皇后
        for(int i=1;i<=n;i++)
        {   //不在攻击范围内时，进行递归下一行
            if(check(row,i)==1)
            {   //queen记录当前皇后放入位置
                queen[row]=i;
                //递归下一行
                backtrack(row+1,n);
                //由于回溯出来，所以要将标记的皇后归零，以便讨论下一种解法
                queen[row]=0;
            }
        }
    }
}
//主函数
int Nqueen(int n)
{   //为方便起见，不考虑0行，即为1行~9行
    backtrack(1,n);
    return solution;
}