本题用递归求解（没有回溯）

题目要求，在n阶矩阵中，找到所有n个皇后摆放方式，摆放要求不能在同一直线1，同一列，以及同一对角线

刚刚开始刷递归以及dfs、回溯的题，在这里总结一下模板，

1. 找出终结条件，即使递归结束的条件 本题为 行数递归到最后一行，代表选择完毕返回
2. 剪枝是对于回溯过程中不合题目要求或者重复的选项进行删除
3. 然后写一个for循环 ，在for循环中判断符合条件的情况，进行递归，递归后还原

本题思路很简单，请看代码注释

import java.util.*;

public class Solution {
  //pos 数组 下标为 row 值为col 
  //pos[row] = col
  
   //记录总摆放方法数
    int count = 0;
  //isValid 方法 判断当前行是否符合题目要求，不在同一行，不在同一列，不在对角线上 
  //注意循环以row为界，因为是判断是否和已经摆放了的位置有冲突
    public boolean isValid(int[] pow,int row ,int col){
        for (int i = 0; i < row; i++) {
            if ( row == i || col == pow[i] || 
                Math.abs(row - i) == Math.abs(col - pow[i])){
              
                return false;
            }
        }
        return true;
    }
	//递归
    public void backTrace(int n ,int row ,int[] pos){
        if (row == n){//终止条件，当递归到最后一行，已经全部摆放完成，返回
            count++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(pos,row,i)){
                pos[row] = i;//判断如果合法，那放入该位置
                backTrace(n,row+1,pos);//寻找下一行是否有合法位置
            }
        }

    }

    public int Nqueen (int n) {
        // write code here
        int[] pos = new int[n];
        backTrace(n,0,pos);
        return count;
    }
}