编辑代码

package backtracking;
import java.util.LinkedList;

public class Queue {
    //当前行curRow的col列是否是可以放的列
    private static boolean isCorrectColumn(int col, int curRow, int queueCount, int[] path) {
        boolean bCorrect = true;
        int leftup = col - 1;   
        int rightup = col + 1;

        for (int i = curRow - 1; i >= 0; --i) {//从当前行的上一行开始，到第一行。上一行的path和当前行的col列的值比较,因为path记录的是列号，说明哪一行(数组下标)的哪一列（对应的值）已经放了皇后
            if (path[i] == col) {//path的下标为i的值与col相等，说明i行的col列已经有值了，col就不是正确的位置了
                //在同一列   
                bCorrect = false;
                break;
            }

            if (leftup >= 0 && path[i] == leftup) {//同理，path的下标为i的值与col列的前一列col-1相等，说明左斜线上已经有皇后了，不是正确的位置
                //在同一左斜线上  
                bCorrect = false;
                break;
            }

            if ( rightup < queueCount && path[i] == rightup) {//path的下标为i的值与col列的后一列col+1相等，说明右斜线上已经有皇后了，不是正确的位置
                //在同一右斜线上
                bCorrect = false;
                break;
            }   
            //若上一行的同一列、左斜线上、右斜线上都没有皇后，则继续向上找，即进行斜线的延伸
            --leftup;   //往左斜线上延伸
            ++rightup;  //往右斜线上延伸
        }
        return bCorrect;
    }
    //寻找皇后可以放的位置
    //输入：皇后的人数，当前行，刚开始调用在第一行0（即每一次递归从哪行开始），存放每一行放皇后情况的数组，存放皇后问题解决方案的列表
    //输出：虽然没有return，但修改了存放皇后问题解决方案的列表，因此它即为输出
    public static void findQueuePos(int queueCount, int curRow, int[] path, LinkedList<int[]> solutions) {
        //递归结束条件：上次递归已经到最后一行，经过+1后，现在的curRow等于皇后人数则递归终止。
        if (queueCount == curRow) {
            solutions.add((int[])path.clone());//将递归到最后一行得到的path数组添加到列表中
            return;
        }

        //递归
        for (int i = 0; i < queueCount; ++i) {//有多少个皇后就每次循环多少列
            if (isCorrectColumn(i, curRow, queueCount, path)) {//调用当前行的i列是否是可以放的列的方法
                //该列可以放，则在path数组中记录它
                path[curRow] = i;
                //求当前节点的子节点，因为相当于在棋盘的下一行找了，所以得curRow+1。然后递归——调用自身，再对下一行的的每一列查找正确的列
                findQueuePos(queueCount, curRow + 1, path, solutions);
            }
        }
    }
    //解决皇后问题
    //输入：皇后的人数
    //输出：存有解决方案的列表
    public static LinkedList<int[]> solveQueueProblem(int queueCount) {
        LinkedList<int[]> solutions = new LinkedList<int[]>();//定义一个存放皇后问题解决方案的列表
        int[] path = new int[queueCount];

        findQueuePos(queueCount, 0,  path, solutions);
        return solutions;
    }

    //打印皇后问题
    //输入：皇后的人数，存有解决方案的列表
    public static void printQueueSolutions(int queueCount, LinkedList<int[]> solutions) {
        System.out.println("皇后问题有" + solutions.size() + "种解决方案：");
        for (int[] solution:solutions) {    //增强for遍历列表
            for (int i = 0; i < solution.length; ++i) {//行
                for (int j = 0; j < queueCount; ++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 = solveQueueProblem(4);
        printQueueSolutions(4, solutions);
    }
}