回溯算法数独所有解决方案失败

Question

我正在代码中看了几个小时，不知道我的失败在哪里。此代码应解决数独问题并找到所有解决方案。首先，它创建矩阵，在该矩阵中用0值表示空白，然后获取第一个空白点，即0值，并搜索可以在该点应用的所有值。之后，它递归地调用使“沿着树下走”的方法，并找到下一个空白点的解决方案。

这里是代码：

Main.java

Sudoku sd = new Sudoku(matrix);
long startTime = System.currentTimeMillis();
sd.solveBacktracking();
long finishTime = System.currentTimeMillis();
System.out.println("Time to result: " + (finishTime - startTime) + "ms");

Sudoku.java

public class Sudoku {

    int[][] solvedMatrix;
    private int leaves = 0, solutionNumber = 0, backtracking = 0;
    private ArrayList<Integer> saveValues = new ArrayList<>();
    private ArrayList<ArrayList<Integer>> D = new ArrayList<>();
    private boolean filledVariants = false;
    private static final int GRID_SIZE = 9;
    private boolean first = true;

    public Sudoku(int[][] solvedMatrix) {
        this.solvedMatrix = solvedMatrix;
    }

    public boolean isSafe(int number, int row, int column) {
        // uniques in row
        for (int i = 0; i < GRID_SIZE; i++)
            if (solvedMatrix[i][column] == number)
                return false;

        // uniques in column
        for (int i = 0; i < GRID_SIZE; i++)
            if (solvedMatrix[row][i] == number)
                return false;

        // uniques in section
        int rowStart = row - row % 3;
        int columnStart = column - column % 3;

        for (int i = rowStart; i < rowStart + 3; i++)
            for (int j = columnStart; j < columnStart + 3; j++)
                if (solvedMatrix[i][j] == number)
                    return false;

        return true;
    }

    public void findSaveValues(int row, int column) {
        if (saveValues.isEmpty()) {
            for (int n = 1; n <= GRID_SIZE; n++)
                if (isSafe(n, row, column))
                    saveValues.add(n);
        } else {
            saveValues.clear();
            for (int n = 1; n <= GRID_SIZE; n++)
                if (isSafe(n, row, column))
                    saveValues.add(n);
        }

    }

    public boolean solveBacktracking() {
// r - row, c - column
        for (int r = 0; r < GRID_SIZE; r++)
            for (int c = 0; c < GRID_SIZE; c++)
                if (solvedMatrix[r][c] == 0 && first) {
                    findSaveValues(r, c);
                    if (saveValues.size() == 0) return false;
                    for (Integer n : saveValues) { // <<<--- error invokes here
                        solvedMatrix[r][c] = n;
                        leaves++;
                        if (solveBacktracking())
                            return true;
                        else {
                            solvedMatrix[r][c] = 0;
                            backtracking++;
                        }
                        if (saveValues.size() != 0 && n.equals(saveValues.get(saveValues.size() - 1))) first = false;
                    }
                    return false;
                } else if (solvedMatrix[r][c] == 0 && !first) {
                    for (int n = 1; n <= 9; n++)
                        if (isSafe(n, r, c)) {
                            solvedMatrix[r][c] = n;
                            first = false;
                            leaves++;
                            if (solveBacktracking()) {
                                return true;
                            } else {
                                solvedMatrix[r][c] = 0;
                                backtracking++;
                            }
                        }
                    return false;
                }
        solutionNumber++;
        printSudoku();
        return true;
    }
}

这是我得到的错误，我不熟悉ArrayList的原因，所以我写了这个问题：

Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)
at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996)

在此行调用错误：for (Integer n : saveValues)

Answer 1

ConcurrentModificationException，这意味着您正在修改要迭代的集合。

在测试并调试代码后，已将GRID_SIZE的大小作为固定值。如果使用较小的网格进行测试，则会产生异常，但如果网格和var具有相同的大小，则可以正常工作。

import java.util.ArrayList;
import java.util.StringJoiner;


public class Sudoku {

int[][] solvedMatrix;
private int leaves = 0, solutionNumber = 0, backtracking = 0;
private ArrayList<Integer> saveValues = new ArrayList<>();
private ArrayList<ArrayList<Integer>> D = new ArrayList<>();
private boolean filledVariants = false;
private int GRID_SIZE ;
private boolean first = true;

public Sudoku(int[][] solvedMatrix) {
    this.solvedMatrix = solvedMatrix;
    GRID_SIZE = solvedMatrix.length;
}

public boolean isSafe(int number, int row, int column) {
    // uniques in row
    for (int i = 0; i < GRID_SIZE; i++)
        if (solvedMatrix[i][column] == number)
            return false;

    // uniques in column
    for (int i = 0; i < GRID_SIZE; i++)
        if (solvedMatrix[row][i] == number)
            return false;

    // uniques in section
    int rowStart = row - row % 3;
    int columnStart = column - column % 3;

    for (int i = rowStart; i < rowStart + 3; i++)
        for (int j = columnStart; j < columnStart + 3; j++)
            if (solvedMatrix[i][j] == number)
                return false;

    return true;
}

public void findSaveValues(int row, int column) {
    if (saveValues.isEmpty()) {
        for (int n = 1; n <= GRID_SIZE; n++)
            if (isSafe(n, row, column))
                saveValues.add(n);
    } else {
        saveValues.clear();
        for (int n = 1; n <= GRID_SIZE; n++)
            if (isSafe(n, row, column))
                saveValues.add(n);
    }

}

public boolean solveBacktracking() {
// r - row, c - column
    for (int r = 0; r < GRID_SIZE; r++) {
        for (int c = 0; c < GRID_SIZE; c++) {
            if (solvedMatrix[r][c] == 0 && first) {
                findSaveValues(r, c);
                if (saveValues.size() == 0) return false;
                for (Integer n : saveValues) { // <<<--- error invokes here
                    solvedMatrix[r][c] = n;
                    leaves++;
                    if (solveBacktracking())
                        return true;
                    else {
                        solvedMatrix[r][c] = 0;
                        backtracking++;
                    }
                    if (saveValues.size() != 0 && n.equals(saveValues.get(saveValues.size() - 1))) first = false;
                }
                return false;
            } else if (solvedMatrix[r][c] == 0 && !first) {
                for (int n = 1; n <= 9; n++)
                    if (isSafe(n, r, c)) {
                        solvedMatrix[r][c] = n;
                        first = false;
                        leaves++;
                        if (solveBacktracking()) {
                            return true;
                        } else {
                            solvedMatrix[r][c] = 0;
                            backtracking++;
                        }
                    }
                return false;
            }
        }
    }
    solutionNumber++;
    printSudoku();
    return true;
}

private void printSudoku() {
    for(int[] row: solvedMatrix ){
        StringJoiner joiner = new StringJoiner("|");
        for (int col : row) {
            joiner.add(String.valueOf(col));
        }
        System.out.println(joiner.toString());
    }
}

public static void main(String... args) {

    Sudoku sd = new Sudoku(new int[][]{new int[]{1, 2, 3}, new int[]{2, 3, 1}, new int[]{3, 1, 2}});
    long startTime = System.currentTimeMillis();
    sd.solveBacktracking();
    long finishTime = System.currentTimeMillis();
    System.out.println("Time to result: " + (finishTime - startTime) + "ms");
}

}

我没有测试您的逻辑...只是更正了异常。