Come parallelizzare il risolutore di Sudoku usando Grand Central Dispatch?

Question

Come esercizio di programmazione, ho appena finito di scrivere un solutore di Sudoku che utilizza l'algoritmo di backtracking (vedere Wikipedia per un semplice esempio scritto in C).

Per fare un ulteriore passo avanti, vorrei utilizzare il GCD di Snow Leopard per parallelizzare questo in modo che venga eseguito su tutti i core della mia macchina. Qualcuno può darmi dei consigli su come dovrei fare questo e quali modifiche al codice dovrei fare? Grazie!

Matt

Answer 1

Per uno, poiché backtracking è una ricerca in profondità non è direttamente parallelizzabile, poiché qualsiasi risultato appena calcolato non può essere utilizzato essere usato direttamente da un altro thread. Invece, è necessario dividere il problema in anticipo, cioè il thread # 1 inizia con la prima combinazione per un nodo nel grafico di backtracking e procede alla ricerca del resto del sottografo. La discussione n. 2 inizia con la seconda combinazione possibile al primo e così via. In breve, per n discussioni trovare le n combinazioni possibili al livello superiore dello spazio di ricerca (non "forward-track"), quindi assegnare queste n punti di partenza per n discussioni.

Tuttavia, penso che l'idea sia fondamentalmente imperfetta: molte permutazioni di sudoku sono risolte nel giro di un paio di migliaia di passi avanti + backtrack e sono risolti in millisecondi su un singolo thread. Questo è infatti così veloce che anche il piccolo coordinamento richiesto per alcuni thread (supponiamo che i thread n riducano il tempo di calcolo a 1/n del tempo originale) su una multi-core/multi-CPU non è trascurabile rispetto a il tempo totale di funzionamento, quindi non è per nulla una soluzione più efficiente.

Answer 2

Sei sicuro di volerlo fare? Tipo, che problema stai cercando di risolvere? Se si desidera utilizzare tutti i core, utilizzare i thread. Se vuoi un risolutore di sudoku veloce, posso dartene uno che ho scritto, vedi l'output qui sotto. Se vuoi lavorare per te, vai avanti e usa GCD;).

Aggiornamento:

Non credo GCD è male, semplicemente non è terribilmente rilevante per il compito di risolvere i sudoku. GCD è una tecnologia per legare gli eventi della GUI al codice. In sostanza, GCD risolve due problemi, uno strano in che modo MacOS X aggiorna le finestre e fornisce un metodo migliorato (rispetto ai thread) di legare il codice agli eventi della GUI.

Non si applica a questo problema perché il Sudoku può essere risolto molto più velocemente di quanto una persona possa pensare (a mio modesto parere). Detto questo, se il tuo obiettivo era risolvere Sudoku più velocemente, dovresti usare i thread, perché vorresti usare direttamente più di un processore.

[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

Per favore fatemi sapere se si finisce per usarlo. È gestito dal mulino ANSI C, quindi dovrebbe funzionare su tutto. Vedi altri post per l'utilizzo.

#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; 
}