N皇后问题

描述

n皇后问题是将n个皇后放置在n*n的棋盘上,皇后彼此之间不能相互攻击。

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

每个解决方案包含一个明确的n皇后放置布局,其中“Q”和“.”分别表示一个女王和一个空位置。

样例
对于4皇后问题存在两种解决的方案:
[
[".Q..", // Solution 1
 "...Q",
 "Q...",
 "..Q."],
["..Q.", // Solution 2
 "Q...",
 "...Q",
 ".Q.."]
]

考察点
  • 回溯算法
答案
ArrayList<ArrayList<String>> lists = new ArrayList<>();

ArrayList<ArrayList<String>> solveNQueens(int n) {
    ArrayList<String> list = new ArrayList<>();
    List<Integer> hasNum = new ArrayList<>();
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    solveQueen(list, hashMap, n, -100, 0, hasNum);
    return lists;
}

/**
 * @param list
 * @param n
 * @param laseNum   上一行的数字
 * @param lineIndex 当前行
 * @param hasNum
 */
void solveQueen(ArrayList<String> list, HashMap<Integer, Integer> hashMap, int n, int laseNum, int lineIndex, List<Integer> hasNum) {
    if (lineIndex >= n) {
        lists.add(new ArrayList<>(list));
        return;
    } else {
        boolean flag = false;
        for (int j = 0; j < n; j++) {
            if (isValide(hashMap, lineIndex, j, hasNum)) {
                flag = true;
                hasNum.add(j);
                lineIndex++;
                list.add(getLine(j, n));
                hashMap.put(lineIndex - 1, j);
                solveQueen(list, hashMap, n, j, lineIndex, hasNum);
                list.remove(list.size() - 1);
                hashMap.remove(lineIndex - 1);
                lineIndex--;
                hasNum.remove(new Integer(j));
            }
        }
        if (!flag) {
            return;
        }
    }
}

private boolean isValide(HashMap<Integer, Integer> hashMap, int lineIndex, int j, List<Integer> hasNum) {
    if (hasNum.contains(j)) {
        return false;
    }
    for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
        float result = (entry.getKey() - lineIndex) * 1.0f / (entry.getValue() - j);
        if (Math.abs(result) == 1f) {
            return false;
        }
    }

    return true;
}

public String getLine(int j, int n) {
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < n; i++) {
        if (i == j) {
            str.append("Q");
        } else {
            str.append(".");
        }
    }
    return str.toString();
}