「＝１０＝」
Fork/Join Sudoku Solver
我的练习有问题。我需要使用 fork/join 并行性找到给定数独的所有解决方案。我做了一个算法，但它似乎不起作用。它在某个时候停止，我不明白为什么。
代码如下：
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
我的想法是，在给定候选单元格的 "legal values" 的情况下，让每个线程都能够解决自己的数独问题。然后，我将所有线程收集到一个 ArrayList 中，并要求它们与最后一个 for 进行分叉。每个线程都应该 return 一个整数（0 表示没有成功，1 表示成功）以计算可以解决多少个可能的数独。
然而，该算法只覆盖了 1/3 的数独：在某个点之后，它停止填充单元格，它只是 returns 没有完成。
有人可以告诉我哪里做错了吗？
从你发布的代码来看，我看不出任何问题可以解释你的问题。但是，您没有发布我可以自己编译和执行的代码（称为最小工作示例或可验证示例，请参阅 Wikipedia and Whosebug's guide on creating one），也没有发布应用程序的堆栈跟踪或输出。这使得很难帮助您解决问题。如果你能提供更多，我愿意继续帮助你解决你的问题。
与此同时，我尝试按照您的方法拼凑一个解决相同问题的程序。它似乎有效，尽管我还没有对它进行彻底的单元测试。也许您可以将它与您编写的内容进行比较，并利用差异来发现问题。您至少需要 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
我找到了解决办法。这是错误：
// 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;
}
我的练习有问题。我需要使用 fork/join 并行性找到给定数独的所有解决方案。我做了一个算法，但它似乎不起作用。它在某个时候停止，我不明白为什么。
代码如下：
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
我的想法是，在给定候选单元格的 "legal values" 的情况下，让每个线程都能够解决自己的数独问题。然后，我将所有线程收集到一个 ArrayList 中，并要求它们与最后一个 for 进行分叉。每个线程都应该 return 一个整数（0 表示没有成功，1 表示成功）以计算可以解决多少个可能的数独。
然而，该算法只覆盖了 1/3 的数独：在某个点之后，它停止填充单元格，它只是 returns 没有完成。
有人可以告诉我哪里做错了吗？
从你发布的代码来看，我看不出任何问题可以解释你的问题。但是，您没有发布我可以自己编译和执行的代码（称为最小工作示例或可验证示例，请参阅 Wikipedia and Whosebug's guide on creating one），也没有发布应用程序的堆栈跟踪或输出。这使得很难帮助您解决问题。如果你能提供更多，我愿意继续帮助你解决你的问题。
与此同时，我尝试按照您的方法拼凑一个解决相同问题的程序。它似乎有效，尽管我还没有对它进行彻底的单元测试。也许您可以将它与您编写的内容进行比较，并利用差异来发现问题。您至少需要 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
我找到了解决办法。这是错误：
// 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;
}