Um ein Sudoku mit Grid-Größe von mehr als 9 * 9 zu lösen Multi-threading-parallele Ausführung verwenden

Question

Ich arbeite an einem Projekt, wo ich ein Sudoku-Rätsel lösen muss. N ist kleiner als gleich 20.

Ich habe einen Sudoku-Solver mit einem Gewinde geschrieben, der gut mit Rätseln funktioniert, die den N-Wert 5 haben, aber wenn ich den N-Wert wie N = 10 oder 20 erhöhe, reagiert der Code nicht mehr. Ich habe auch versucht, Thread-Pool (java.concurrent) und zuweisen N^2 Nummer des Threads parallel auszuführen. Aber es funktioniert nicht, kann mir jemand eine Lösung geben, die die Leistung verbessern kann.

Hier ist mein Single-Threaded-Ansatz:

public class SUDOKU { 

    public static int[][] grid; 

    public boolean solveSUDOKU() { 
     int row; 
     int col; 
     int[] blankCell = findBlankLocation(); 
     row = blankCell[0]; 
     col = blankCell[1]; 
     if (row == -1) { 
      // means will have filled the grid, return; 
      return true; 
     } 
     // we need to fill grid[row][col] cell 
     for (int i = 1; i <= grid.length; i++) { 
      // check if number i is safe for grid[row][col] cell 
      if (isSafe(row, col, i)) { 
       // means its safe to fill the number 
       grid[row][col] = i; 
       // fill the rest of the grid 
       if (solveSUDOKU()) { 
        return true; 
       } 
       // if we are here that means current selection of number didnt 
       // work, revert back the changes 
       grid[row][col] = 0; 
      } 
     } 
     return false; // This will cause the backtracking 
    } 

    public boolean isSafe(int row, int col, int n) { 
     // we need to check row contains number n OR 
     // Column contains number n OR 
     // Block in which cell appears contains number n 
     // If Any of the above statement is true, return false 
     if (!UsedInRow(row, n) 
       && !UsedInColumn(col, n) 
       && !UsedInBox((int) (row - row % Math.sqrt(grid.length)), 
         (int) (col - col % Math.sqrt(grid.length)), n)) { 
      return true; 
     } 
     return false; 
    } 

    // check if n not in particular row 
    public boolean UsedInRow(int row, int n) { 
     for (int i = 0; i < grid.length; i++) { 
      if (grid[row][i] == n) { 
       return true; 
      } 
     } 
     return false; 
    } 

    // check if n not in particular column 
    public boolean UsedInColumn(int col, int n) { 
     for (int i = 0; i < grid.length; i++) { 
      if (grid[i][col] == n) { 
       return true; 
      } 
     } 
     return false; 
    } 

    // check if n not in particular box 
    public boolean UsedInBox(int boxStartRow, int boxStartCol, int n) { 
     for (int i = 0; i < Math.sqrt(grid.length); i++) { 
      for (int j = 0; j < Math.sqrt(grid.length); j++) { 
       if (grid[i + boxStartRow][j + boxStartCol] == n) { 
        return true; 
       } 
      } 
     } 
     return false; 
    } 

    public int[] findBlankLocation() { 
     int[] cell = new int[2]; // cell[0]-row cell[1] -column 
     for (int i = 0; i < grid.length; i++) { 
      for (int j = 0; j < grid.length; j++) { 
       if (grid[i][j] == 0) { 
        cell[0] = i; 
        cell[1] = j; 
        return cell; 
       } 
      } 
     } 
     cell[0] = -1; 
     cell[1] = -1; 
     return cell; // means grid is full 
    } 

    public void print() { 
     for (int row = 0; row < grid.length; row++) { 
      if (row % Math.sqrt(grid.length) == 0) { 
       System.out.println(); // for more readability 
      } 
      for (int col = 0; col < grid.length; col++) { 
       if (col % Math.sqrt(grid.length) == 0) { 
        System.out.print(" "); // for more readability 
       } 
       System.out.print(grid[row][col] + " "); 

      } 
      System.out.println(); 
     } 
    } 

    public static void main(String[] args) { 
     grid = new int[][]{ 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; 
     SUDOKU s = new SUDOKU(); 
     if (s.solveSUDOKU()) { 
      s.print(); 
     } else { 
      System.out.println("NO SOLUTION"); 
     } 
    } 

} 

Answer 1

Die Dinge sind nicht so einfach. Sie werfen bei einem Problem nicht "parallel" und "mehr Threads" und Sie verbessern auf magische Weise die Leistung.

In Ihrem Fall haben Sie eine riesige Suchbaum zu decken. Bedeutung: Ihre Methoden könnten viele Millionen von Zeiten genannt werden.

Also die erste Sache zu tun: verstehen was Ihr Code macht.

Bedeutung: Sie können mit einfachen Druckanweisungen beginnen; oder indem Sie "Aufrufzähler" hinzufügen. Oder, wenn Sie nach vorhandenen Profiling Werkzeuge suchen, die Ihnen helfen, zu verstehen, in welche Teile Ihr Programm die meiste Zeit verbringt. Und dann beginnen Sie, nach Optimierungsmöglichkeiten zu suchen.

Eine erste, ganz naheliegend: Sie sind Rechen

Math.sqrt(grid.length) 

wie in 3 oder 5 verschiedenen Orten. Das ist eine teure Lösung. Die sqrt() könnte leicht vermieden werden (indem man den Wert einmal berechnet und ihn in eine Konstante setzt, die alle anderen Codes verwenden). Es könnte sich auch lohnen, in die Modulo-Berechnung zu schauen (obwohl es schwieriger sein könnte, sie loszuwerden).

Und darüber hinaus: um parallel Ihren Code zu teilen, müssen Sie verstehen, wie dieser Code seine Daten verarbeitet. Sie sehen, Sie können nicht nur für n Threads arbeiten gleichen einzigen Array von Zahlen. Denn plötzlich müssen Sie sich Gedanken machen über Konsistenz; Sie können nicht einen Thread Inhalt überschreiben, während ein anderer es liest.

also die wesentliche Antwort lautet:

• verstehen Ihren Code in der Single-Thread-Szenario
• Ihre Single-Thread-Lösung optimieren, alles unterlassen, die zu teuer ist

Und dann; wenn Sie tatsächlich verstehen, was Ihr Code macht; und du bist immer noch nicht glücklich; Dann könnten Sie versuchen, "mehr Threads" auf Ihr Problem zu werfen. Aber selbst dann: Bedenke, dass Threads nicht kostenlos sind. Beim Erstellen und Wechseln zwischen ihnen besteht ein erheblicher Aufwand. Für rein CPU-intensive Operationen mit mehr Threads wird nicht viel helfen.

Threads helfen mit einem höheren Durchsatz, wenn Sie viele IO-Operationen haben (und Threads darauf warten, dass Daten vom IO gelesen werden).