没有对输入的待解数独进行一般性验证（同一行、一列以及同一个小九宫格都不能出现重复数字）
算法利用回溯的思想：
从第一个空白处开始，找到其候选解（排除同行、同列以及同一小九宫格的所有出现过的数字，剩下未出现的数字都是候选解）的第一个值填入数独。
对第二个空白执行第一步（前面所填入的数字对此空白处有影响）。
当出现某个空白的候选解个数为0时，就开始回溯，找到第一个候选解多于一个的，将其在使用的候选解设为不可取（本程序取值为-1），找到其下一个候选解，继续上面的步骤！
直到所有空白处填满，运算完成，输出结果！
#include#include typedef struct node{ int col; int row; int value[10];}Node;int findvalue(int sudoku[9][9], Node * node);int main(void){ int sudoku[9][9] = { {3, 4, 0, 0, 0, 2, 0, 7, 5}, {0, 5, 0, 0, 0, 0, 0, 4, 0}, {0, 0, 0, 8, 0, 0, 2, 0, 0}, {0, 0, 0, 6, 0, 0, 0, 9, 4}, {0, 0, 0, 2, 0, 9, 0, 0, 0}, {4, 9, 0, 0, 0, 8, 0, 0, 0}, {0, 0, 9, 0, 0, 7, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 0, 5, 0}, {2, 7, 0, 9, 0, 0, 0, 1, 3}}; int i, j, k = 0, num_of_empty = 0; int index, temp = 0; //计算所给数独中待填入的空白数 for(i=0; i<9; i++) for(j=0; j<9; j++) if(sudoku[i][j]==0) num_of_empty++; //为回溯栈分配空间 Node * node_stack = (Node *)malloc(sizeof(struct node) * num_of_empty); //回溯法求解数独 while(num_of_empty) { for(i=0; i<9; i++) for(j=0; j<9; j++) if(sudoku[i][j]==0) { //初始化栈中存储候选值的数组 for(index=0; index<10; index++) (node_stack + k)->value[index] = 0; (node_stack + k)->col = i; (node_stack + k)->row = j; sudoku[i][j] = findvalue(sudoku, node_stack + k); if(sudoku[i][j]==-1) { sudoku[i][j] = 0; k--; while((node_stack + k)->value[0]==1) { sudoku[(node_stack + k)->col][(node_stack + k)->row] = 0; num_of_empty++; k--; } (node_stack + k)->value[0]--; i = (node_stack + k)->col; j = (node_stack + k)->row; for(index=1; index<10; index++) if((node_stack + k)->value[index]==0) { (node_stack + k)->value[index] = -1; break; } for(index=1; index<10; index++) if((node_stack + k)->value[index]==0) { sudoku[i][j] = index; break; } } k++; } //当栈空，说明数独错误，无解 if(k==0) { printf("此数独无解！\n"); free(node_stack); return 0; } num_of_empty--; } free(node_stack); //打印数独 for(i=0; i<9; i++) { for(j=0; j<9; j++) printf("%2d ", sudoku[i][j]); printf("\n"); } return 0;}int findvalue(int sudoku[9][9], Node * node){ int m, n, i = node->col, j = node->row; for(m=1; m<10; m++) { if(node->value[sudoku[i][m-1]]==0) node->value[sudoku[i][m-1]] = sudoku[i][m-1]; if(node->value[sudoku[m-1][j]]==0) node->value[sudoku[m-1][j]] = sudoku[m-1][j]; } for(m=0; m<3; m++) for(n=0; n<3; n++) if(node->value[sudoku[i/3*3+m][j/3*3+n]]==0) node->value[sudoku[i/3*3+m][j/3*3+n]] = sudoku[i/3*3+m][j/3*3+n]; for(m=1; m<10; m++) if(node->value[m]==0) node->value[0]++; for(m=1; m<10; m++) if(node->value[m]==0) break; if(node->value[0]==0) return -1; else return m; }
做了下改进：将各个步骤独立成函数，加入了待解数独的前期一般性检查，还有部分代码优化
#include#include #define BOOL int#define FALSE 1#define TRUE 0typedef struct node{ int col; int row; int value[10];} Node;int findvalue(int sudoku[9][9], Node * node);BOOL general_inspection(int sudoku[9][9]);int blank_num(int sudoku[9][9]);Node * mem_alloc(int num_of_empty);void trace(int sudoku[9][9], Node * node_stack, int num_of_empty);void print_sudoku(int sudoku[9][9]);int main(void){ int sudoku[9][9] = { {3, 4, 1, 0, 0, 2, 0, 7, 5}, {0, 5, 0, 0, 0, 0, 0, 4, 0}, {0, 0, 0, 8, 0, 0, 2, 0, 0}, {0, 0, 0, 6, 0, 0, 0, 9, 4}, {0, 0, 0, 2, 0, 9, 0, 0, 0}, {4, 9, 0, 0, 0, 8, 0, 0, 0}, {0, 0, 9, 0, 0, 7, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 0, 5, 0}, {2, 7, 0, 9, 0, 0, 0, 1, 3}}; int num_of_empty; //为回溯栈分配空间 Node * node_stack; if(general_inspection(sudoku)) { printf("此数独存在错误！请检查\n"); print_sudoku(sudoku); return 0; } num_of_empty = blank_num(sudoku); node_stack = mem_alloc(num_of_empty); trace(sudoku, node_stack, num_of_empty); print_sudoku(sudoku); return 0;}BOOL general_inspection(int sudoku[9][9]){ int temp[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int i, j, m, n; for(i=0; i<9; i++) for(j=0; j<9; j++) if(sudoku[i][j]!=0) { //检查所在行 for(m=0; m<10; m++) temp[m] = 0; for(m=0; m<9; m++) if(sudoku[i][m]!=0) { if(temp[sudoku[i][m]]==0) temp[sudoku[i][m]] = 1; else return FALSE; } //检查所在列 for(m=0; m<10; m++) temp[m] = 0; for(m=0; m<9; m++) if(sudoku[m][j]!=0) { if(temp[sudoku[m][j]]==0) temp[sudoku[m][j]] = 1; else return FALSE; } //检查所在九宫格 for(m=0; m<10; m++) temp[m] = 0; for(m=0; m<3; m++) for(n=0; n<3; n++) if(sudoku[i/3*3+m][j/3*3+n]!=0) { if(temp[sudoku[i/3*3+m][j/3*3+n]]==0) temp[sudoku[i/3*3+m][j/3*3+n]] = 1; else return FALSE; } } return TRUE;}int blank_num(int sudoku[9][9]){ //计算所给数独中待填入的空白数 int i, j, num = 0; for(i=0; i<9; i++) for(j=0; j<9; j++) if(sudoku[i][j]==0) num++; return num;}Node * mem_alloc(int num_of_empty){ Node * node_stack = (Node *)malloc(sizeof(struct node) * num_of_empty); if(node_stack==NULL) { printf("内存分配失败！\n"); exit(1); } return node_stack;}void trace(int sudoku[9][9], Node * node_stack, int num_of_empty){ int i, j, index, k = 0; //回溯法求解数独 while(num_of_empty) { for(i=0; i<9; i++) { for(j=0; j<9; j++) { if(sudoku[i][j]==0) { (node_stack + k)->col = i; (node_stack + k)->row = j; sudoku[i][j] = findvalue(sudoku, node_stack+k); if(sudoku[i][j]==-1) { sudoku[i][j] = 0; k--; while((node_stack + k)->value[0]==0) { //当栈空，说明数独错误，无解 if(k==0) { printf("此数独无解！\n"); //free(node_stack); //为啥这里一释放内存，就弹出debug assertion failed窗口啊！ exit(1); } sudoku[(node_stack + k)->col][(node_stack + k)->row] = 0; num_of_empty++; k--; } for(index=1; index<10; index++) if((node_stack + k)->value[index]==0) { sudoku[(node_stack + k)->col][(node_stack + k)->row] = index; (node_stack + k)->value[index] = 1; (node_stack + k)->value[0]--; break; } num_of_empty++; i = (node_stack + k)->col; j = (node_stack + k)->row; } k++; num_of_empty--; } } } } //栈空间使用结束，释放 free(node_stack); node_stack=NULL;}int findvalue(int sudoku[9][9], Node * node){ int m, n, i = node->col, j = node->row; //初始化栈中存储候选值的数组 for(m=0; m<10; m++) node->value[m] = 0; for(m=1; m<10; m++) { node->value[sudoku[i][m-1]] = 1; node->value[sudoku[m-1][j]] = 1; } for(m=0; m<3; m++) for(n=0; n<3; n++) node->value[sudoku[i/3*3+m][j/3*3+n]] = 1; //node->value[0]记录候选值个数，前面的循环可能会修改掉它，需要重新赋0值 node->value[0] = 0; for(m=1; m<10; m++) if(node->value[m]==0) node->value[0]++; for(m=1; m<10; m++) if(node->value[m]==0) { node->value[m] = 1; node->value[0]--; break; } //返回候选值m，若无候选值可用，返回错误标记-1 if(m==10) return -1; else return m;}void print_sudoku(int sudoku[9][9]){ //打印数独 int i, j; for(i=0; i<9; i++) { for(j=0; j<9; j++) printf("%2d ", sudoku[i][j]); printf("\n"); }}