回溯数独解算器的递归问题[Java]

Question

问题：用Java编写回溯数独解算器，该解算器接收表示谜题的文件，将其转换为矩阵，然后使用递归回溯解决问题

问题：在我的解决方法中，它将尝试解决第一个空框，但不会越过该框

错误日志：

Exception in thread "main" java.lang.StackOverflowError at java.util.AbstractCollection.(AbstractCollection.java:49)
at java.util.AbstractList.(AbstractList.java:59)
at java.util.ArrayList.(ArrayList.java:108)
at java.util.ArrayList.(ArrayList.java:119)
at ssolver.solve(ssolver.java:67)
at ssolver.solve(ssolver.java:83)
at ssolver.solve(ssolver.java:83)
...

方法：

public static int[][] solve(int[][]puzzle, int x, int y){
        //using backtracking for brute force power of the gods(norse cause they obviously most b.a.
        ArrayList<Integer> list = new ArrayList<Integer>();
        //next for both  x and y
        int nextx, nexty=y;

        if(x == 8){
            nextx=0;
            nexty=y+1;
        }
        else{
            nextx=x++;
        }

        if(isSolved(puzzle))
            return puzzle;

        if(!(puzzle[y][x]==0))
            solve(puzzle, nextx, nexty);
        else{
            for(int i =1; i<10; i++){
                if(isTrue(puzzle, y, x, i))
                    list.add(i);
            }   
            for(int i : list){
                puzzle[y][x] = list.get(i);
                printPuzzle(puzzle);//prints here for testing 
                if(isSolved(puzzle)||(x==8&&y==8));
                else{
                    solve(puzzle, nextx, nexty);
                }
            }
        }

        return puzzle;              
    }

有人能告诉我哪里出了问题吗。如果我做错了什么事，在第一次发帖时提前道歉。 干杯

Answer 1

所采用的算法类似于用于解决八皇后难题的标准回溯，如图所示：http://en.wikipedia.org/wiki/Eight_queens_puzzle

下面是Bob Carpenter（http://www.colloquial.com/carp）提供的一个类

这个代码示例帮助我解决了一个数独游戏的回溯问题。 经过一点调查，我能够重新编码，以适应我的程序

如果您在理解此代码的逻辑时遇到问题，请回复消息

下面的代码是直接从他的源代码复制粘贴的

/**
 * The <code>Sudoku</code> class povides a static <code>main</code>
 * method allowing it to be called from the command line to print the
 * solution to a specified Sudoku problem.
 *
 * <p>The following is an example of a Sudoku problem:
 *
 * <pre>
 *            -
 * |   8   | 4   2 |   6   |
 * |   3 4 |       | 9 1   |
 * | 9 6   |       |   8 4 |
 *             -
 * |       | 2 1 6 |       |
 * |       |       |       |
 * |       | 3 5 7 |       |
 *             -
 * | 8 4   |       |   7 5 |
 * |   2 6 |       | 1 3   |
 * |   9   | 7   1 |   4   |
 *             -
 * </pre>
 *
 * The goal is to fill in the missing numbers so that
 * every row, column and box contains each of the numbers
 * <code>1-9</code>.  Here is the solution to the
 * problem above:
 *
 * <pre>
 *             -
 * | 1 8 7 | 4 9 2 | 5 6 3 |
 * | 5 3 4 | 6 7 8 | 9 1 2 |
 * | 9 6 2 | 1 3 5 | 7 8 4 |
 *             -
 * | 4 5 8 | 2 1 6 | 3 9 7 |
 * | 2 7 3 | 8 4 9 | 6 5 1 |
 * | 6 1 9 | 3 5 7 | 4 2 8 |
 *             -
 * | 8 4 1 | 9 6 3 | 2 7 5 |
 * | 7 2 6 | 5 8 4 | 1 3 9 |
 * | 3 9 5 | 7 2 1 | 8 4 6 |
 *             -
 * </pre>
 *
 * Note that the first row <code>187492563</code> contains
 * each number exactly once, as does the first column
 * <code>159426873</code>, the upper-left box
 * <code>187534962</code>, and every other row, column
 * and box.
 *
 * <p>The {@link #main(String[])} method encodes a problem as an array
 * of strings, with one string encoding each constraint in the problem
 * in row-column-value format.  Here is the problem again with
 * the indices indicated:
 *
 * <pre>
 *     0 1 2   3 4 5   6 7 8
 *               -
 * 0 |   8   | 4   2 |   6   |
 * 1 |   3 4 |       | 9 1   |
 * 2 | 9 6   |       |   8 4 |
 *               -
 * 3 |       | 2 1 6 |       |
 * 4 |       |       |       |
 * 5 |       | 3 5 7 |       |
 *              -
 * 6 | 8 4   |       |   7 5 |
 * 7 |   2 6 |       | 1 3   |
 * 8 |   9   | 7   1 |   4   |
 *               -
 * </pre>
 *
 * The <code>8</code> in the upper left box of the puzzle is encoded
 * as <code>018</code> (<code>0</code> for the row, <code>1</code> for
 * the column, and <code>8</code> for the value).  The <code>4</code>
 * in the lower right box is encoded as <code>874</code>.
 *
 * <p>The full command-line invocation for the above puzzle is:
 *
 * <pre>
 * % java -cp . Sudoku 018 034 052 076 \
 *                     113 124 169 171 \
 *                     209 216 278 284 \
 *                     332 341 356     \
 *                     533 545 557     \
 *                     608 614 677 685 \
 *                     712 726 761 773 \
 *                     819 837 851 874 \
 * </pre>
 *
 * <p>See <a href="http://en.wikipedia.org/wiki/Sudoku">Wikipedia:
 * Sudoku</a> for more information on Sudoku.
 *
 * <p>The algorithm employed is similar to the standard backtracking
 * <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle">eight
 * queens algorithm</a>.
 *
 * @version 1.0
 * @author <a href="http://www.colloquial.com/carp">Bob Carpenter</a>
 */
