刷题日志--N皇后问题 5.4

N皇后

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/n-queens/

问题叙述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1

输入

n = 4

输出

[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]

解释

如上图所示，4 皇后问题存在两个不同的解法。

示例 2

输入

n = 1

输出

[[“Q”]]

分析

一层一层的暴搜，遍历每个格子的时候，需要判断本行本列和两条对角线上没有别的Queen，但由于我们是一层一层遍历的，所以不需要当前行的下方，所以我们只需要判断一下上方，左上方和右上方是否存在别的Queen，如果存在的话，就直接跳过本次操作

Code

class Solution {
int n;
char[][] map;
List<List<String>> res = new ArrayList<>();

public List<List<String>> solveNQueens(int _n) {
    n = _n;
    map = new char[n][n];
    for (char[] c : map) Arrays.fill(c, '.');
    dfs(0);
    return res;
}

void dfs(int row) {
    if (row == n) {
        List<String> list = new ArrayList<>();
        for (char[] c : map) list.add(new String(c));
        res.add(list);
    }
    //对当前行行进行暴搜
    for (int col = 0; col < n; col++) {
        //存在别的Queen，直接跳过
        if (judge(row, col)) continue;
        map[row][col] = 'Q';
        //对下一行进行暴搜
        dfs(row + 1);
        //回溯
        map[row][col] = '.';
    }
}

//检测Queen
boolean judge(int row, int col) {
    //判断上方
    for (int i = 0; i < row; i++)
        if (map[i][col] == 'Q') return true;
    //判断左上方
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (map[i][j] == 'Q') return true;
    //判断右上方
    for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++)
        if (map[i][j] == 'Q') return true;
    return false;
}
}

N皇后II

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/n-queens-ii/