题解 | #N皇后问题#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int resNum = 0;
    public int Nqueen (int n) {
        // write code here
        // 用一个标记记录行号，每次从每一行中的每一列中选出一个位置，如果该位置符合条件
        // 则选择放皇后(每行只可能有一个皇后)，否则返回上一行，重新选择一列，如果最后选择到了最后一行也选择出了一个皇后，则此时
        // 标记的行号等于矩阵的总行数，代表成功选择出一个方案，然后返回，重新选当前行是否还有适合的，没有就
        // 返回上一行，重新选，没有就选择上一行这样子循环，直到返回到第一行，重新选择下一列（循环），然后判断是否适合放皇后
        // 记录每个皇后的位置，利用一个一维数组，下标是行号，值是列号，代表一个皇后所在的位置
        int[] queenPos = new int[n];
        int row = 0;
        recursion(row, n, queenPos);
        return resNum;
    }
    
    public void recursion(int row, int n, int[] queenPos){
        // 结束条件
        if(row == n){
            resNum++;
            return;
        }
        // 遍历每一行的每一列
        for(int j=0; j<n; j++){
            if(ifRightPos(row,j,queenPos)){
                // 回退的时候会覆盖
                queenPos[row] = j;
                recursion(row+1,n,queenPos);
            }
        }
        return;
        
    }
    // 用于判断某个位置是否是合理的位置可以放置皇后
    public boolean ifRightPos(int row, int line, int[] queenPos){
        // 遍历整个queenPos的每个皇后，判断当前传递过来的下标是否和这些皇后同行同列同斜线
        for(int i=0; i<row; i++){
            // 同行         同列                      同斜线
            if(row == i || line == queenPos[i] || Math.abs(row-i) == Math.abs(line-queenPos[i])){
                return false;
            }
        }
        return true;
    }
}