数独算法研究

主要算法，首先找出没有数字的格子中可能性最小的，然后依次将可能的数字填入这个空格，最后进行迭代，直至得到最后的结果，完结。

#include #include #include #include #include typedef struct{int mux[9][9];} Sudoku;/*Sudoku sudoku =   {.mux = {        {8, 0, 0, 0, 0, 0, 0, 0, 0},        {0, 0, 3, 6, 0, 0, 0, 0, 0},        {0, 7, 0, 0, 9, 0, 2, 0, 0},        {0, 5, 0, 0, 0, 7, 0, 0, 0},        {0, 0, 0, 0, 4, 5, 7, 0, 0},        {0, 0, 0, 1, 0, 0, 0, 3, 0},        {0, 0, 1, 0, 0, 0, 0, 6, 8},        {0, 0, 8, 5, 0, 0, 0, 1, 0},        {0, 9, 0, 0, 0, 0, 4, 0, 0}}};*/Sudoku sudoku ={.mux = {{0, 0, 5, 3, 0, 0, 0, 0, 0},{8, 0, 0, 0, 0, 0, 0, 2, 0},{0, 7, 0, 0, 1, 0, 5, 0, 0},{4, 0, 0, 0, 0, 5, 3, 0, 0},{0, 1, 0, 0, 7, 0, 0, 0, 6},{0, 0, 3, 2, 0, 0, 0, 8, 0},{0, 6, 0, 5, 0, 0, 0, 0, 9},{0, 0, 4, 0, 0, 0, 0, 3, 0},{0, 0, 0, 0, 0, 9, 7, 0, 0}}};int number_thread = 0;int number_count = 0;void *thread1(void *arg){pthread_t thread;Sudoku number, number_temp = {.mux = {0}};int in1, in2, in3, temp = 0, temp_in1, temp_in2, temp_temp_1, temp_temp_2, temp_temp_3, temp_temp_4;int position[2] = {-1, -1};int last_number[9]; // numbers which exists here;int last_number_1[9];int number_not_zero = 0;memcpy(number.mux, arg, sizeof(Sudoku));for (in1 = 0; in1 < 9; in1++){for (in2 = 0; in2 < 9; in2++){printf('%d,', number.mux[in1][in2]);}printf('\n');}printf('\n');temp = 0;for (in1 = 0; in1 < 9; in1++){for (in2 = 0; in2 < 9; in2++){if (number.mux[in1][in2] != 0){printf('0,');number_not_zero++;continue;}memset(last_number, 0, sizeof(last_number));for (in3 = 0; in3 < 9; in3++){if (in1 == 0 && in2 == 8)printf('\n%d, %d\n', number.mux[in1][in3], number.mux[in3][in2]);if (number.mux[in1][in3] != 0){last_number[number.mux[in1][in3] - 1] = 1;}if (number.mux[in3][in2] != 0){last_number[number.mux[in3][in2] - 1] = 1;}}temp_temp_1 = (in1 % 3);temp_temp_2 = (in1 / 3);temp_temp_3 = (in2 % 3);temp_temp_4 = (in2 / 3);//printf('\nstart sub \n');for (temp_in1 = temp_temp_1; temp_in1 < (temp_temp_1 + 3); temp_in1++){// printf('%d----', temp_temp_2 * 3 + (temp_in1 % 3));for (temp_in2 = temp_temp_3; temp_in2 < (temp_temp_3 + 3); temp_in2++){last_number[number.mux[temp_temp_2 * 3 + (temp_in1 % 3)][temp_temp_4 * 3 + (temp_in2 % 3)] - 1] = 1;//printf('%d', temp_temp_4 * 3 + (temp_in2 % 3));}//printf('\n');}//printf('end sub \n');for (in3 = 0; in3 < 9; in3++){if (last_number[in3] != 0){number_temp.mux[in1][in2]++;}}if (number_temp.mux[in1][in2] > temp && number_temp.mux[in1][in2] < 9){temp = number_temp.mux[in1][in2];position[0] = in1;position[1] = in2;memcpy(last_number_1, last_number, sizeof(last_number));}printf('%d,', number_temp.mux[in1][in2]);}printf('\n');}for (in3 = 0; in3 < 9; in3++){printf('%d,', last_number_1[in3]);}printf('position%d, %d, %d\n', position[0], position[1], temp);if (position[0] == -1 || position[1] == -1)return 0;//check the resultfor (in3 = 0; in3 < 9; in3++){if (last_number_1[in3] == 0){number.mux[(position[0])][(position[1])] = in3 + 1;for (in1 = 0; in1 < 9; in1++){for (in2 = 0; in2 < 9; in2++){printf('%d,', number.mux[in1][in2]);}printf('\n');}printf('----------------------\n');if (number_not_zero == 80){printf('++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n');printf('\nCongratulation!!!\n\nThe result is:\n');for (in1 = 0; in1 < 9; in1++){for (in2 = 0; in2 < 9; in2++){printf('%d,', number.mux[in1][in2]);}printf('\n');}printf('++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n');exit(1);}thread1((void *)&number);}}return 0;}int main(){thread1((void *)&sudoku);getchar();return 0;}