来自:http://my.oschina.net/lovewxm/blog/288043?p=1
#include <stdio.h>
#include <stdlib.h> #define BOOL int
#define FALSE 1
#define TRUE 0 typedef struct node
{
int col;
int row;
int value[];
} Node; int findvalue(int sudoku[][], Node * node);
BOOL general_inspection(int sudoku[][]);
int blank_num(int sudoku[][]);
Node * mem_alloc(int num_of_empty);
void trace(int sudoku[][], Node * node_stack, int num_of_empty);
void print_sudoku(int sudoku[][]); int main(void)
{
int sudoku[][] = {{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,}
}; int num_of_empty;
//为回溯栈分配空间
Node * node_stack; if(general_inspection(sudoku))
{
printf("此数独存在错误!请检查\n");
print_sudoku(sudoku);
return ;
}
num_of_empty = blank_num(sudoku);
node_stack = mem_alloc(num_of_empty);
trace(sudoku, node_stack, num_of_empty);
print_sudoku(sudoku); return ;
} BOOL general_inspection(int sudoku[][])
{
int temp[] = {, , , , , , , , , };
int i, j, m, n;
for(i=; i<; i++)
for(j=; j<; j++)
if(sudoku[i][j]!=)
{
//检查所在行
for(m=; m<; m++)
temp[m] = ;
for(m=; m<; m++)
if(sudoku[i][m]!=)
{
if(temp[sudoku[i][m]]==)
temp[sudoku[i][m]] = ;
else
return FALSE;
}
//检查所在列
for(m=; m<; m++)
temp[m] = ;
for(m=; m<; m++)
if(sudoku[m][j]!=)
{
if(temp[sudoku[m][j]]==)
temp[sudoku[m][j]] = ;
else
return FALSE;
}
//检查所在九宫格
for(m=; m<; m++)
temp[m] = ;
for(m=; m<; m++)
for(n=; n<; n++)
if(sudoku[i/*+m][j/*+n]!=)
{
if(temp[sudoku[i/*+m][j/*+n]]==)
temp[sudoku[i/*+m][j/*+n]] = ;
else
return FALSE;
}
}
return TRUE;
} int blank_num(int sudoku[][])
{
//计算所给数独中待填入的空白数
int i, j, num = ;
for(i=; i<; i++)
for(j=; j<; j++)
if(sudoku[i][j]==)
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();
}
return node_stack;
} void trace(int sudoku[][], Node * node_stack, int num_of_empty)
{
int i, j, index, k = ;
//回溯法求解数独
while(num_of_empty)
{
for(i=; i<; i++)
{
for(j=; j<; j++)
{
if(sudoku[i][j]==)
{
(node_stack + k)->col = i;
(node_stack + k)->row = j;
sudoku[i][j] = findvalue(sudoku, node_stack+k);
if(sudoku[i][j]==-)
{
sudoku[i][j] = ;
k--;
while((node_stack + k)->value[]==)
{
//当栈空,说明数独错误,无解
if(k==)
{
printf("此数独无解!\n");
//free(node_stack); //为啥这里一释放内存,就弹出debug assertion failed窗口啊!
exit();
}
sudoku[(node_stack + k)->col][(node_stack + k)->row] = ;
num_of_empty++;
k--;
}
for(index=; index<; index++)
if((node_stack + k)->value[index]==)
{
sudoku[(node_stack + k)->col][(node_stack + k)->row] = index;
(node_stack + k)->value[index] = ;
(node_stack + k)->value[]--;
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[][], Node * node)
{
int m, n, i = node->col, j = node->row;
//初始化栈中存储候选值的数组
for(m=; m<; m++)
node->value[m] = ;
for(m=; m<; m++)
{
node->value[sudoku[i][m-]] = ;
node->value[sudoku[m-][j]] = ;
}
for(m=; m<; m++)
for(n=; n<; n++)
node->value[sudoku[i/*+m][j/*+n]] = ; //node->value[0]记录候选值个数,前面的循环可能会修改掉它,需要重新赋0值
node->value[] = ;
for(m=; m<; m++)
if(node->value[m]==) node->value[]++;
for(m=; m<; m++)
if(node->value[m]==)
{
node->value[m] = ;
node->value[]--;
break;
} //返回候选值m,若无候选值可用,返回错误标记-1
if(m==)
return -;
else
return m;
} void print_sudoku(int sudoku[][])
{
//打印数独
int i, j;
for(i=; i<; i++)
{
for(j=; j<; j++)
printf("%2d ", sudoku[i][j]);
printf("\n");
}
}