首页 > 代码库 > 回溯法求解数独算法（C语言）
回溯法求解数独算法（C语言）
没有对输入的待解数独进行一般性验证（同一行、一列以及同一个小九宫格都不能出现重复数字）
算法利用回溯的思想：
从第一个空白处开始，找到其候选解（排除同行、同列以及同一小九宫格的所有出现过的数字，剩下未出现的数字都是候选解）的第一个值填入数独。
对第二个空白执行第一步（前面所填入的数字对此空白处有影响）。
当出现某个空白的候选解个数为0时，就开始回溯，找到第一个候选解多于一个的，将其在使用的候选解设为不可取（本程序取值为-1），找到其下一个候选解，继续上面的步骤！
直到所有空白处填满，运算完成，输出结果！
#include <stdio.h>
#include <malloc.h>
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 <stdio.h>
#include <stdlib.h>
#define BOOL int
#define FALSE 1
#define TRUE 0
typedef 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");
}
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。