Wie parallelisiert man den Sudoku-Solver mit Grand Central Dispatch?

Question

Als Programmierübung habe ich gerade einen Sudoku-Solver geschrieben, der den Backtracking-Algorithmus verwendet (siehe Wikipedia für ein einfaches in C geschriebenes Beispiel).

Um noch einen Schritt weiter zu gehen, möchte ich den GCD von Snow Leopard parallelisieren, so dass er auf allen Kernen meiner Maschine läuft. Kann mir jemand Hinweise geben, wie ich das machen soll und welche Codeänderungen ich vornehmen soll? Vielen Dank!

Matt

Answer 1

Zum einen, da Backtracking ist eine Tiefensuche es nicht direkt parallelisierbaren ist, da jedes neu berechnetes Ergebnis nicht verwendet werden, kann direkt von einem anderen Thread verwendet werden. Stattdessen müssen Sie das Problem früh aufteilen, d. H. Thread Nr. 1 beginnt mit der ersten Kombination für einen Knoten in dem Backtracking-Graphen und fährt damit fort, den Rest dieses Subgraphen zu durchsuchen. Thread # 2 beginnt mit der zweiten möglichen Kombination beim ersten und so weiter. Kurz gesagt, für n Themen finden die n möglichen Kombinationen auf der obersten Ebene des Suchraumes (nicht „vorwärts-track“), dann ordnen Sie diese n Ausgangspunkte zu n Fäden.

Aber ich denke, die Idee ist grundsätzlich fehlerhaft: Viele Sudoku-Permutationen werden in einigen tausend Forward + Backtracking-Schritten gelöst und innerhalb von Millisekunden in einem einzigen Thread gelöst. Dies ist in der Tat so schnell, dass sogar die kleine Koordination für ein paar Threads (vorausgesetzt, dass n Threads Rechenzeit auf 1/n der ursprünglichen Zeit reduzieren) auf einem Multi-Core/Multi-CPU ist nicht vernachlässigbar im Vergleich zu Die Gesamtlaufzeit ist also keine effizientere Lösung.

Answer 2

Sind Sie sicher, dass Sie das tun möchten? Wie, welches Problem versuchen Sie zu lösen? Wenn Sie alle Kerne verwenden möchten, verwenden Sie Threads. Wenn Sie einen schnellen Sudoku-Löser haben wollen, kann ich Ihnen einen geben, den ich geschrieben habe, siehe Ausgabe unten. Wenn du Arbeit für dich selbst machen willst, mach weiter und benutze GCD;).

aktualisieren:

Ich glaube nicht GCD ist schlecht, es ist einfach nicht sehr relevant für die Aufgabe Sudoku zu lösen. GCD ist eine Technologie, um GUI-Ereignisse mit Code zu verknüpfen. Im Wesentlichen löst GCD zwei Probleme, einen Quirk in der Art und Weise, wie MacOS X Windows aktualisiert, und bietet eine verbesserte Methode (im Vergleich zu Threads), Code an GUI-Ereignisse zu binden.

Es gilt nicht für dieses Problem, weil Sudoku wesentlich schneller gelöst werden kann, als eine Person denken kann (meiner bescheidenen Meinung nach). Wenn Sie jedoch Sudoku schneller lösen möchten, sollten Sie Threads verwenden, da Sie direkt mehr als einen Prozessor verwenden möchten.

[bear@bear scripts]$ time ./a.out ..1..4.......6.3.5...9.....8.....7.3.......285...7.6..3...8...6..92......4...1... 
[----------------------- Input Data ------------------------] 

*,*,1 *,*,4 *,*,* 
*,*,* *,6,* 3,*,5 
*,*,* 9,*,* *,*,* 

8,*,* *,*,* 7,*,3 
*,*,* *,*,* *,2,8 
5,*,* *,7,* 6,*,* 

3,*,* *,8,* *,*,6 
*,*,9 2,*,* *,*,* 
*,4,* *,*,1 *,*,* 

[----------------------- Solution 01 ------------------------] 

7,6,1 3,5,4 2,8,9 
2,9,8 1,6,7 3,4,5 
4,5,3 9,2,8 1,6,7 

8,1,2 6,4,9 7,5,3 
9,7,6 5,1,3 4,2,8 
5,3,4 8,7,2 6,9,1 

3,2,7 4,8,5 9,1,6 
1,8,9 2,3,6 5,7,4 
6,4,5 7,9,1 8,3,2 