public class Sudoku2 {

    /**
     * Print the specified Sudoku problem and its solution.  The
     * problem is encoded as specified in the class documentation
     * above.
     *
     * @param args The command-line arguments encoding the problem.
     */
    public static void main(String[] args) {
        int[][] matrix = parseProblem(args);
        writeMatrix(matrix);
        if (solve(0,0,matrix))    // solves in place
            writeMatrix(matrix);
        else
            System.out.println("NONE");
    }

    static boolean solve(int i, int j, int[][] cells) {
        if (i == 9) {
            i = 0;
            if (++j == 9)
                return true;
        }
        if (cells[i][j] != 0)  // skip filled cells
            return solve(i+1,j,cells);

        for (int val = 1; val <= 9; ++val) {
            if (legal(i,j,val,cells)) {
                cells[i][j] = val;
                if (solve(i+1,j,cells))
                    return true;
            }
        }
        cells[i][j] = 0; // reset on backtrack
        return false;
    }

    static boolean legal(int i, int j, int val, int[][] cells) {
        for (int k = 0; k < 9; ++k)  // row
            if (val == cells[k][j])
                return false;

        for (int k = 0; k < 9; ++k) // col
            if (val == cells[i][k])
                return false;

        int boxRowOffset = (i / 3)*3;
        int boxColOffset = (j / 3)*3;
        for (int k = 0; k < 3; ++k) // box
            for (int m = 0; m < 3; ++m)
                if (val == cells[boxRowOffset+k][boxColOffset+m])
                    return false;

        return true; // no violations, so it's legal
    }

    static int[][] parseProblem(String[] args) {
        int[][] problem = new int[9][9]; // default 0 vals
        for (int n = 0; n < args.length; ++n) {
            int i = Integer.parseInt(args[n].substring(0,1));
            int j = Integer.parseInt(args[n].substring(1,2));
            int val = Integer.parseInt(args[n].substring(2,3));
            problem[i][j] = val;
        }
        return problem;
    }

    static void writeMatrix(int[][] solution) {
        for (int i = 0; i < 9; ++i) {
            if (i % 3 == 0)
                System.out.println("            -");
            for (int j = 0; j < 9; ++j) {
                if (j % 3 == 0) System.out.print("| ");
                System.out.print(solution[i][j] == 0
                    ? " "
                    : Integer.toString(solution[i][j]));

                System.out.print(' ');
            }
            System.out.println("|");
        }
        System.out.println("            -");
    }

}

Answer 2

StackOverflowError表示已超过递归深度限制

显然，对这个问题使用递归不是一个好主意

在没有递归的情况下实现这样的代码更难，但您没有其他选择

你可以从这篇文章Replace Recursion with Iteration中得到一些启发

Answer 3

请注意，sudoko拼图需要大约9*9=81的深度才能工作，因此这可能是一个过度的操作

另一个原因是你检查了所有可能的数字，所以它是9^9=387420489个可能的组合

您至少应该添加一个函数isValid来解决这个难题，以避免运行无效的“分支”并进一步使用它们

为了有效地解决这个问题，你应该使它易于使用，并且为每个单元格输入你可以使用的可能的数字

here's a link关于求解sudoko的工作原理（请看数字4）。在为每个单元格输入所有数字后，您所要做的就是一步一步地按照逻辑消除数字

只有在使用了所有逻辑规则之后，才可以使用递归方法（或itereation）。这将使您的算法比任何其他回溯算法更高效、更快