时间戳

首页 > 解决方案 > 如何使用倒车法添加多个解决方案

java - 如何使用倒车法添加多个解决方案

问题描述

然而，我正在尝试学习回溯，虽然我想将所有解决方案添加到我的数组列表中，但它只包含我的方法找到的第一个解决方案。我检查了 isSafe 方法，它是正确的。唯一的问题是我的queensList 方法。您能否解释一下如何将所有解决方案添加到我的数组列表中。例如，对于 4x4 表，我的 ArrayList 的元素是

[0, 1, 0, 0]

[0, 0, 0, 1]

[1, 0, 0, 0]

[0, 0, 1, 0]

public static boolean queensList(int[][] aList, int r, int k, ArrayList<int[][]> qL) {
        if (r >= k) {
            qL.add(aList);
            return true;
        }
        for (int i = 0; i < k; i++) {

            if (isSafe(aList, r, i)) {
                aList[r][i] = 1;
                if (queensList(aList, r + 1, k, qL)) 
                    return true;
                aList[r][i] = 0;
            }
        }
        return false;
    }

    public static boolean isSafe(int[][] trying, int r, int c) {
        for (int i = 0; i < trying.length; i++) {
            if (trying[r][i] == 1 || trying[i][c] == 1)
                return false;
        }
        int i = 0;
        while (r - i < trying.length && 0 <= r - i && c - i < trying.length && 0 <= c - i || r - i < trying.length && 0 <= r - i && c + i < trying.length && 0 <= c + i
                || r + i < trying.length && 0 <= r + i && c - i < trying.length && 0 <= c - i || r + i < trying.length && 0 <= r + i && c + i < trying.length && 0 <= c + i) {
            if (r - i < trying.length && 0 <= r - i && c - i < trying.length && 0 <= c - i && trying[r - i][c - i] == 1)
                return false;
            if (r - i < trying.length && 0 <= r - i && c + i < trying.length && 0 <= c + i && trying[r - i][c + i] == 1)
                return false;
            if (r + i < trying.length && 0 <= r + i && c - i < trying.length && 0 <= c - i && trying[r + i][c - i] == 1)
                return false;
            if (r + i < trying.length && 0 <= r + i && c + i < trying.length && 0 <= c + i && trying[r + i][c + i] == 1)
                return false;
            i++;
        }
        return true;
    }

标签： javabacktrackingn-queensrecursive-backtracking

解决方案

你的函数的退出条件queensList应该是 only when (r >= k)，这意味着当行r结束k并且女王仍然安全时，这是一个有效的解决方案。

但是在您的实现中，当您在 for 循环中找到解决方案时，您也会返回，这意味着它没有完成整个for循环以找到所有可能的解决方案。

所以对你的回溯功能做一个小的改变，如下所示：

public static void queensList(int[][] aList, int r, int k, ArrayList<int[][]> qL) {
    //exit condition
    if (r >= k) {
        qL.add(aList);
        return;
    }
    for (int i = 0; i < k; i++) {
        if (isSafe(aList, r, i)) {
            aList[r][i] = 1;
            queensList(aList, r + 1, k, qL);
            aList[r][i] = 0;
        }
    }
}

推荐阅读