52.N-Queens II

朴灿烈づ我的快乐病毒、 2021-10-29 15:56 304阅读 0赞

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

![689069-20151219194929585-194789872.png][]

解题思路：回溯法。可以用一个大小为n的一维数组来表示皇后的摆放情况。a\[i\]=j表示第i行的皇后的摆放位置是第j列。我们假设前面k-1个皇后的摆放位置没有问题，我们如何判断第k个皇后的摆放位置是否有问题呢？相关的判断定义在函数place中，如果i从1到k-1,都没有a\[i\]==a\[k\]||abs(a\[i\]-a\[k\])==abs(i-k)成立，那表示第k个皇后的位置摆放的也没有问题。a\[i\]==a\[k\]表示两个皇后摆放在同一列，很显然不成立。怎么判断两个皇后摆放在同一条对角线上呢？先来个图示例一下：

![689069-20151219194930460-1902355973.png][]

如果两个皇后在同一条对角线上那么一定有abs(a\[i\]-a\[k\])==abs(i-k)成立，可以理解成两者在一个正方形的两个角上。

回溯法的思路是这样的，首先设k=1,每一次循环都是设置第k个皇后摆放的位置。当a\[k\]<=n&&!place(k)满足时，增加a\[k\],直至不满足条件退出内部循环，此时第k个皇后要不已经摆放到位，要不a\[k\]已经超过了n，不满足条件。进一步的，如果k=n,表示第n个皇后摆放到位，相应的又多了一种摆放情况。如果k<n,还要继续处理下一行皇后的摆放，k++。其他情况对应我们不满足要求的情况，此时我们应该回溯，对第k行的皇后摆放设置清空，k--，重新处理第k-1行皇后的摆放。

`class` `Solution {`

`private``:`

```int` `*a;`

```int` `sum;`

```bool` `place(``int` `k){`

```int` `i;`

```for``(i=1;i<k;i++){`

```if``(a[i]==a[k]||``abs``(a[i]-a[k])==``abs``(i-k))`

```return` `false``;`

```}`

```return` `true``;`

```}`

`public``:`

```int` `totalNQueens(``int` `n) {`

```int` `sum=0;`

```a=``new` `int` `[n+1];`

```memset``(a,0,(n+1)*``sizeof``(``int``));`

```int` `k=1;`

```while``(k>0){`

```a[k]++;//第k行开始放在第一纵列`

```while``(a[k]<=n&&!place(k))//a[k]放在第1到n行，且要保证摆放不破坏规则`

```a[k]++;`

```if``(a[k]<=n&&k==n){//最后的结果满足要求`

```sum++;`

```}`

```else``if``(a[k]<=n&&k<n)``//继续摆放下一行`

```k++;`

```else``//不符合要求，回溯`

```a[k--]=0;`

```}`

```return` `sum;`

```}`

`};`

转载于:https://www.cnblogs.com/zhoudayang/p/5059654.html

[689069-20151219194929585-194789872.png]: /images/20211029/a3c11871afe84fd19d8bf5d4a449b955.png
[689069-20151219194930460-1902355973.png]: /images/20211029/d47d096c6ad646bdac98d68fbfa9b17b.png