八皇后

问题一

判断是否在同一条斜线
是否在同一条斜线就是两个点p(a,b),q(c,d)形成的斜率是否为正负1
1）斜率为1，a-c / b-d = 1，移项后a-b = c-d，横纵坐标之差相等
1）斜率为-1，a-c / b-d = -1，移项后a+b = c+d，横纵坐标之差相等

以四皇后举个例子

image.png

代码清单一

结果数组只记录包含元素的坐标，行是下标，列是元素值

public class N_Queues {
    /*
   思路：DFS+剪枝
   1, 提出理论
   2, 证明理论
   3, 编码实践
   4, 修正理论
   */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList();
        dfs(res, new ArrayList<Integer>(), n, 0, 1);
        return res;
    }

    public void dfs(List<List<String>> res, List<Integer> path,  int n, int r, int count) {
        if (r > n - 1) { // 到达最大行，判断当前方案是否可行
            if (count < n) {
                // 维护路径，拿到当前节点
                // path.remove(path.size() - 1);
                return;
            }
            // 添加到结果集
            res.add(new ArrayList(path));
            // 维护路径,不需要维护了
            // path.remove(path.size() - 1);
            return;
        }
        for (int c = 0; c < n; c++) { // c代表列，进入每一行都要逐列判断该列是否合法
            if (!check(r, c, path)) {
                continue;
            }
            path.add(c);
            dfs(res, path, n, r + 1, count + 1);
            // 维护路径
            path.remove(path.size() - 1);
        }
    }

    // 不同行，不同列，不同主对角线，不同负对角线
    public boolean check(int r, int c, List<Integer> tmp) {
        for (int i = 0; i < tmp.size(); i++) {
            if (r == i
                    || c == tmp.get(i)
                    || (r - c == i - tmp.get(i))
                    || (r + c == i + tmp.get(i))) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        N_Queues n_queues = new N_Queues();
        // [[1, 3, 0, 2], [2, 0, 3, 1]]
        System.out.println(n_queues.solveNQueens(4));
    }
}

代码清单二

public class N_Queues1 {
    /*
   思路：DFS+剪枝
   1, 提出理论
   2, 证明理论
   3, 编码实践
   4, 修正理论
   */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList();
        dfs(res, new ArrayList<Integer>(), n, 0, 1);
        return res;
    }

    public void dfs(List<List<String>> res, List<Integer> path, int n, int r, int count) {
        if (r > n - 1) { // 到达最大行，判断当前方案是否可行
            if (count < n) {
                // 维护路径，拿到当前节点
                // path.remove(path.size() - 1);
                return;
            }
            // 添加到结果集
            // res.add(new ArrayList(path));
            // [1, 3, 0, 2] => [".Q..","...Q","Q...","..Q."]
            List<String> tmp = new ArrayList<>();
            // 升维，一维 => 二维
            for (Integer elem : path) {
                StringBuffer sb = new StringBuffer();
                for (int j = 0; j < n; j++) {
                    if (j == elem) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                tmp.add(sb.toString());
            }
            res.add(tmp);
            // 维护路径,不需要维护了
            // path.remove(path.size() - 1);
            return;
        }
        for (int c = 0; c < n; c++) { // c代表列，进入每一行都要逐列判断该列是否合法
            if (!check(r, c, path)) {
                continue;
            }
            path.add(c);
            dfs(res, path, n, r + 1, count + 1);
            // 维护路径
            path.remove(path.size() - 1);

        }
    }

    // 不同行，不同列，不同主对角线，不同负对角线
    public boolean check(int r, int c, List<Integer> path) {
        for (int i = 0; i < path.size(); i++) {
            if (r == i
                    || c == path.get(i)
                    || (r - c == i - path.get(i))
                    || (r + c == i + path.get(i))) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        N_Queues1 n_queues = new N_Queues1();
        // [[1, 3, 0, 2], [2, 0, 3, 1]]
        System.out.println(n_queues.solveNQueens(4));
    }
}

for (int c = 0; c < n; c++) { // c代表列，进入每一行都要逐列判断该列是否合法
    if (check(r, c, path)) {
        path.add(c);
        dfs(res, path, n, r + 1, count + 1);
        // 维护路径
        path.remove(path.size() - 1);
    }
}

将判断行r作为递归的出口改为判断count作为递归的出口

public void dfs(List<List<String>> res, List<Integer> path, int n, int r, int count) {
    if (count > n) { // 放置皇后的数量 > n，方案可行
        List<String> tmp = new ArrayList<>();
        // 升维，一维 => 二维
        for (Integer elem : path) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < n; j++) {
                if (j == elem) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            tmp.add(sb.toString());
        }
        res.add(tmp);
        return;
    }
    for (int c = 0; c < n; c++) { // c代表列，进入每一行都要逐列判断该列是否合法
        if (check(r, c, path)) {
            path.add(c);
            dfs(res, path, n, r + 1, count + 1);
            // 维护路径
            path.remove(path.size() - 1);
        }
    }
}

递归回溯模板

递归

void f() {
     if(符合边界条件) {
       ///////
        return;
    }

     //某种形式的调用
     f();
}

回溯
回溯：递归的一种，或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。

void dfs(int 当前状态) {
    if(当前状态为边界状态) {
        记录或输出
        return;
    }
    for(i=0;i<n;i++)    {    //横向遍历解答树所有子节点
       //扩展出一个子状态。
       修改了路径记录
       if(子状态满足约束条件) {
          dfs(子状态)
       }
        恢复路径记录//回溯部分
    }
}