[leetcode]n queens ii

n queens ii

题目描述

Follow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions.

题目解析

我们令x[i]的值为第i个皇后所在的列数。那么我们第一个皇后的位置可以在第一行任意一个位置任选，所以我们试出来第一个皇后在第1到第n个列位置下的不同情况（一共有n颗n叉树）。然后安排完第一个皇后位置后，第二个皇后位置在第二行也是从第1到第n列分别试一遍，看是否满足要求。若满足要求则进行第三个皇后，否则该树是没有结果的。当不断递归到t>n的时候，那说明在上一步已经安排完了，那么久直接对计数加1，然后返回。

void Backtrack(int t,int num)
    {
        if(t>num)
        {
            countn++;
        }
        else
            for(int i=1;i<=num;i++)
            {
                x[t]=i;
                if(Place(t))
                    Backtrack(t+1,num);
            }
    }void Backtrack(int t,int num)
    {
        if(t>num)
        {
            countn++;
        }
        else
            for(int i=1;i<=num;i++)
            {
                x[t]=i;
                if(Place(t))
                    Backtrack(t+1,num);
            }
    }

题目要求就是每一个皇后不能跟上一行的那个皇后同一列和对角线，所以在获得下一列真实的位置的时候，需要判断是不是在同一列或者对角线，即：

bool Place(int t)
    {
        bool ok=true;
        for(int j=1;j<t;j++)
        {
            if(x[t]==x[j]||t-j==fabs(x[t]-x[j]))//判断列对角线是否冲突
            {
                ok=false;
                break;
            }
        }
        return ok;
    }

代码实现

public:
    int countn=0;
    int x[200];
    bool Place(int t)
    {
        bool ok=true;
        for(int j=1;j<t;j++)
        {
            if(x[t]==x[j]||t-j==fabs(x[t]-x[j]))//判断列对角线是否冲突
            {
                ok=false;
                break;
            }
        }
        return ok;
    }

    void Backtrack(int t,int num)
    {
        if(t>num)
        {
            countn++;
        }
        else
            for(int i=1;i<=num;i++)
            {
                x[t]=i;
                if(Place(t))
                    Backtrack(t+1,num);
            }
    }
    int totalNQueens(int n) {
        Backtrack(1,n);
        return countn;
    }