Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
这是n皇后问题的第二种问题形式，我们在上一题中将所有放置皇后的方式都找了出来并存储在集合中，现在，我们问题貌似变得简单了，只需要计算出总共有多少中放置皇后的方式即可。事实上，我们可以根据上一题的结果，直接计算集合中的元素个数就是本题的解，但是这显然是一种效率低下的方法，因为相对于本题来说，我们会做很多无用功。
上一题的链接：点击打开链接
那么，我们需要做的是，怎样尽可能的优化上一题的解法，并且达到计算此题的目的（参考了讨论区的思路）。
首先，我们注意到上一题中需要集合来存储每一种放置皇后的方式，而现在显然不需要了，只要一个变量用来存储次数即可。
第二，在此题中，我们不需要知道皇后具体存放在什么位置，只需要知道哪一行，哪一列，以及哪一条斜线已经放置了皇后就行了。总共有n行n列，
所以定义一个元素为n的boolean数组即可，用来表示第i列是否已经放置了皇后。又，左上到右下的斜线和左下到右上的斜线都有2n-1条，所以定义一个元素为2n-1的boolean数组即可，用来表示某一条斜线是否已经放置了皇后。
基于上述2点，我们在上一题的解法下做了如下优化，解决了此题。
下面是代码：
public class Solution { int count = 0; public int totalNQueens(int n) { boolean[] b1 = new boolean[n]; //第i列是否放置皇后 boolean[] b2 = new boolean[2*n-1]; //第i条斜线（左上到右下）是否放置皇后 boolean[] b3 = new boolean[2*n-1]; //第i条斜线（左下到右上）是否放置皇后 fon(0,b1,b2,b3,n); return count; } public void fon(int row, boolean[] b1, boolean[] b2, boolean[] b3 , int n){ if(row == n) { count++; return; } for(int i=0;i<n;i++){ int x1 = row+i; int x2 = row-i+n-1; if(b1[i] || b2[x1] || b3[x2]) //判断第row行，第i列是否可以放置皇后 continue; b1[i] = true; b2[x1] = true; b3[x2] = true; fon(row+1,b1,b2,b3,n); b1[i] = false; b2[x1] = false; b3[x2] = false; } } } 这种方法在LeetCode上超越了87.87%，是一种不错的解法！这2道题主要用到的是回溯算法，回溯算法的一种形象比喻就是： 我们去爬山有很多上山的入口，每个入口都有很多岔路，我们任意选择一个路口前行，当到达山顶或者遇到死路时，退回到上一个路口，再重新选择一条路前进。
