java - Sudoko Backtracker 中奇怪的堆栈溢出错误

Question

(免责声明:这个问题在 SO 上可能有 20 个不同的版本，但阅读其中大​​多数版本仍然没有解决我的问题)

大家好，这里是(相对)初学者程序员。所以我一直在尝试构建一个数独回溯器来填补不完整的谜题。即使 1-3 行完全为空(即用 0 填充)，它似乎也能正常工作，但是当更多的框开始清空时(特别是在第四行的 7-8 列周围，我停止在其中写入数字)，我收到堆栈溢出错误。代码如下:

import java.util.ArrayList;
import java.util.HashSet;

public class Sudoku
{
    public static int[][] puzzle = new int[9][9];
    public static int filledIn = 0;
    public static ArrayList<Integer> blankBoxes = new ArrayList<Integer>(); 
    public static int currentIndex = 0;
    public static int runs = 0;

    /**
     * Main method.
     */
    public static void main(String args[])
    {

        //Manual input of the numbers
        int[] completedNumbers = {0,0,0,0,0,0,0,0,0,
                0,0,0,0,0,0,0,0,0,
                0,0,0,0,0,0,0,0,0,
                0,0,0,0,0,0,0,0,0,
                0,0,0,0,0,0,0,3,4,
                8,9,1,2,3,4,5,6,7,
                3,4,5,6,7,8,9,1,2,
                6,7,8,9,1,2,3,4,5,
                9,1,2,3,4,5,6,7,8};


        //Adds the numbers manually to the puzzle array
        ArrayList<Integer> completeArray = new ArrayList<>();
        for(Integer number : completedNumbers) {
            completeArray.add(number);
        }
        int counter = 0;
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                puzzle[i][j] = completeArray.get(counter);
                counter++;
            }
        }

        //Adds all the blank boxes to an ArrayList.
        //The index is stored as 10*i + j, which can be retrieved
        // via modulo and integer division.
        boolean containsEmpty = false;
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(puzzle[i][j] == 0) {
                    blankBoxes.add(10*i + j);
                    containsEmpty = true;
                }
            }
        }
        filler(blankBoxes.get(currentIndex));
    }

    /**
     * A general method for testing whether an array contains a
     * duplicate, via a (relatively inefficient) sort.
     * @param testArray The int[] that is being tested for duplicates
     * @return True if there are NO duplicate, false if there
     * are ANY duplicates.
     */

    public static boolean checkDupl(int[] testArray) {
        for(int i = 0; i < 8; i++) {
            int num = testArray[i];
            for(int j = i + 1; j < 9; j++) {
                if(num == testArray[j] && num != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * If the puzzle is not full, the filler will be run. The filler is my attempt at a backtracker.
     * It stores every (i,j) for which puzzle[i][j] == 0. It then adds 1 to it's value. If the value
     * is already somewhere else, it adds another 1. If it is 9, and that's already there, it loops to 
     * 0, and the index beforehand is rechecked.
     */
    public static void filler(int indexOfBlank) {
        //If the current index is equal to the size of blankBoxes, meaning that we
        //went through every index of blankBoxes, meaning the puzzle is full and correct.
        runs++;
        if(currentIndex == blankBoxes.size()) {
            System.out.println("The puzzle is full!" + "\n");
            for(int i = 0; i < 9; i++) {
                System.out.println();
                for(int j = 0; j < 9; j++) {
                    System.out.print(puzzle[i][j]);                 
                }
            }
            System.out.println("\n" + "The filler method was run " + runs + " times");
            return;
        }

        //Assuming the puzzle isn't full, find the row/column of the blankBoxes index.
        int row = blankBoxes.get(currentIndex) / 10;
        int column = blankBoxes.get(currentIndex) % 10;
        //Adds one to the value of that box.
        puzzle[row][column] =  (puzzle[row][column] + 1);

        //Just used as a breakpoint for a debugger.
        if(row == 4 && column == 4){
            int x  = 0;
        }

        //If the value is 10, meaning it went through all the possible values:
        if(puzzle[row][column] == 10) {
            //Do filler() on the previous box
            puzzle[row][column] = 0;
            currentIndex--;
            filler(currentIndex);
        }
        //If the number is 1-9, but there are duplicates:
        else if(!(checkSingleRow(row) && checkSingleColumn(column) && checkSingleBox(row, column))) {
            //Do filler() on the same box.
            filler(currentIndex);
        }
        //If the number is 1-9, and there is no duplicate:
        else {
            currentIndex++;
            filler(currentIndex);
        }       
    }

    /**
     * Used to check if a single row has any duplicates or not. This is called by the 
     * filler method.
     * @param row
     * @return
     */
    public static boolean checkSingleRow(int row) {
        return checkDupl(puzzle[row]);
    }

    /**
     * Used to check if a single column has any duplicates or not. 
     * filler method, as well as the checkColumns of the checker.
     * @param column
     * @return
     */
    public static boolean checkSingleColumn(int column) {
        int[] singleColumn = new int[9];
        for(int i = 0; i < 9; i++) {
            singleColumn[i] = puzzle[i][column];
        }
        return checkDupl(singleColumn);         
    }

    public static boolean checkSingleBox(int row, int column) {
        //Makes row and column be the first row and the first column of the box in which
        //this specific cell appears. So, for example, the box at puzzle[3][7] will iterate
        //through a box from rows 3-6 and columns 6-9 (exclusive).
        row = (row / 3) * 3;
        column = (column / 3) * 3;

        //Iterates through the box
        int[] newBox = new int[9];
        int counter = 0;
        for(int i = row; i < row + 3; i++) {
            for(int j = row; j < row + 3; j++) {
                newBox[counter] = puzzle[i][j];
                counter++;
            }
        }
        return checkDupl(newBox);
    }
}

为什么我称其为奇怪的错误？几个原因:

1. 发生错误的框随机变化(给予或拿走一个框)。
2. 发生错误的实际代码行随机变化(似乎通常发生在填充方法中，但这可能只是因为这是最大的一个。
3. 不同的编译器在不同的框中有不同的错误(可能与 1 有关)

我认为我只是编写了低效的代码，因此虽然它不是实际的无限递归，但调用堆栈溢出错误已经足够糟糕了。但如果有人发现明显的问题，我很想听听。谢谢!

Answer 1

您的代码没有回溯。回溯意味着失败时返回:

 if(puzzle[row][column] == 10) {
        puzzle[row][column] = 0;
        currentIndex--;
        filler(currentIndex);// but every fail you go deeper
    }

一定有类似的东西:

public boolean backtrack(int currentIndex) {
    if (NoBlankBoxes())
        return true;
    for (int i = 1; i <= 9; ++i) {
        if (NoDuplicates()) {
            puzzle[row][column] = i;
            ++currentIndex;
            if (backtrack(currentIndex) == true) {
                return true;
            }
            puzzle[row][column] = 0;
        }
    }
    return false;
}