LeetCode 51 N-Queens

思路

dfs搜索，其实是排列型搜索permutation。利用一个List来存每一列上存了什么数字，索引就是行数，可以保证每一行只有一个数字。
搜索部分就是permutation模板实现，只是模板中的visit判断放入判断是否相互攻击的函数中了。
判断是否不会相互攻击：（1）每行只有一个：通过list索引自动解决
（2）每列只有一个：搜索所有已经存进list中的index是否与将加入的index重复
（3）左下-右上对角线：位于该对角线上的x+y为定值
（4）左上-右下对角线：位于该对角线上的x-y为定值
然后使用得到的list来画棋盘， 然后加入results中即可。

复杂度

时间复杂度O(n!)
空间复杂度O(n)

代码

public class Solution {
    /** @param n: The number of queens* @return: All distinct solutions*/public List<List<String>> solveNQueens(int n) {
    // write your code hereList<List<String>> results = new ArrayList<>();if (n <= 0) {
    return results;}helper(new ArrayList<>(), n, results);return results;}private void helper(List<Integer> col, int n, List<List<String>> results) {
    if (col.size() == n) {
    results.add(drawChessBoard(col));return;}for (int i = 0; i < n; i++) {
    if (!isValid(col, i)) {
    continue;}col.add(i);helper(col, n, results);col.remove(col.size() - 1);}}private boolean isValid(List<Integer> col, int colIndex) {
    int rowIndex = col.size();for (int row = 0; row < col.size(); row++) {
    // 扫描col中所有存在的，看是否与要加入的colIndex有重复// 其实就是替代了permutation模板中的visitif (col.get(row) == colIndex) {
    return false;}// 左下-右上 斜线if (row + col.get(row) == rowIndex + colIndex) {
    return false;}// 左上-右下 斜线if (row - col.get(row) == rowIndex - colIndex) {
    return false;}}return true;}private List<String> drawChessBoard(List<Integer> col) {
    List<String> result = new ArrayList<>();for (int i = 0; i < col.size(); i++) {
    StringBuilder sb = new StringBuilder();for (int j = 0; j < col.size(); j++) {
    sb.append(j == col.get(i) ? 'Q' : '.');}result.add(sb.toString());}return result;}
}