Как распараллелить судоку с помощью Grand Central Dispatch?

Question

Как упражнение по программированию, я только что закончил писать решатель Судоку, который использует алгоритм обратного слежения (см. Wikipedia для простого примера, написанного на C).

Чтобы сделать этот шаг дальше, я хотел бы использовать GCD Snow Leopard, чтобы распараллелить это, чтобы он работал на всех ядрах моей машины. Может ли кто-нибудь дать мне указания на то, как я должен это делать и какие изменения кода я должен сделать? Благодаря!

М-М:

Answer 1

С одной стороны, так как возвратов является поиск в глубину не напрямую параллелизуемое, так как любой вновь вычисленное результат не может быть использован непосредственно использоваться другой нитью. Вместо этого вы должны разделить проблему раньше, т. Е. Поток # 1 начинается с первой комбинации для узла в графе обратного отслеживания и продолжает искать остальную часть этого подграфа. Тема № 2 начинается со второй возможной комбинации в первой и т. Д. Короче говоря, для п нитей найти п возможных комбинации на верхнем уровне пространства поиска (не «вперед-трека»), а затем присвоить эти п отправных точек для п нитей.

Однако я думаю, что идея в корне ошибочна: многие перестановки судоку разрешаются в течение нескольких тысяч шагов вперед + назад и решаются в миллисекундах на одном потоке. Это на самом деле так быстро, что даже небольшая координация требуется для нескольких потоков (предположим, что потоки n сокращают время вычислений до 1/n исходного времени) на многоядерном/многопроцессорном процессоре, общее время работы, таким образом, это не случайно более эффективное решение.

Answer 2

Вы уверены, что хотите этого сделать? Например, какую проблему вы пытаетесь решить? Если вы хотите использовать все ядра, используйте потоки. Если вы хотите быстро решить sudoku, я могу дать вам тот, который я написал, см. Выход ниже. Если вы хотите сделать работу самостоятельно, продолжайте использовать GCD;).

Update:

Я не думаю, что НОД плохо, это просто не очень отношение к задаче решения судоку. GCD - это технология привязки графических интерфейсов к коду. По сути, GCD решает две проблемы: Quirk в том, как MacOS X обновляет окна и предоставляет улучшенный метод (по сравнению с потоками) привязки кода к событиям GUI.

Это не относится к этой проблеме, поскольку судоку можно решить значительно быстрее, чем человек может думать (по моему скромному мнению). При этом, если ваша цель состояла в том, чтобы быстрее решать Sudoku, вы бы хотели использовать потоки, потому что вы хотели бы использовать более одного процессора.

[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

Пожалуйста, дайте мне знать, если вы закончите использовать его. Он запускается на станке ANSI C, поэтому должен работать на всех. См. Другое сообщение для использования.

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