叉/加入Sudoku Solver

Question

我的锻炼有问题。我需要找到给定sudoku的所有解决方案，使用叉/连接并行。我做了一个算法，但似乎不起作用。它在某一时刻停止了，我不知道为什么。

下面是代码：

private static int counter;
private Cella[][] sudoku;
private int i;
private int j;
private int theCounter = 0;

public SudokuMulti(Cella[][] sudoku) {
    this.sudoku = sudoku;
}

public SudokuMulti(Cella[][] sudoku, int i, int j) {
    this.sudoku = sudoku;
    this.i = i;
    this.j = j;
}

//DELETED

// Copy the sudoku matrix
private Cella[][] createCopy() {
    Cella[][] toReturn = new Cella[9][9];
    for (int i = 0; i < 9; i++) {
        System.arraycopy(sudoku[i], 0, toReturn[i], 0, 9);
    }
    return toReturn;
}

以及Cella对象的代码：

public class Cella {

private int current;

public Cella() {
    current = 0;
}

public Cella(int current) {
    this.current = current;
}

//Getter and Setter

考虑到候选单元的“法律价值”，我的想法是让每个线程都有能力解决自己的sudoku问题。然后，我收集ArrayList中的所有线程，并要求它们使用最后一个for进行分叉。每个线程都应该返回一个整数(0表示没有成功，1表示成功)，以便计算出可以解决多少可能的sudokus。

然而，该算法只覆盖sudoku的1/3 :在某个点之后，它停止填充单元格，它只是返回而不完成它。

有人能告诉我我在哪里做错了吗？

Answer 1

我找到了解决办法。以下是错误：

// Copy the sudoku matrix
private Cella[][] createCopy() {
    Cella[][] toReturn = new Cella[9][9];
    for (int i = 0; i < 9; i++) {
        // !!ERROR!!
        System.arraycopy(sudoku[i], 0, toReturn[i], 0, 9);
    }
    return toReturn;
}

当我复制数组时，我用Cella对象引用来填充它，而不是用一个新的引用，因此它会导致数据竞争。

复制矩阵的正确方法是：

private Cella[][] createCopy() {
    Cella[][] toReturn = new Cella[9][9];
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            toReturn[i][j] = new Cella(sudoku[i][j].getCurrent());
        }
    }
    return toReturn;
}

Answer 2

从你发布的代码来看，我看不出有什么问题可以解释你的问题。但是，您没有发布我可以自己编译和执行的代码(称为最低工作或可验证的示例，参见维基百科和StackOverflow的创建指南)，也没有为应用程序发布堆栈跟踪或输出。这使得帮助你解决问题变得很困难。如果你能为我提供更多，我愿意继续帮助你解决你的问题。

在此期间，我试图按照您的方法构建一个解决相同问题的程序。虽然我还没有对它进行彻底的单元测试，但它似乎很有效。也许您可以将其与您所写的内容进行比较，并利用这些差异来发现问题。您至少需要Java 7来编译和运行这段代码。

如果这是作业作业，我建议你的教授或助教检查后再看这份清单。

public class Main {
    public static void main( String[] args ) {
        Sudoku puzzle = new Sudoku();
          // Uncomment these lines to have a uniquely solvable Sudoku puzzle.  They are commented out to prove that this code can count multiple solutions.
//        puzzle.set(1, 0, 2);
//        puzzle.set(2, 0, 9);
//        puzzle.set(4, 0, 5);
//        puzzle.set(7, 0, 4);
//        puzzle.set(8, 0, 1);
//        puzzle.set(3, 1, 8);
//        puzzle.set(6, 1, 3);
//        puzzle.set(2, 2, 3);
        puzzle.set(3, 2, 7);
        puzzle.set(4, 2, 4);
        puzzle.set(5, 2, 9);
        puzzle.set(6, 2, 6);
        puzzle.set(3, 3, 4);
        puzzle.set(6, 3, 2);
        puzzle.set(7, 3, 1);
        puzzle.set(1, 4, 6);
        puzzle.set(3, 4, 3);
        puzzle.set(4, 4, 7);
        puzzle.set(5, 4, 1);
        puzzle.set(7, 4, 8);
        puzzle.set(1, 5, 4);
        puzzle.set(2, 5, 1);
        puzzle.set(5, 5, 6);
        puzzle.set(2, 6, 5);
        puzzle.set(3, 6, 9);
        puzzle.set(4, 6, 2);
        puzzle.set(5, 6, 8);
        puzzle.set(6, 6, 7);
        puzzle.set(2, 7, 4);
        puzzle.set(5, 7, 7);
        puzzle.set(0, 8, 3);
        puzzle.set(1, 8, 7);
        puzzle.set(4, 8, 6);
        puzzle.set(6, 8, 5);
        puzzle.set(7, 8, 2);

        SudokuSolver solver = new SudokuSolver(puzzle);
        long start = System.nanoTime();
        int totalSolutions = solver.compute();
        long end = System.nanoTime();
        System.out.println(totalSolutions);
        System.out.format("%f ms", (end - start) / 1e6);
    }

