كيفية توازي Sudoku Solver باستخدام إيفاد Grand Central Respatch؟
https://stackoverflow.com/questions/1853755
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
كممارسة برمجة، انتهيت للتو من كتابة Sudoku Solver يستخدم خوارزمية التراجع (انظر ويكيبيديا مثال بسيط مكتوب في ج).
لاتخاذ هذه الخطوة أبعد من ذلك، أود استخدام GCD ل Snow Leopard's GCD لتعزيز هذا بحيث يعمل على جميع نوى الجهاز الخاصة بي. هل يمكن لشخص ما أن يعطيني مؤشرات حول كيفية القيام بذلك، وما هي التغييرات التي يجب أن تصنعها؟ شكرًا!
غير لامع
المحلول
بالنسبة إلى واحد، نظرا لأن التراجع هو البحث الأول - أولا، فلا يمكن التوازي مباشرة، نظرا لأن أي نتيجة محسوبة حديثا لا يمكن استخدامها مباشرة من قبل مؤشر ترابط آخر. بدلا من ذلك، يجب عليك تقسيم المشكلة في وقت مبكر، أي الخيط رقم 1 يبدأ مع التركيبة الأولى لعقدة في الرسم البياني الخلفي، وعائدات البحث في البحث عن بقية هذا المجموع الفصري. يبدأ الموضوع رقم 2 مع التركيبة الثانية الممكنة في الأول وما إلى ذلك. باختصار، ل ن الخيوط تجد ن مجموعات محتملة على المستوى العلوي من مساحة البحث (لا "المسار إلى الأمام")، ثم تعيين هذه ن نقاط البداية إلى ن الخيوط.
ومع ذلك، أعتقد أن الفكرة معيبة بشكل أساسي: تم حل العديد من عمليات تصارات سودوكو في مسألة بضعة آلاف من خطوات إعادة توجيه + تراجع، ويتم حلها داخل مللي ثانية على موضوع واحد. هذا في الواقع سريع جدا حتى التنسيق الصغير المطلوب لبضع خيوط (افترض ذلك ن خيوط تقليل وقت الحساب إلى 1 /ن من الوقت الأصلي) على وحدة المعالجة المركزية متعددة النواة / متعددة ليست ضئيلة مقارنة بموعد التشغيل الإجمالي، وبالتالي فهي ليست عن طريق أي فرصة أكثر كفاءة.
نصائح أخرى
واسمحوا لي أن أعرف إذا انتهى بك الأمر باستخدامه. يتم تشغيل مطحنة 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;
}
هل أنت متأكد أنك تريد أن تفعل ذلك؟ مثل، ما المشكلة التي تحاول حلها؟ إذا كنت ترغب في استخدام جميع النوى، استخدم مؤشرات الترابط. إذا كنت تريد حلال Sudoku سريع، يمكنني أن أعطيك أحد كتبته، راجع الإخراج أدناه. إذا كنت ترغب في عمل عمل لنفسك، فأنت في المستقبل واستخدم GCD؛).
تحديث:
لا أعتقد أن GCD سيء، فهو لا يتعلق الأمر بمهمة حل سودوكو. GCD هي التكنولوجيا لربط الأحداث واجهة المستخدم الرسومية لرمز. في الأساس، يحل GCD مشكلتين، Quirk في كيفية تحديث نظام التشغيل Macos X Windows، ويوفر طريقة محسنة (مقارنة بالتخواسيس) من رمز ربط الأحداث واجهة المستخدم الرسومية.
لا ينطبق على هذه المشكلة لأن سودوكو يمكن حل أسرع بكثير من الشخص الذي يمكن أن يفكر فيه الشخص (في رأيي المتواضع). ومع ذلك، إذا كان هدفك هو حل سودوكو بشكل أسرع، فأنت ترغب في استخدام الخيوط، لأنك تريد استخدام أكثر مباشرة أكثر من معالج واحد.
[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
