题解 | #N皇后问题#

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */

    static int cnt = 0;

    public int Nqueen (int n) {
        // write code here
        int[][] board = new int[n][n];
        cnt = 0;
        dfs(board, 0, n);
        return cnt;
    }

    public void dfs(int[][] board, int i, int n) {

        if (i >= n) {
            cnt++;
            return;
        }

        for (int j = 0; j < n; j++) {
            if (isValid(board, i, j)) {
                // 放棋子
                board[i][j] = 1;
                dfs(board, i + 1, n);
                // 复原
                board[i][j] = 0;
            }
        }
    }

    // 判断皇后摆在(x,y)是否合法
    public boolean isValid(int[][] board, int x, int y) {

        int n = board.length;

        for (int i = 0; i < n; i++) {
            if (board[i][y] == 1) {
                return false;
            }
        }

        for (int j = 0; j < n; j++) {
            if (board[x][j] == 1) {
                return false;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (x - i >= 0 && y - i >= 0 && board[x - i][y - i] == 1) {
                return false;
            }

            if (x + i < n && y - i >= 0 && board[x + i][y - i] == 1) {
                return false;
            }

            if (x - i >= 0 && y + i < n && board[x - i][y + i] == 1) {
                return false;
            }

            if (x + i < n && y + i < n && board[x + i][y + i] == 1) {
                return false;
            }
        }

        return true;
    }

    // 打印棋盘，以供检查
    public void printBoard(int[][] board,int n) {
        for (int k = 0; k < n; k++) {
            for (int l = 0; l < n; l++) {
                System.out.print(board[k][l] + " ");
            }
            System.out.println();
        }
    }
}