ग्रांड सेंट्रल डिस्पैच का उपयोग करके सुडोकू सॉल्वर को समानांतर कैसे करें?

Question

प्रोग्रामिंग अभ्यास के रूप में, मैंने बस एक सुडोकू सॉल्वर लिखना समाप्त कर दिया जो बैकट्रैकिंग एल्गोरिदम का उपयोग करता है (सी 0 में लिखे गए एक साधारण उदाहरण के लिए Wikipedia देखें)।

इसे एक कदम आगे बढ़ाने के लिए, मैं हिम तेंदुए के जीसीडी का उपयोग समानांतर करने के लिए करना चाहता हूं ताकि यह मेरे सभी मशीनों के कोर पर चलता है। क्या कोई मुझे पॉइंटर्स दे सकता है कि मुझे ऐसा करने के बारे में कैसे जाना चाहिए और मुझे कौन सा कोड बदलना चाहिए? धन्यवाद!

मैट

Answer 1

एक के लिए, बैक ट्रैकिंग के बाद से, गहराई-पहले खोज यह सीधे चलाने योग्य नहीं है। इसके बजाए, आपको समस्या को जल्दी से विभाजित करना होगा, यानी थ्रेड # 1 बैकट्रैकिंग ग्राफ़ में नोड के लिए पहले संयोजन के साथ शुरू होता है, और शेष सबग्राफ को खोजने के लिए आगे बढ़ता है। थ्रेड # 2 पहले और आगे के दूसरे संभावित संयोजन के साथ शुरू होता है। संक्षेप में, n धागे के लिए n खोज अंतरिक्ष के शीर्ष स्तर पर संभव संयोजनों को खोजने ("आगे ट्रैक" नहीं है), तो n धागे के लिए इन n शुरुआती बिंदु आवंटित।

हालांकि मुझे लगता है कि विचार मौलिक रूप से त्रुटिपूर्ण है: कई सुडोकू क्रमपरिवर्तनों को कुछ हज़ारों आगे + बैकट्रैकिंग चरणों के मामले में हल किया जाता है, और एकल धागे पर मिलीसेकंड के भीतर हल किया जाता है। यह वास्तव में इतना तेज़ है कि कुछ धागे के लिए भी छोटा समन्वय आवश्यक है (मान लें कि n धागे गणना समय को 1/एन मूल समय के लिए कम करते हैं) बहु-कोर/बहु-CPU पर नगण्य नहीं है कुल चलने का समय, इस प्रकार यह किसी भी मौके से अधिक कुशल समाधान नहीं है।

Answer 2

क्या आप वाकई ऐसा करना चाहते हैं? पसंद है, आप किस समस्या को हल करने की कोशिश कर रहे हैं? यदि आप सभी कोर का उपयोग करना चाहते हैं, तो थ्रेड का उपयोग करें। यदि आप एक तेज़ सुडोकू सॉल्वर चाहते हैं, तो मैं आपको एक लिख सकता हूं, नीचे आउटपुट देखें। यदि आप अपने लिए काम करना चाहते हैं, तो आगे बढ़ें और जीसीडी का उपयोग करें;)।

अद्यतन:

मुझे नहीं लगता कि GCD बुरा है, यह सिर्फ बहुत सुडोकू हल के लिए काम करने के लिए प्रासंगिक नहीं है। जीसीडी कोड करने के लिए जीयूआई घटनाओं को बांधने के लिए एक तकनीक है। अनिवार्य रूप से, जीसीडी दो समस्याओं को हल करता है, मैकोज़ एक्स कैसे विंडोज़ अपडेट करता है, और यह जीयूआई कार्यक्रमों में टाइपिंग कोड के एक बेहतर विधि (थ्रेड की तुलना में) प्रदान करता है।

यह इस समस्या पर लागू नहीं होता है क्योंकि सुडोकू को किसी व्यक्ति की सोच से काफी तेजी से हल किया जा सकता है (मेरी विनम्र राय में)। ऐसा कहा जा रहा है कि, यदि आपका लक्ष्य सुडोकू को तेज़ी से हल करना था, तो आप धागे का उपयोग करना चाहते हैं, क्योंकि आप सीधे एक से अधिक प्रोसेसर का उपयोग करना चाहते हैं।

[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

अगर आप इसका उपयोग कर रहे हैं तो कृपया मुझे बताएं। यह मिल एएनएसआई सी का रन है, इसलिए सबकुछ पर चलना चाहिए। उपयोग के लिए अन्य पोस्ट देखें। के बाद से किसी भी हाल में अभिकलन परिणाम नहीं किया जा इस्तेमाल किया सीधे एक और धागा द्वारा इस्तेमाल किया जा सकता

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