real 0m0.044s 
user 0m0.041s 
sys 0m0.001s 

Answer 3

Bitte lassen Sie mich wissen, wenn Sie es am Ende verwenden. Es wird von der Mühle ANSI C gefahren, also sollte alles laufen. Siehe anderen Beitrag zur Verwendung.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

short sudoku[9][9]; 
unsigned long long cubeSolutions=0; 
void* cubeValues[10]; 
const unsigned char oneLookup[64] = {0x8b, 0x80, 0, 0x80, 0, 0, 0, 0x80, 0, 0,0,0,0,0,0, 0x80, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x80,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}; 

int ifOne(int val) { 
    if (oneLookup[(val-1) >> 3] & (1 << ((val-1) & 0x7)) ) 
    return val; 
    return 0; 
} 


void init_sudoku() { 
    int i,j; 
    for (i=0; i<9; i++) 
    for (j=0; j<9; j++) 
     sudoku[i][j]=0x1ff; 
} 

void set_sudoku(char* initialValues) { 
    int i; 
    if (strlen (initialValues) != 81) { 
    printf("Error: inputString should have length=81, length is %2.2d\n", strlen(initialValues)); 
    exit (-12); 
    } 
    for (i=0; i < 81; i++) 
    if ((initialValues[i] > 0x30) && (initialValues[i] <= 0x3a)) 
     sudoku[i/9][i%9] = 1 << (initialValues[i] - 0x31) ; 
} 

void print_sudoku (int style) { 
    int i, j, k; 
    for (i=0; i < 9; i++) { 
    for (j=0; j < 9; j++) { 
     if (ifOne(sudoku[i][j]) || !style) { 
     for (k=0; k < 9; k++) 
      if (sudoku[i][j] & 1<<k) 
      printf("%d", k+1); 
     } else 
     printf("*"); 
     if (!((j+1)%3)) 
     printf("\t"); 
     else 
     printf(","); 
    } 
    printf("\n"); 
    if (!((i+1) % 3)) 
     printf("\n"); 
    } 
} 

void print_HTML_sudoku() { 
    int i, j, k, l, m; 
    printf("<TABLE>\n"); 
    for (i=0; i<3; i++) { 
    printf(" <TR>\n"); 
    for (j=0; j<3; j++) { 
     printf(" <TD><TABLE>\n"); 
     for (l=0; l<3; l++) { printf("  <TR>"); for (m=0; m<3; m++) { printf("<TD>"); for (k=0; k < 9; k++) { if (sudoku[i*3+l][j*3+m] & 1<<k) 
      printf("%d", k+1); 
      } 
      printf("</TD>"); 
     } 
     printf("</TR>\n"); 
     } 
    printf(" </TABLE></TD>\n"); 
    } 
    printf(" </TR>\n"); 
    } 
    printf("</TABLE>"); 
} 



int doRow() { 
    int count=0, new_value, row_value, i, j; 
    for (i=0; i<9; i++) { 
    row_value=0x1ff; 
    for (j=0; j<9; j++) 
     row_value&=~ifOne(sudoku[i][j]); 
    for (j=0; j<9; j++) { 
     new_value=sudoku[i][j] & row_value; 
     if (new_value && (new_value != sudoku[i][j])) { 
     count++; 
     sudoku[i][j] = new_value; 
     } 
    } 
    } 
    return count; 
} 

int doCol() { 
    int count=0, new_value, col_value, i, j; 
    for (i=0; i<9; i++) { 
    col_value=0x1ff; 
    for (j=0; j<9; j++) 
     col_value&=~ifOne(sudoku[j][i]); 
    for (j=0; j<9; j++) { 
     new_value=sudoku[j][i] & col_value; 
     if (new_value && (new_value != sudoku[j][i])) { 
     count++; 
     sudoku[j][i] = new_value; 
     } 
    } 
    } 
    return count; 
} 

int doCube() { 
    int count=0, new_value, cube_value, i, j, l, m; 
    for (i=0; i<3; i++) 
    for (j=0; j<3; j++) { 
     cube_value=0x1ff; 
     for (l=0; l<3; l++) 
     for (m=0; m<3; m++) 
      cube_value&=~ifOne(sudoku[i*3+l][j*3+m]); 
     for (l=0; l<3; l++) 
     for (m=0; m<3; m++) { 
      new_value=sudoku[i*3+l][j*3+m] & cube_value; 
      if (new_value && (new_value != sudoku[i*3+l][j*3+m])) { 
      count++; 
      sudoku[i*3+l][j*3+m] = new_value; 
      } 
     } 
    } 
    return count; 
} 

