题解 | #N皇后问题#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int count = 0;
    public int Nqueen (int n) {
        // write code here
        //创建一个二维数组用来模拟棋盘并占位
        int[][] board = new int[n][n];
        
        dfs(n, 1, board);
        return count;
    }
    public void dfs(int n, int row, int[][] board) {
        //如果row等于n + 1，则计数+1
        
        if (row > n) {
            count++;
            return;
        }
        //遍历本行棋盘
        for (int i = 0; i < n; i++) {
            //System.out.print("行:" + row);
            //System.out.print("列:" + (i+1) + "   ");
            if (board[row - 1][i] == 1) {
                continue;
            }
            int[][] newBoard = new int[n][n];
            for (int q = 0; q < n; q++){
                for (int p = 0; p < n; p++) {
                    newBoard[q][p] = board[q][p];
                }
            }
            //将该棋子下方同列同斜线所有格子都标记
            for (int below = row -1; below < n; below++) {
                //正下方标记
                newBoard[below][i] = 1;
                //左斜下方标记
                if (i - (below- row + 1) >= 0) {
                    newBoard[below][i - (below-row + 1)] = 1;
                }
                //右斜下方标记
                if (i + (below- row + 1) < n) {
                    newBoard[below][i + (below-row + 1)] = 1;
                }
            } 
            //进入下一层
            
            dfs(n,row+1,newBoard);    
        }   
    }
}