Solveur de Sudoku parallèle en Java

Question

J'ai un devoir qui nécessite de mettre en œuvre une version séquentielle et parallèle d'un solveur de sudoku en Java (en utilisant le Framework ForkJoin pour le parallèle).

J'ai écrit le séquentiel et ça marche bien. L'idée algorithmique est un simple retour en arrière: pour chaque cellule (à partir du coin supérieur gauche de la table) non remplie, remplissez-la (séquentiellement, et une à la fois) avec tous les candidats légaux (entier de 1 à 9) jusqu'à la fin (rangée 9 col 9) de la matrice. Si vous avez atteint la fin, augmente le nombre de solutions.

Je pensais implémenter la version parallèle juste en engendrant un nouveau thread pour chaque candidat valide trouvé pour une cellule particulière, puis en les attendant .. Il semble ne pas fonctionner et je n'ai pas pu trouver la raison.

je poste la classe qui devrait faire tout le travail avec l'espoir de trouver un bon conseil:

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

D'abord, vous devriez considérer ce qui se passe si un thread termine son travail. Vous devriez noter qu'il essaie de réinitialiser la cellule à 0, mais qu'en est-il s'il y a un autre sous-thread qui travaille avec la cellule?

De toute évidence, si un autre thread accédant à la même cellule essaie de vérifier si elle est légale, il se peut qu'elle doive mettre une valeur erronée car un autre thread y remet un zéro!

Answer 2

Je pense que vous devriez passer le copier du tableau aux nouveaux threads. Dans votre code, vous passez le même tableau à tous les threads et ils essaient d'insérer la valeur correcte en même temps.