🌕 52. N皇后 II

难度: 🌕

问题描述

---

解法

class Solution {
    int res = 0;
    public int totalNQueens(int n) {
        // 思路：
        int[][] board = new int[n][n];
        mySol(n, 0, board);
        return res;
    }

    private void mySol(int len, int row, int[][] board) {
        // 递归终止条件
        if(row == len) {
            res ++;
            return;
        }
        // row < len
        // 查找当前行可插入的列
        for(int j = 0; j < len; j ++) {
            if(isValid(len, board, row, j)) {
                board[row][j] = 1;
                mySol(len, row + 1, board);
                board[row][j] = 0;
            }
        }
    }

    private boolean isValid(int len, int[][] board, int row, int col) {
        // 垂直向上查找
        for(int i = 0; i < row; i ++) {
            if(board[i][col] == 1) {
                return false;
            }
        }
        // 左上方查找
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --) {
            if(board[i][j] == 1) {
                return false;
            }
        }
        // 右上方查找
        for(int i = row - 1, j = col + 1; i >= 0 && j < len; i --, j ++) {
            if(board[i][j] == 1) {
                return false;
            }
        }
        return true;
    }
}

---

输出