C语言数独计算

桃扇骨 2022-06-01 05:53 139阅读 0赞

蒜头君今天突然开始还念童年了，想回忆回忆童年。他记得自己小时候，有一个很火的游戏叫做数独。便开始来了一局紧张而又刺激的高阶数独。蒜头君做完发现没有正解，不知道对不对？ 不知道聪明的你能否给出一个标准答案？

标准数独是由一个给与了提示数字的 9 \\times 99×9 网格组成，我们只需将其空格填上数字，使得每一行，每一列以及每一个 3 \\times 33×3 宫都没有重复的数字出现。

#include <stdio.h> // 寻找下一个未填充的单元 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("\n"); } } } 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] = { 0,2,6,0,0,0,0,0,0, 0,0,0,5,0,2,0,0,4, 0,0,0,1,0,0,0,0,7, 0,3,0,0,2,0,1,8,0, 0,0,0,3,0,9,0,0,0, 0,5,4,0,1,0,0,7,0, 5,0,0,0,0,1,0,0,0, 6,0,0,9,0,7,0,0,0, 0,0,0,0,0,0,7,5,0 }; resolve_sudoku(a); print(a); return 0; } // 1 2 6 7 3 4 5 9 8 // 3 7 8 5 9 2 6 1 4 // 4 9 5 1 6 8 2 3 7 // 7 3 9 4 2 5 1 8 6 // 8 6 1 3 7 9 4 2 5 // 2 5 4 8 1 6 3 7 9 // 5 4 7 2 8 1 9 6 3 // 6 1 3 9 5 7 8 4 2 // 9 8 2 6 4 3 7 5 1