5
作爲一個編程練習，我剛剛完成了一個使用回溯算法的Sudoku求解器的完成（參見Wikipedia爲一個用C語言編寫的簡單示例）。如何使用Grand Central Dispatch並行化Sudoku解算器？
爲了更進一步，我想使用Snow Leopard的GCD並行化它，以便它可以在我所有機器的內核上運行。有人能給我指示我應該如何去做這件事以及我應該做什麼代碼更改？謝謝！
馬特
A
回答
3
其一，由於回溯是一個深度優先搜索它不是直接可並行化的，因爲任何新計算的結果不能用來直接使用由另一個線程。相反，您必須儘早分解問題，即線程＃1以回溯圖中節點的第一個組合開始，然後繼續搜索該子圖的其餘部分。線程＃2從第一個等第二個可能的組合開始。總之，對於ñ線程找到搜索空間的頂層ñ可能的組合（沒有「前軌」），然後將這些ň出發點ñ線程。
但是我認爲這個想法存在根本上的缺陷：許多數獨排列都是在幾千次前進+回溯步驟中解決的，並且在單個線程中以毫秒爲單位解決。這實際上是如此之快以致於在多核/多CPU上，即使幾個線程所需的小協調（假設線程將計算時間減少到原始時間的1/n）也不可忽略，與總運行時間，因此它不是一個更有效的解決方案。
2
您確定要這樣嗎？就像，你想要解決什麼問題？如果你想使用所有的核心，使用線程。如果你想要一個快速的數獨求解器，我可以給你一個我寫的，見下面的輸出。如果你想爲自己工作，繼續使用GCD;）。
更新：
我不認爲GCD是壞，它只是不解決數獨的任務非常重要。 GCD是一種將GUI事件與代碼綁定的技術。從本質上講，GCD解決了兩個問題，一個是MacOS X如何更新窗口的Quirk，另一個是將代碼綁定到GUI事件的改進方法（與線程相比）。
它不適用於這個問題，因爲數獨可以比人們想象的更快地得到解決（以我的愚見）。話雖如此，如果你的目標是更快地解決Sudoku，你會想要使用線程，因爲你想直接使用多個處理器。
[[email protected] 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
+0
我很想看你的代碼。 – 2009-12-05 23:10:36
+0
足夠給我一個負面評價？ – Bear 2009-12-05 23:20:42
+2
那不是我。我需要至少100個聲望點才能給出負面評價...... – 2009-12-05 23:22:09
5
請讓我知道，如果你最終使用它。它是軋機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;
}
+1
對於很多非常酷的代碼+1。 – 2009-12-05 23:36:44
+1
+1，但你應該編輯你的帖子 – 2009-12-05 23:42:11
相關問題
- 1. Grand Central Dispatch與Cilk ++
- 2. Swift - Grand Central Dispatch Class
- 3. Swift - Grand Central Dispatch vs Blocks/Closures
- 4. Grand Central Dispatch等效於omp_get_thread_num
- 5. 雙核iPad（A5）= Grand Central Dispatch？
- 6. Grand Central Dispatch（GCD）和CoreData
- 7. 使用Grand Central Dispatch（GCD）時獲取OSSpinLockLock
- 8. 在Swift中使用Grand Central Dispatch來並行化並加速「for」循環？
- 9. 用於Visual Basic的Grand Central Dispatch？
- 10. 在connectionDidFinishLoading中使用Grand Central Dispatch解析JSON：？
- 11. iOS：如何在使用Grand Central Dispatch（GCD）時同步我的managedObjectContext？
- 12. Grand Central Dispatch如何真正使用操作系統？
- 13. 如何在使用Grand Central Dispatch時發佈NSNotification？
- 14. Qt中有什麼類似Grand Central Dispatch？
- 15. Grand Central Dispatch（GCD）調度源標記
- 16. 基於Grand Central Dispatch（GCD）的Web框架？
- 17. Grand Central Dispatch尋找不同的方法
- 18. 使用Grand Central Dispatch和UINavigationController的用戶界面問題
- 19. 是否可以在Windows上使用Grand Central Dispatch（`libdispatch`）？
- 20. 爲什麼要使用OpenMP上的Grand Central Dispatch？
- 21. 正確使用具有多個UIActivityIndicatorViews的Grand Central Dispatch
- 22. 如何在iPhone上檢測Grand Central Dispatch功能支持？
- 23. Grand Central Dispatch：如何等待塊的隊列完成？
- 24. 如何在Grand Central Dispatch中創建死鎖？
- 25. Grand Central vs Parallel Extensions
- 26. 如何用Quartz 2D和Grand CEntral Dispatch以編程方式生成UIImage
- 27. Objective-C - 剖析泄漏顯示Grand Central Dispatch正在泄漏
- 28. Grand Central Dispatch中的線程數和線程數
- 29. Grand Central Dispatch應該創建多少個線程？
- 30. 程序進入掛起模式時的Grand Central Dispatch
謝謝！我想我會堅持我目前的做法！ – 2009-12-06 00:07:22