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中的并行数独求解器

回答

相关问题