public class EightQueens {

    private static final int N = 8; // 棋盘大小
    private int[] queens; // 记录皇后所在的列
    private int count; // 解的数量

    public EightQueens() {
        queens = new int[N];
        count = 0;
    }

    /**
     * 判断第n行的第c列是否可以放置皇后
     */
    private boolean canPlace(int n, int c) {
        for (int i = 0; i < n; i++) {
            // 检查是否在同一列或同一对角线
            if (queens[i] == c || Math.abs(queens[i] - c) == Math.abs(i - n)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 递归地放置皇后
     */
    private void placeQueens(int n) {
        if (n == N) { // 所有皇后都已放置，找到一个解
            count++;
            printSolution();
        } else {
            for (int c = 0; c < N; c++) {
                if (canPlace(n, c)) {
                    queens[n] = c; // 放置皇后
                    placeQueens(n + 1); // 继续放置下一行
                }
            }
        }
    }

    /**
     * 打印当前的解
     */
    private void printSolution() {
        System.out.println("解 #" + count + ":");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (queens[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.placeQueens(0);
        System.out.println("总共有 " + eightQueens.count + " 个解.");
    }
}