#define FALSE -1 
#define TRUE 1 
#define INCOMPLETE 0 

int validCube() { 
    int i, j, l, m, r, c; 
    int pigeon; 
    int solved=TRUE; 

    //check horizontal 
    for (i=0; i<9; i++) { 
    pigeon=0; 
    for (j=0; j<9; j++) 
     if (ifOne(sudoku[i][j])) { 
     if (pigeon & sudoku[i][j]) return FALSE; 
     pigeon |= sudoku[i][j]; 
     } else { 
     solved=INCOMPLETE; 
     } 
    } 

    //check vertical 
    for (i=0; i<9; i++) { 
    pigeon=0; 
    for (j=0; j<9; j++) 
     if (ifOne(sudoku[j][i])) { 
     if (pigeon & sudoku[j][i]) return FALSE; 
     pigeon |= sudoku[j][i]; 
     } 
     else { 
     solved=INCOMPLETE; 
     } 
    } 

    //check cube 
    for (i=0; i<3; i++) 
    for (j=0; j<3; j++) { 
     pigeon=0; 
     r=j*3; c=i*3; 
     for (l=0; l<3; l++) 
     for (m=0; m<3; m++) 
     if (ifOne(sudoku[r+l][c+m])) { 
      if (pigeon & sudoku[r+l][c+m]) return FALSE; 
      pigeon |= sudoku[r+l][c+m]; 
     } 
     else { 
      solved=INCOMPLETE; 
     } 
    } 

    return solved; 
} 

int solveSudoku(int position) { 
    int status, i, k; 
    short oldCube[9][9]; 

    for (i=position; i < 81; i++) { 

    while (doCube() + doRow() + doCol()); 

    status = validCube() ; 
    if ((status == TRUE) || (status == FALSE)) 
     return status; 


    if ((status == INCOMPLETE) && !ifOne(sudoku[i/9][i%9])) { 
     memcpy(&oldCube, &sudoku, sizeof(short) * 81) ; 
     for (k=0; k < 9; k++) { 
     if (sudoku[i/9][i%9] & (1<<k)) { 
      sudoku[i/9][i%9] = 1 << k ; 
      if (solveSudoku(i+1) == TRUE) { 

      /* return TRUE; */ 
      /* Or look for entire set of solutions */ 

      if (cubeSolutions < 10) { 
       cubeValues[cubeSolutions] = malloc (sizeof(short) * 81) ; 
       memcpy(cubeValues[cubeSolutions], &sudoku, sizeof(short) * 81) ; 
      } 

      cubeSolutions++; 
      if ((cubeSolutions & 0x3ffff) == 0x3ffff) { 
       printf ("cubeSolutions = %llx\n", cubeSolutions+1); 
      } 

      //if (cubeSolutions > 10) 
      // return TRUE; 

      } 

      memcpy(&sudoku, &oldCube, sizeof(short) * 81) ; 
     } 
     if (k==8) 
      return FALSE; 
     } 

    } 
    } 

    return FALSE; 
} 


int main (int argc, char** argv) { 
    int i; 
    if (argc != 2) { 
    printf("Error: number of arguments on command line is incorrect\n"); 
    exit (-12); 
    } 

    init_sudoku(); 
    set_sudoku(argv[1]); 

    printf("[----------------------- Input Data ------------------------]\n\n"); 
    print_sudoku(1); 

    solveSudoku(0); 
    if ((validCube()==1) && !cubeSolutions) { 
    // If sudoku is effectively already solved, cubeSolutions will not be set 
    printf ("\n This is a trivial sudoku. \n\n"); 
    print_sudoku(1); 
    } 


    if (!cubeSolutions && validCube()!=1) 
    printf("Not Solvable\n"); 
    if (cubeSolutions > 1) { 
    if (cubeSolutions >= 10) 
     printf("10+ Solutions, returning first 10 (%lld) [%llx] \n", cubeSolutions, cubeSolutions); 
    else 
     printf("%llx Solutions. \n", cubeSolutions); 
    } 

    for (i=0; (i < cubeSolutions) && (i < 10); i++) { 
    memcpy (&sudoku, cubeValues[i], sizeof(short) * 81); 
    printf("[----------------------- Solution %2.2d ------------------------]\n\n", i+1); 
    print_sudoku(0); 
    //print_HTML_sudoku(); 
    } 
    return 0; 
}