Java中的並行數獨求解器

我有一個家庭作業，需要在Java中使用數獨求解器的順序和並行版本（使用ForkJoin框架，並行版本爲）。Java中的並行數獨求解器

我寫了順序的一個，它工作正常。算法的思想是一個簡單的回溯練習：對於每個單元格（從表格的左上角開始）尚未填充，填充它（依次，並一次一個）與所有合法候選人（從1到9）直到你到達矩陣的最後（第9列第9列）。如果您已達到最終結果，則增加解決方案編號。

我認爲實施並行版本只是爲每個有效的候選人找到一個特定的單元格，然後等待他們產生一個新的線程。它似乎不工作，我無法找到原因。

我張貼應該做的全部工作，希望找到一個很好的建議類：

class SolveSudoku extends RecursiveAction{ 
    private int i, j; 
    private int[][] cells; 

    SolveSudoku(int i, int j, int[][] cells){ 
     this.i = i; 
     this.j = j; 
     this.cells = cells; 
    } 

    @Override 
    protected void compute(){ 
     if (j == 9) { 
      j = 0; 
      if (++i == 9){ 
       solutions++; 
       System.out.println(solutions); 
       return; 
      } 
     } 

     if (cells[i][j] != 0){        // skip filled cells 
      SolveSudoku s = new SolveSudoku(i, j+1, cells); 
      s.compute(); 
      return; 
     } 


     ArrayList<Integer> vals = new ArrayList<Integer>(); 
     for (int val = 1; val <= 9; val++)     // try all the legal candidates for i, j 
      if (legal(i,j,val,cells)) 
       vals.add(val); 


     if(vals.size() == 1){       // only one, no new threads 
      cells[i][j] = vals.get(0); 
      new SolveSudoku(i, j+1, cells).compute(); 
     } 
     else{ 
      SolveSudoku threads[] = new SolveSudoku[vals.size()]; 
      int n = 0; 
      int first; 
      for(int k=0; k<vals.size(); k++){ 
       if(k == vals.size()-1){ 
        cells[i][j] = vals.get(k); 
        threads[n] = new SolveSudoku(i, j+1, cells); 
        threads[n].compute(); 
       } 
       else{ 
        cells[i][j] = vals.get(k); 
        threads[n] = new SolveSudoku(i, j+1, cells); 
        threads[n].fork(); 
       } 
       n++; 
      } 


      for(int k=0; k<threads.length-1; k++) 
       if(k != vals.size()-1) 
        threads[k].join(); 

     } 

     cells[i][j] = 0; 
     return; 
    }} 

new ForkJoinPool().invoke(new SolveSudoku(0, 0, M)); // where *M* is a sudoku instance to solve where all the unfilled cells contain '0'

來源

2016-12-25 Process0

那麼並行算法應該一次解決整個數獨？ – vatbub

是的，@vatbub！實際上，如果你定義了一個經典的* main *方法（在類定義之外的那一行），並且如果你在else塊的最後一行的下面添加了* threads [n] .join（）; *循環），一切工作正常。不知道錯誤在哪裏，但似乎線程做他們想做的事... – Process0

首先，你應該考慮一下，如果一個線程完成它的工作會發生什麼。你應該注意到它試圖將單元重置爲0，但是如果還有另一個子線程與Cell一起工作呢？

很明顯，如果訪問同一個Cell的另一個線程試圖檢查它是否合法，它可能必須輸入一個錯誤的值，因爲另一個線程將零置回！

來源

2016-12-26 16:26:43 ReadTheInitialLetters

這個答案提出了一個很好的觀點，但它會更好地作爲評論，因爲它不是解決問題的辦法。 – Aaron

不幸的是，我不認爲你是對的。由於「boss」線程等待其產生的每個孩子，所以在「boss」終止之後，子線程（它的子線程）不能執行。而且，由於我爲每個找到的新合法候選人創建了一個新實例，因此對象（* cells *字段）不在線程之間共享，因此我們不需要任何同步。 – Process0

如果孩子還沒有結束，b0ss會如何終止？問題是，還有其他子線程同時訪問同一個網格，並對其進行修改。可悲的是，這不是一種價值的呼喚，而是參照。 – ReadTheInitialLetters

我想你應該將數組的副本傳遞給新線程。在你的代碼中，你將相同的數組傳遞給所有的線程，並且他們嘗試同時插入正確的值。

來源

2016-12-30 02:30:22

Java中的並行數獨求解器

回答

相關問題