编辑代码

import java.util.LinkedList;

public class EightQueen {
    // 判断是否在同一列或同一对角线上
    private static boolean isCorrectColumn(int col, int curRow, int queenCount, int[] path) {
        boolean bCorrect = true;
        int leftup = col - 1;
        int rightup = col + 1;

        for (int i = curRow - 1; i >= 0; --i) {
            if (path[i] == col) {
                // 在同一列
                bCorrect = false;
                break;
            }

            if (leftup >= 0 && path[i] == leftup) {
                // 在同一左斜线上
                bCorrect = false;
                break;
            }

            if (rightup < queenCount && path[i] == rightup) {
                // 在同一右斜线上
                bCorrect = false;
                break;
            }
            --leftup;
            ++rightup;
        }

        return bCorrect;
    }

    // 递归查找所有可能的解
    public static void findQueenPos(int queenCount, int curRow, int[] path, LinkedList<int[]> solutions) {
        if (queenCount == curRow) {
            // 找到一种解决方案，保存并返回
            solutions.add((int[])path.clone());
            return;
        }

        // 遍历所有列，找到可以放置皇后的位置
        for (int i = 0; i < queenCount; ++i) {
            if (isCorrectColumn(i, curRow, queenCount, path)) {
                // 可以放置皇后，继续递归查找下一行
                path[curRow] = i;
                findQueenPos(queenCount, curRow + 1, path, solutions);
            }
        }
    }

    // 解决八皇后问题，返回所有解决方案
    public static LinkedList<int[]> solveQueenProblem(int queenCount) {
        LinkedList<int[]> solutions = new LinkedList<int[]>();
        int[] path = new int[queenCount];

        findQueenPos(queenCount, 0,  path, solutions);
        return solutions;
    }

    // 输出所有解决方案
    public static void printQueenSolutions(int queenCount, LinkedList<int[]> solutions) {
        System.out.println("皇后问题有" + solutions.size() + "种解决方案：");
        for (int[] solution:solutions) {
            for (int i = 0; i < solution.length; ++i) {
                for (int j = 0; j < queenCount; ++j) {
                    if (j == solution[i]) {
                        System.out.print('O');
                    }
                    else {
                        System.out.print('X');
                    }
                }
                System.out.println();
            }

            System.out.println();
            System.out.println();
        }
    }

    public static void test() {
        LinkedList<int[]> solutions = solveQueenProblem(8);
        printQueenSolutions(8, solutions);
    }

    public static void main(String[] args){
        test();
    }
}