Как параллелизировать решатель Судоку с помощью Центральной Отправки?
Абсолютно определите столбцы, которые Вы хотите ВЫБРАТЬ каждый раз. Нет никакой причины не к, и повышение производительности определенно стоит того.
Они никогда не должны были давать опцию "ВЫБРАТЬ *"
3 ответа
Во-первых, поскольку поиск с возвратом является поиском в глубину, его нельзя напрямую распараллелить, так как любой вновь вычисленный результат не может использоваться напрямую другим потоком. Вместо этого вы должны разделить проблему на раннем этапе, т. Е. Поток №1 начинается с первой комбинации для узла в графе с возвратом и переходит к поиску остальной части этого подграфа. Поток №2 начинается со второй возможной комбинации с первой и так далее. Коротко, для n потоков найдите n возможных комбинаций на верхнем уровне области поиска (не «вперед-трек»), затем назначьте эти n начальные точки в n потоков.
Однако я думаю, что эта идея в корне ошибочна: многие перестановки судоку решаются за пару тысяч шагов вперед и назад и решаются за миллисекунды в одном потоке. На самом деле это настолько быстро, что даже небольшая координация, необходимая для нескольких потоков (предположим, что n потоков сокращают время вычислений до 1 / n исходного времени) на многоядерном / многопроцессорность не является незначительной по сравнению с общим временем работы, поэтому это никоим образом не является более эффективным решением.
затем назначьте эти n начальных точек потокам n .Однако я думаю, что идея в корне ошибочна: многие перестановки судоку решаются за пару тысяч перестановок вперед + назад шаги и решаются за миллисекунды в одном потоке. На самом деле это настолько быстро, что даже небольшая координация, необходимая для нескольких потоков (предположим, что n потоков сокращают время вычислений до 1 / n исходного времени) на многоядерном / многопроцессорность не является незначительной по сравнению с общим временем работы, поэтому это никоим образом не является более эффективным решением.
затем присвойте эти n начальные точки потокам n .Однако я думаю, что идея в корне ошибочна: многие перестановки судоку решаются за пару тысяч перестановок вперед + назад шаги и решаются за миллисекунды в одном потоке. На самом деле это настолько быстро, что даже небольшая координация, необходимая для нескольких потоков (предположим, что n потоков сокращают время вычислений до 1 / n исходного времени) на многоядерном / многопроцессорность не является незначительной по сравнению с общим временем работы, поэтому это никоим образом не является более эффективным решением.
и решаются за миллисекунды в одном потоке. На самом деле это настолько быстро, что даже небольшая координация, необходимая для нескольких потоков (предположим, что n потоков сокращают время вычислений до 1 / n исходного времени) на многоядерном / многопроцессорность не является незначительной по сравнению с общим временем работы, поэтому это никоим образом не является более эффективным решением. и решаются за миллисекунды в одном потоке. На самом деле это настолько быстро, что даже небольшая координация, необходимая для нескольких потоков (предположим, что n потоков сокращают время вычислений до 1 / n исходного времени) на многоядерном / многопроцессорность не является незначительной по сравнению с общим временем работы, поэтому это никоим образом не является более эффективным решением.Пожалуйста, дайте мне знать, если вы в конечном итоге воспользуетесь им. Он работает по стандарту 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;
}
Вы уверены, что хотите это сделать? Мол, какую проблему вы пытаетесь решить? Если вы хотите использовать все ядра, используйте потоки. Если вам нужен быстрый решатель судоку, я могу дать вам тот, который написал я, см. Результат ниже. Если вы хотите работать на себя, используйте GCD;).
Обновление :
Я не думаю, что GCD плохой, просто он не очень важен для решения судоку . GCD - это технология привязки событий графического интерфейса к коду. По сути, GCD решает две проблемы: причуду в том, как MacOS X обновляет окна, и предоставляет улучшенный метод (по сравнению с потоками) привязки кода к событиям графического интерфейса.
Это не относится к этой задаче, потому что судоку можно решить значительно быстрее, чем человек может подумать (по моему скромному мнению). При этом, если вашей целью было быстрее решать судоку, вы захотите использовать потоки, потому что вам нужно напрямую использовать более одного процессора.
[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