算法篇八回溯算法

回溯算法定义

回溯是一种通用的算法，把问题分步解决，在每一步都试验所有的可能，当发现已经找到一种方式或者目前这种方式不可能是结果的时候，退回上一步继续尝试其他可能。很多时候每一步的处理都是一致的。

当回溯用于树的时候，就是深度优先搜索。几乎所有可以用回溯解决的问题都可以表示为树。那么这俩在这里就几乎同义了。如果一个问题解决的时候显式地使用了树，那么就叫它DFS。

N皇后问题

https://leetcode-cn.com/problems/n-queens/


class Solution {
    public List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        // 下标表示行, 值表示存储在哪一列
        int[] a = new int[n];
        calNQueens(a, 0, n);
        return result;
    }

    private void calNQueens(int[] a, int row, int n) {
        // row = n代表n行都有皇后了
        if (row == n) {
            add(a);
            return;
        }
        // 对当前行每一列进行判断
        for (int column = 0; column < n; column++) {
            if (isOk(a, row, column, n)) {
                a[row] = column;
                // 当当前列符合条件, 则进行下一行的判断
                calNQueens(a, row + 1, n);
            }
        }
    }

    /**
     * 判断在当前坐标放上棋子, 是否满足所有条件
     *
     * @param a      棋盘
     * @param row    当前行
     * @param column 当前列
     * @param n      一共多少颗棋子
     * @return 是否满足条件
     */
    private boolean isOk(int[] a, int row, int column, int n) {
        // l代表左上对角线, r代表右上对角线
        // 上一行的左对角线所在点就是 column - 1, 右对角线 column + 1
        int l = column - 1, r = column + 1;
        // i代表行
        for (int i = row - 1; i >= 0; i--) {
            if (a[i] == column) return false;
            // 判断对角线, a[i] == l 就代表在某一行的l列有皇后, 是处在对角线上的
            if ((l >= 0 && a[i] == l) || (r < n && a[i] == r)) return false;
            // 每次左对角线坐标都要减1, 右对角线加1
            l--;
            r++;
        }
        return true;
    }

    /**
     * 把可以的排列添加到result列表里
     */
    private void add(int[] a) {
        List<String> list = new ArrayList<>();
        for (int row = 0; row < a.length; row++) {
            String cStr = "";
            for (int c = 0; c < a.length; c++) {
                cStr += a[row] == c ? "Q" : ".";
            }
            list.add(cStr);
        }
        result.add(list);
    }
}

算法篇八 回溯算法

回溯算法定义

N皇后问题

算法篇八回溯算法