叉/加入數獨求解器

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