¿Cómo poner en paralelo el solucionador de Sudoku usando Grand Central Dispatch?

Question

Como ejercicio de programación, acabo de escribir un solucionador de Sudoku que usa el algoritmo de retroceso (ver Wikipedia para un ejemplo simple escrito en C).

Para llevar esto un paso más allá, me gustaría usar el GCD de Snow Leopard para paralelizar esto para que funcione en todos los núcleos de mi máquina. ¿Puede alguien darme consejos sobre cómo debo hacer esto y qué cambios de código debo hacer? ¡Gracias!

Matt

Answer 1

Por un lado, desde backtracking es una búsqueda en profundidad no es directamente paralelizable, ya que cualquier resultado recién calculada no puede ser utilizado ser utilizada directamente por otro hilo. En su lugar, debe dividir el problema temprano, es decir, el subproceso # 1 comienza con la primera combinación de un nodo en el gráfico de retroceso y continúa buscando el resto de ese subgráfico. El hilo # 2 comienza con la segunda combinación posible al principio y así sucesivamente. En resumen, para n hilos encontrar los n combinaciones posibles en el nivel superior del espacio de búsqueda (no "con visión de pista"), entonces asignar esos n puntos de partida para n hilos.

Sin embargo, creo que la idea es fundamentalmente defectuosa: muchas permutaciones de sudoku se resuelven en cuestión de un par de miles de pasos hacia adelante y hacia atrás, y se resuelven en milisegundos en un solo hilo. De hecho, es tan rápido que incluso la pequeña coordinación necesaria para unos pocos hilos (suponiendo que n hilos reducen el tiempo de cálculo a 1/n del tiempo original) en un multi-core/multi-CPU no es despreciable en comparación con el tiempo total de ejecución, por lo tanto, no es, por casualidad, una solución más eficiente.

Answer 2

¿Seguro que quieres hacer eso? ¿Qué problema estás tratando de resolver? Si quiere usar todos los núcleos, use hilos. Si quieres un solucionador de sudoku rápido, puedo darte uno que escribí, mira el resultado a continuación. Si quiere hacer un trabajo para usted, siga adelante y use GCD;).

actualización:

No creo GCD es malo, simplemente no es muy relevante para la tarea de resolver el sudoku. GCD es una tecnología para unir eventos GUI al código. Esencialmente, GCD resuelve dos problemas, una cuestión de cómo MacOS X actualiza las ventanas y proporciona un método mejorado (en comparación con los hilos) de vincular el código a los eventos GUI.

No se aplica a este problema porque el Sudoku puede resolverse significativamente más rápido de lo que una persona puede pensar (en mi humilde opinión). Dicho esto, si tu objetivo era resolver el Sudoku más rápido, querrías usar hilos, porque querrías usar directamente más de un procesador.

[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

Háganme saber si usted lo usa. Se ejecuta de la fábrica ANSI C, por lo que debe ejecutarse en todo. Ver otra publicación para uso.

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