题解 | #N皇后问题#

class Solution {
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int Nqueen(int n) {
        // write code here
        traceback(n, 0);
        return res;
    }

    void traceback(int n, int row)
    {
        if(row == n)
        {
            res++;
            return;
        }
        for(int i = 0; i<n; i++)
        {
            if(used_col[i] || used_left[i-row+n-1] || used_right[i+row])
                continue;
            used_col[i] = 1;
            used_left[i-row+n-1] = 1;
            used_right[i+row] = 1;
            traceback(n, row+1);
            used_col[i] = 0;
            used_left[i-row+n-1] = 0;
            used_right[i+row] = 0;
        }
    }
private:
    int used_col[10] = {0};
    int used_left[18] = {0};
    int used_right[18] = {0};
    int res = 0;
};

回溯法：

每一层递归就是一行，每一行选择一个，满足同行只能有一个。

用三个数组记录使用过的列、斜线1（主对角线方向），斜线2（副对角线方向）

同层递归中，每一个i代表使用的列，用used_col记录

对于主对角线，如

0 1 2 3

0 0 1 2 3

1 -1 0 1 2

2 -2 -1 0 1

3 -3 -2 -1 0

可以看到同一对角线上的i-j都是一样的，为了用数组作为哈希表记录，那么在i-j上加上n-1即可。

副对角线同理。

回溯的时候记得将占用的列和斜线复原。