N-Queens II

##题目

####N-Queens II

Follow up for N-Queens problem.

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

##解题思路
该题和N-Queens基本相同,只是最后返回的是解得个数。但是这里需要注意的是:用java写的时候,基本数据类型是值传递,因此不能用int来作为递归的结果参数。

##算法代码
代码采用JAVA实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
public int totalNQueens(int n) {
ArrayList<Integer> res = new ArrayList<Integer>(); //这里不能用int类型
res.add(0);
helper(n,0,new int[n],res);
return res.get(0);
}
//columnForRow 记录每一行中皇后的位置
void helper(int n,int row,int[] columnForRow, ArrayList<Integer> res)
{

if(row==n)
{
int num=res.get(0)+1;
res.set(0,num);
return;
}else{
for(int i=0;i<n;i++)
{
columnForRow[row]=i;
if(check(row,columnForRow))
{
helper(n,row+1,columnForRow,res);
}
}
}
}

boolean check(int row,int[] columnForRow)
{

for(int i=0;i<row;i++)
{
if(columnForRow[row]==columnForRow[i] || Math.abs(columnForRow[row]-columnForRow[i])==(row-i))
return false;
}
return true;
}
}

Comments