☆打卡算法☆LeetCode 52、N皇后II 算法解析

示例 1：
输入： n = 4
输出： 2
解释： 如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入： n = 1
输出： 1

public class Solution {
    public int TotalNQueens(int n) 
    {
        var dp = new bool[n, n];
        var res = 0;
        FindP(0, 0);
        return res;

        void FindP(int y, int nums)
        {
            if (nums == n) 
            {
                res++;
                return;
            }
            
            for (int x = 0; x < n; x++)
            {
                if (CanP(x, y))
                {
                    dp[y, x] = true;
                    FindP(y + 1, nums + 1); 
                    dp[y, x] = false; // 撤销
                }
            }
        }

        bool CanP(int x, int y)
        {
            // 上
            for (int i = y - 1; i >= 0; i--)
                if (dp[i, x]) return false;
            // 左上
            for (int i = y - 1, j = x - 1; i >= 0 &amp;&amp; j >= 0; i--, j--)
                if (dp[i, j]) return false;
            // 右上
            for (int i = y - 1, j = x + 1; i >= 0 &amp;&amp; j < n; i--, j++)
                if (dp[i, j]) return false;

            return true;
        }
    }
}