    private static class Sudoku {
        private final int[][] cells;

        Sudoku() {
            cells = new int[9][9];
        }

        Sudoku( Sudoku original ) {
            cells = new int[9][9];
            for (int column = 0; column < 9; ++column) {
                for (int row = 0; row < 9; ++row) {
                    set(column, row, original.get(column, row));
                }
            }
        }

        int get( int column, int row) {
            return cells[column][row];
        }

        void set( int column, int row, int value ) {
            cells[column][row] = value;
        }

        boolean isPlausible() {
            return columnsArePlausible() && rowsArePlausible() && blocksArePlausible();
        }

        private boolean columnsArePlausible() {
            boolean result = true;

            for (int column = 0; result && column < 9; ++column) {
                result = isColumnPlausible(column);
            }

            return result;
        }

        private boolean isColumnPlausible( int column ) {
            boolean result = true;

            boolean[] seen = new boolean[10];
            for (int row = 0; result && row < 9; ++row) {
                int value = get(column, row);
                if (value > 0 && seen[value]) {
                    result = false;
                } else {
                    seen[value] = true;
                }
            }

            return result;
        }

        private boolean rowsArePlausible() {
            boolean result = true;

            for (int row = 0; result && row < 9; ++row) {
                result = isRowPlausible(row);
            }

            return result;
        }

        private boolean isRowPlausible( int row ) {
            boolean result = true;

            boolean[] seen = new boolean[10];
            for (int column = 0; result && column < 9; ++column) {
                int value = get(column, row);
                if (value > 0 && seen[value]) {
                    result = false;
                } else {
                    seen[value] = true;
                }
            }

            return result;
        }

        private boolean blocksArePlausible() {
            boolean result = true;

            for (int column = 0; result && column < 9; column += 3) {
                for (int row = 0; result && row < 9; row += 3) {
                    result = isBlockPlausible(column, row);
                }
            }

            return result;
        }

        private boolean isBlockPlausible( int column, int row ) {
            boolean result = true;

            boolean[] seen = new boolean[10];
            for (int x = 0; result && x < 3; ++x) {
                for (int y = 0; result && y < 3; ++y) {
                    int value = get(column + x, row + y);
                    if (value > 0 && seen[value]) {
                        result = false;
                    } else {
                        seen[value] = true;
                    }
                }
            }

            return result;
        }
    }

    private static class SudokuSolver extends RecursiveTask<Integer> {
        private static final long serialVersionUID = 8759452522630056046L;

        private Sudoku state;
        private int column;
        private int row;

        SudokuSolver( Sudoku state ) {
            this.state = state;
            // These settings allow the search loop in compute() to increment first without asking questions about
            // whether this cell has been checked yet.
            column = -1;
            row = 8;
        }

        SudokuSolver( Sudoku state, int column, int row ) {
            this.column = column;
            this.row = row;
            this.state = state;
        }

        @Override
        protected Integer compute() {
            int viableSolutions = 0;

            if (state.isPlausible()) {
                int originalColumn = column;
                int originalRow = row;

                do {
                    if (row + 1 >= 9) {
                        ++column;
                        row = 0;
                    } else {
                        ++row;
                    }
                } while (column < 9 && state.get(column, row) != 0);

                if (column >= 9) {
                    viableSolutions = 1;
                } else {
                    List<SudokuSolver> solvers = new ArrayList<>();
                    for (int value = 1; value <= 9; ++value) {
                        Sudoku copy = new Sudoku(state);
                        copy.set(column, row, value);
                        solvers.add(new SudokuSolver(copy, column, row));
                    }
                    invokeAll(solvers);
                    for (SudokuSolver solver : solvers) {
                        viableSolutions += solver.join();
                    }
                }
            }

            return viableSolutions;
        }
    }
}

由于这段代码会计算出解决方案所需的时间，所以输出可能会有所不同，但我得到了

354
709.848410 ms