題目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

image

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

解法思路（一）

皇后之間不能相互攻擊什么意思？

• 皇后之間不能在同一行，同一列，同一對角線；

最后的解有什么樣的特征？

• 每一行只有一個皇后；
• 每一列只有一個皇后；
• 每一對角線只有一個皇后；

二維數(shù)組的對角線有什么特征？

• 每一條從右上到左下的對角線，橫縱坐標相加之和是一個常數(shù)；
• 每一條從左上到右下的對角線，橫縱坐標相減之差是一個常數(shù)；

如何回溯的找所有解？

• 一行一行的放皇后；
• 第一行放過皇后的列，第二行的皇后就不能放在這一列，故用一個數(shù)組 col 記錄哪些行上放過皇后；
• 同時，當一個皇后被放置后，有兩條對角線上也不能再放皇后了；
• 兩個方向的所有對角線是否有皇后，用兩個布爾數(shù)組 dia1 和 dia2 表示；
• dia1 表示從右上到左下的所有對角線，坐標 (row, col) 處于哪個對角線上，dia1[row + col] 就是的；
• dia2 表示從左上到右下的所有對角線，坐標 (row, col) 處于哪個對角線上，dia2[row - col + n - 1] 就是的；
• 每一行可以在哪落皇后，都是根據(jù) col dia1 dia2 的限制決定的，每一行可以落皇后的位置可以有多個，先在第一個位置落，如果進行到下一行發(fā)現(xiàn)落哪都不成了，那么回退到上一行，在下一個可以落皇后的位置落皇后，再去下一行落皇后，直到在最后一行成功落下皇后，一個解就找到了；
• 然后再一行行的向上回溯，回溯到每一個位置，都將該位置所處的 col dia1 dia2 置為未占用的狀態(tài)，然后在該行能放皇后的下一個位置放置皇后，直到該行所有能放置皇后的位置都放過了，然后回溯到上一行，將上一行能放置皇后的位置都試一遍，直到回溯到第一行的最后一個能放皇后的位置也試過了，那么所有的解就都找到了；

解法實現(xiàn)（一）

時間復(fù)雜度

• O(n^n)；

空間復(fù)雜度

• O(n)；

關(guān)鍵字

N Queens 回溯 遞歸 二維數(shù)組 對角線

實現(xiàn)細節(jié)

• Arrays.fill(row, '.'); 給一個 char 數(shù)組填充值的 API，比較少用，標出以注意；
• LinkedList 才有 addLast(E e) 和 removeLast() 這樣的 API，加以注意；
• dia2[rowIndex - i + n - 1] 用以表示從左上到右下的所有對角線的數(shù)組，橫縱坐標相減再加上個 n - 1 的偏移量就對應(yīng)到 dia2 上了；
• res 作為收集解的倉庫，存在于遞歸方法之外；

package leetcode._51;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution51_1 {

    private boolean[] cols;
    private boolean[] dia1;
    private boolean[] dia2;
    private ArrayList<List<String>> res;

    public List<List<String>> solveNQueens(int n) {

        cols = new boolean[n];
        // 表示從右上到左下的所有對角線上是否有皇后
        dia1 = new boolean[2 * n - 1];
        // 表示從左上到右下的所有對角線上是否有皇后
        dia2 = new boolean[2 * n - 1];
        res = new ArrayList<>();

        LinkedList<Integer> chessboard = new LinkedList<>();
        putQueen(n, 0, chessboard);

        return res;
    }

    private void putQueen(int n, int rowIndex, LinkedList<Integer> chessboard) {

        if (n == rowIndex) {
            res.add(generateOneSolution(n, chessboard));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!cols[i] && !dia1[rowIndex + i] && !dia2[rowIndex - i + n - 1]) {
                chessboard.addLast(i);
                cols[i] = true;
                dia1[rowIndex + i] = true;
                dia2[rowIndex - i + n - 1] = true;
                putQueen(n, rowIndex + 1, chessboard);
                dia2[rowIndex - i + n - 1] = false;
                dia1[rowIndex + i] = false;
                cols[i] = false;
                chessboard.removeLast();
            }
        }

        return;
    }

    private List<String> generateOneSolution(int n, List<Integer> chessboard) {

        assert n == chessboard.size();

        ArrayList<String> oneSolution = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[chessboard.get(i)] = 'Q';
            oneSolution.add(new String(row));
        }

        return oneSolution;
    }

}

返回 LeetCode [Java] 目錄