回溯法求八皇后问题

题目

在 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();
        }
    }
}