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,然后返回。

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

代码实现