叉/加入数独求解器

Question

我有一个练习的问题。我需要使用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; 
} 

和对象塞拉代码：

public class Cella { 

private int current; 

public Cella() { 
    current = 0; 
} 

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

//Getter and Setter 

我的想法是让每个线程教师解决自身的数独，给予“合法值“的候选单元格。然后我收集一个ArrayList中的所有线程，并要求它们与最后一个分叉。每个线程都应该返回一个整数（0代表不成功，1代表成功），以便计算可以解决多少可能的数独问题。

然而，该算法仅覆盖数独的1/3：某点后，它停止填充细胞和它只是返回的，未完成它。

有人建议我在哪里，我在做错误（S）？

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; 
} 

当我复制阵列I与塞拉对象引用，而不是用一个新的填充它，所以它会导致数据争用。

复制的矩阵正确的方法是：

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

从您发布的代码中，我看不到任何问题可以解释您的问题。但是，您尚未发布可自行编译和执行的代码（称为最小工作或可验证示例，请参阅Wikipedia和StackOverflow's guide on creating one），也没有发布适用于您的应用程序的堆栈跟踪或输出。这使得你很难帮助你解决你的问题。如果你能为我提供更多，我愿意继续帮助你解决你的问题。

在此期间，我试图拼凑可以解决以下你的方法相同的问题的程序。它似乎工作，虽然我没有彻底的单元测试它。也许你可以将它与你所写的内容进行比较，并利用差异来发现问题。您至少需要Java 7才能编译并运行此代码。

如果这是作业作业，我建议在查看此列表之前向您的教授或TA查询。

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