通过n皇后问题搞明白回溯算法

    // 这个方法用来判断我们接下来要放置的皇后在不在某个已经放置的皇后的水平方向、垂直方向或者斜对角，
    // 如果都不，那我们找到了一个合适的位置来放一个新皇后了
    static boolean isValidPosition(int proposedRow, int proposedCol, List<Integer> solution) {
        //对当前棋盘上的所有皇后，我们都要做判断
        for (int oldRow = 0; oldRow < proposedRow; ++oldRow) {
            int oldCol = solution.get(oldRow);
            int diagonalOffset = proposedRow - oldRow;
            if (oldCol == proposedCol ||
                    oldCol == proposedCol - diagonalOffset ||
                    oldCol == proposedCol + diagonalOffset) {
                return false;
            }
        }
        return true;
    }

static void solveNQueensRec(int n, List<Integer> solution, int row, List<List<Integer>> results) {
        // 最后一行也找到了一个合适的位置，我们成功找到了一种解决方案
        if (row == n) {
            results.add(new ArrayList<Integer>(solution));
            return;
        }

        // 从每一行的第一列开始尝试
        for (int i = 0; i < n; ++i) {
            // 对于走到最后一列还没都没有找到合适的点的情况， 当前递归结束，调用栈回到上一层的递归流程，会回去执行前面一行里剩余的情况
            if (isValidPosition(row, i, solution)) {
                solution.set(row, i);
                solveNQueensRec(n, solution, row + 1, results);
            }
        }
    }

static int solveNQueens(int n, List<List<Integer>> results) {
        List<Integer> solution = new ArrayList<Integer>(n);
        for (int i = 0; i < n; ++i) {
            solution.add(-1);
        }
        solveNQueensRec(n, solution, 0, results);
        return results.size();
    }

 // 这边栈里我们只存放列的值
    static int solveNQueens(int n, List<List<Integer>> results) {

        List<Integer> solution = new ArrayList<Integer>(n);
        Stack<Integer> solStack = new Stack<Integer>();

        for (int i = 0; i < n; ++i) {
            solution.add(-1);
        }

        int row = 0;
        int col = 0;

        while(row < n){
            while(col < n){
                // 当前可以放置皇后，继续下一行的寻找
                if(isValidPosition(row, col, solution)){
                    solStack.push(col);
                    solution.set(row, col);
                    row++;
                    col = 0;
                    break;
                }
                // 当前位置不行，尝试在下一列放置皇后
                col++;
            }

            // 找到了当前行的最后一列
            if(col == n){
                // 说明前面一行还没到最后一列，执行pop操作回到前一行寻找过程
                if(!solStack.empty()){
                    col = solStack.peek() + 1;
                    solStack.pop();
                    row--;
                }
                else{
                    // 只有第一行也走到了最后一列，并且所有路径都尝试过了，此时由于上面if里的逻辑栈空了，说明我们的寻找过程该结束了
                    break;
                }
            }

            if(row == n){
                // 我们找到一种符合条件的摆放位置
                results.add(new ArrayList<Integer>(solution));

                // 回溯到前一行
                row--;
                col = solStack.peek() + 1;
                solStack.pop();
            }
        }
        return results.size();
    }