Parallel Sudoku Solver в Java

Question

У меня есть домашняя работа, которая требует реализации последовательной и параллельной версии решения sudoku в Java (с использованием ForkJoin Framework для параллельного).

Я написал последовательный, и он отлично работает. Алгоритмическая идея - это простое упражнение по обратному выводу: для каждой ячейки (начиная с верхнего левого угла таблицы), которая еще не заполнена, заполнить ее (последовательно и по одному) со всеми юридическими кандидатами (целое число от 1 до 9), пока вы не достигнете конца (строка 9 col 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' 

Answer 1

Во-первых, вы должны рассмотреть, что произойдет, если один поток заканчивает свою работу. Вы должны отметить, что он пытается сбросить ячейку до 0, но что, если есть еще одна под-нить, работающая с Cell?

Очевидно, что если другой поток, обращающийся к одной и той же Ячейке, пытается проверить, является ли это законным, возможно, это должно быть неправильное значение, потому что другой поток положил туда нуль!

Answer 2

Я думаю, вы должны передать копию из массива в новые темы. В вашем коде вы передаете один и тот же массив всем потокам, и они пытаются вставить правильное значение одновременно.