回溯法求八皇後問題

題目

在 n×n 棋盤上放置 n 個皇後，使她們互不沖突，需要每個皇後不能在同行、同列或者同對角線，求所有解。

分析

經典回溯法求解例題。定義cols[i]表示第 i 行的皇後所放的列，則其長度為n。逐行窮舉皇後的位置，一旦發現某一行無論如何放置都會沖突則回溯到上一行，從上一行的下個位置繼續窮舉。由于是逐行窮舉，是以不用考慮 0∘ 方向的沖突，隻需要考慮 90∘ ， 45∘ 和 135∘ 的沖突。

如果兩個點 x ，y位置為 45∘ 方向，則 x.row−x.col=y.row−y.col 。如果兩個點 x ，y位置為 135∘ 方向，則 x.row+x.col=y.row+y.col 。對于 8×8 的棋盤舉例如下

⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢0−1−2−3−4−5−6−710−1−2−3−4−5−6210−1−2−3−4−53210−1−2−3−443210−1−2−3543210−1−26543210−176543210⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢0123456712345678234567893456789104567891011567891011126789101112137891011121314⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

代碼

public class Queens {
    static List<int[]> results = new ArrayList<>();
    static int[] cols;

    static void solution(int curRow, int n) {
        if (curRow == n) {
            int[] newResult = new int[n];
            System.arraycopy(cols, , newResult, , n);
            results.add(newResult); // 獲得一個可行解
        } else {
            for (int j = ; j < n; j++) {
                cols[curRow] = j; // 對目前行的所有列窮舉
                if (!isConflicted(curRow)) {
                    solution(curRow + , n); // 不沖突就繼續窮舉下一行所有列
                } // 沖突則回溯到本行，考察下一列
                // 可能需要進行回溯的清理，這裡cols[curRow]直接更新不需要清理
            }
        }
    }

    static boolean isConflicted(int curRow) {
        for (int i = ; i < curRow; i++) {
            if (cols[curRow] == cols[i]) return true; // 90度
            if (curRow - cols[curRow] == i - cols[i]) return true; // 45度
            if (curRow + cols[curRow] == i + cols[i]) return true; // 135度
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        cols = new int[n];
        solution(, n);
        System.out.println(results.size());
        for (int[] cols : results) {
            for (int i = ; i < n; i++) {
                System.out.print(cols[i]);
                if (i != n - ) System.out.print(" ");
            }
            System.out.println();
        }
    }
}