java - 退出 void 递归 Java 函数的更顺畅的方法

Question

所以我编写了这个函数，它的行为类似于 Knuth 的 X 算法。仅作说明 - 该函数需要一个大的可能行矩阵，它会尝试从中选择构成合法解决方案的行的组合。

问题是，一旦我们找到解决方案，由于它是空的，该函数不会返回任何东西，而只是回溯(这意味着它会为递归深度的每个级别打印出数独)。

关于如何在找到解决方案时结束功能的任何建议？我目前正在使用 System.exit(0) 但这并不好，因为程序会在您找到解决方案的那一刻结束(因此您之后想做的任何事情都是不可能的 - 例如在数独数组上运行该函数并解决每个问题一个)。

代码在这里:

public static void solve(ArrayList<int[]> solution, ArrayList<int[]> coverMatrix) {

    if (Arrays.equals(solvedCase, workCase)) {
        //this means we found the solution

        drawSudoku(testOutput);
        System.exit(0);

    } else {

        //find the column we didnt yet cover
        int nextColToCover = findSMARTUnsatisfiedConstraint(coverMatrix, workCase);

        //get all the rows that MIGHT solve this problem
        ArrayList<int[]> rows = matchingRows(coverMatrix, nextColToCover);

        //recusively try going down every one of them
        for (int i = 0; i < rows.size(); i++) {

            //we try this row as solution
            solution.add(rows.get(i));

            //we remove other rows that cover same columns (and create backups as well)
            removeOtherRowsAndAdjustSolutionSet(coverMatrix);

            if (isSolutionPossible(coverMatrix)) {
                solve(solution, coverMatrix);
            }

            // here the backtracking occurs if algorithm can't proceed
            // if we the solution exists, do not rebuild the data structure
            if (!Arrays.equals(solvedCase, workCase)) {
                restoreTheCoverMatrix(coverMatrix);
            }
        }
    }
}

Answer 1

如果我没理解错的话，你想在得到第一个解时结束递归。您可以通过为方法设置 boolean 返回类型来实现此目的，并在获得第一个解决方案时返回 true :.

    public static boolean solve(ArrayList<int[]> solution, ArrayList<int[]> coverMatrix) {

if (Arrays.equals(solvedCase, workCase)) {
    //this means we found the solution

    drawSudoku(testOutput);
    return true;

} else {

    //find the column we didnt yet cover
    int nextColToCover = findSMARTUnsatisfiedConstraint(coverMatrix, workCase);

    //get all the rows that MIGHT solve this problem
    ArrayList<int[]> rows = matchingRows(coverMatrix, nextColToCover);

    //recusively try going down every one of them
    for (int i = 0; i < rows.size(); i++) {

        //we try this row as solution
        solution.add(rows.get(i));

        //we remove other rows that cover same columns (and create backups as well)
        removeOtherRowsAndAdjustSolutionSet(coverMatrix);

        if (isSolutionPossible(coverMatrix)) {
            boolean result = solve(solution, coverMatrix);
            if(result  == true) return result;//else continue
        }

        // here the backtracking occurs if algorithm can't proceed
        // if we the solution exists, do not rebuild the data structure
        if (!Arrays.equals(solvedCase, workCase)) {
            restoreTheCoverMatrix(coverMatrix);
        }
    }
    return false;
}