题解 | #N皇后问题#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    private int ans = 0;
    public int Nqueen (int n) {
        char[][] chess = new char[n][n];
        dfs(chess,0);
        return ans;
    }
    
    void dfs(char[][] chess,int row){
        if(row == chess.length){
            ans++;
            return ;
        }
        for(int i = 0; i < chess.length; i++){
            if(!isSafe(chess,row,i)) continue;
            chess[row][i] = 'Q';
            dfs(chess,row+1);
            chess[row][i] = ' ';
        }
    }
    
    boolean isSafe(char[][] chess,int row,int col){
        for(int i = 0; i < chess.length; i++){ // 判断行 列!
            if(chess[row][i] == 'Q') return false;
            if(chess[i][col] == 'Q') return false;
        }
        
        for(int i = row,j = col; i < chess.length && j < chess.length; i++,j++){ // 判断右下
            if(chess[i][j] == 'Q') return false;
        }
        for(int i = row,j = col; i >= 0 && j >= 0; i--,j--){// 左上
            if(chess[i][j] == 'Q') return false;
        }
        
        for(int i = row,j = col; i < chess.length && j >= 0; i++,j-- ){// 左下
            if(chess[i][j] == 'Q') return false;
        }
         
        for(int i  = row,j = col; i >= 0 && j < chess.length; i--,j++ ){// 右上
            if(chess[i][j] == 'Q') return false;
        }
        return true;
    }
    
    
}