解数独算法,用C语言递归实现

前几天在看离散数学及其应用第七版的时候,看到了数独的相关章节,就自己写了一个数独的解法,先记下来。生成数独的方法以后再写



#include

// 寻找下一个未填充的单元
int find_next_empty(int arr[9][9], int startrow, int *row, int *col)
{
int i, j;

for (i = startrow; i < 9; i++)
for (j = 0; j < 9; j++)
if (arr[i][j] == 0) {
*row = i;
*col = j;
return 1;
}

return 0;
}

void print(int a[9][9])
{
int i, j;

for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
printf("%2d", a[i][j]);
if (j == 8) printf("
");
}
}
}

int do_resolve(int arr[9][9], int row, int col)
{
int i, j, n;

int next_row, next_col;

n = 0;
while(1) {
next_num:
++n;
if (n >= 10) break;

// 判断行重复
for (j = 0; j < 9; j++) {
if (arr[row][j] == n) {
goto next_num;
}
}

// 判断列重复
for (i = 0; i < 9; i++) {
if (arr[i][col] == n) {
goto next_num;
}
}

/* 判断所在小九宫格重复*/
int x = (row / 3) * 3;
int y = (col / 3) * 3;
for (i = x; i < x + 3; i++) {
for (j = y; j < y + 3; j++) {
if (arr[i][j] == n) {
goto next_num;
}
}
}

//该单元可以填充
arr[row][col] = n;
//如果9宫格已填满,完成,这里不考虑有多解的情况
if (!find_next_empty(arr, row, &next_row, &next_col)) {
return 1;
}
//否则继续填下一个未填充的格子
if (!do_resolve(arr, next_row, next_col)) {
arr[row][col] = 0;
continue;
} else {
return 1;
}
}

return 0;
}

void resolve_sudoku(int a[9][9])
{
int row, col;

find_next_empty(a, 0, &row, &col);
do_resolve(a, row, col);
}

int main(void)
{
int a[9][9] = {
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
};
resolve_sudoku(a);
print(a);

return 0;
}




相关文档

  • 高一语文课文《致橡树》赏析2篇|致橡树是几年级的课文
  • 快速搭建一套免费云上MongoDB集群
  • Java实现自定义工作流
  • 中学教务处主任竞聘演讲稿范文
  • 大寒代表什么意思
  • 【opencv学习】使用opencv与两个摄像头实现双目标定与测距
  • 操作系统实验报告??磁盘调度算法
  • 高二历史复习方法:三种高效学习的方法
  • 家长给高一学生一封信作文范文
  • 商业艺术摄影作品赏析
  • 班级趣事多
  • 我有一个武侠梦生活随笔
  • 个人承诺书样本最新5篇
  • 三星s8韩版刷国行缺陷
  • python response.text和response.content的区别
  • 校园健身操比赛主持词
  • 世界线收束是什么梗什么意思世界线收束的梗是怎么来的
  • 邮件命名是指主题吗
  • 明星权志龙桌面壁纸图片
  • 合理用药的宣传语
  • 淡淡的日子也飘香作文
  • 台湾为何不接受来自大陆的援助
  • 2021年腊八节是几月几号为什么说过了腊八就是年
  • Golang系列(七)之常用包
  • 怎样在运行里打开我的电脑
  • 写了一个chrome插件:拦截ajax请求并修改返回结果
  • 小学三年级作文范文及评语
  • oracle数据库null和空字符串区别,null和空字符串('')的区别
  • 常用的人脸识别库及下载地址
  • 怎样快捷减肥有效的方法有哪些
  • 电脑版