题解 | #N皇后问题，空间(n^2),时间O(n!)#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型
     * @return int整型
     */
    public int Nqueen (int n) {
        //map[i][j] == 1表示（i，j）已经放了皇后
        int map[][] = new int[n][n] ;
        return help(map , 0) ;
    }
    //从索引为row的行开始，一共有多少种放置方法
    public int help(int[][] map , int row) {
        if(row == map.length) return 1 ;//如果最后一层已经放置了皇后，那么这就是一种情况
        int count = 0 ;
        //本行的每一个位置有多少种情况
        for(int i = 0 ; i < map[0].length ; i ++) {
            if(!isOK(map , row , i)) continue ;
            map[row][i] = 1 ;//标记
            //确定当前位置后，看其余的层数能房都找种
            count += help(map , row + 1) ;
            map[row][i] = 0 ;//恢复现场，移除标记
        }
        return count ;
    }
    //检查map[i][j]是否能够放置皇后
    public boolean isOK(int[][] map , int row , int col) {
        for(int i = 0 ; i < row ; i ++) {
            for(int j = 0 ; j < map[0].length ; j ++) {
                //同一对角线，或同列的情况下 是否有已经放置的皇后
                if((Math.abs(i - row) == Math.abs(j - col) && map[i][j] == 1) ||
                  ((j == col) && map[i][j] == 1)) {
                    return false ;
                }
            }
        }
        return true ;
    }
}