c语言 九宫格还原算法 经典回溯算法问题：九宫格

九宫格是在81个格子中，要满足以下条件：(1)每个横行和竖列中的9个格子都包含数字1至9，不重复；(2)每个黑色粗实线围住的9个格子都包含数字1至9，不重复。如下表所示：7 6 1 9 3 4 8 2 5

3 5 4 6 2 8 1 9 7

9 2 8 1 5 7 6 3 4

2 1 9 5 4 6 3 7 8

4 8 3 2 7 9 5 1 6

5 7 6 3 8 1 9 4 2

1 9 5 7 6 2 4 8 3

8 3 2 4 9 5 7 6 1

6 4 7 8 1 3 2 5 9

要求找出给定数字的九宫格。

【输入形式】

输入9行9列81个数字，其中0表示要填的数字。

【输出形式】

输出满足条件的九宫格。

【输入样例】0 6 1 0 3 0 0 2 0

0 5 0 0 0 8 1 0 7

0 0 0 0 0 7 0 3 4

0 0 9 0 0 6 0 7 8

0 0 3 2 0 9 5 0 0

5 7 0 3 0 0 9 0 0

1 9 0 7 0 0 0 0 0

8 0 2 4 0 0 0 6 0

0 4 0 0 1 0 2 5 0

【输出样例】7 6 1 9 3 4 8 2 5

3 5 4 6 2 8 1 9 7

9 2 8 1 5 7 6 3 4

2 1 9 5 4 6 3 7 8

4 8 3 2 7 9 5 1 6

5 7 6 3 8 1 9 4 2

1 9 5 7 6 2 4 8 3

8 3 2 4 9 5 7 6 1

6 4 7 8 1 3 2 5 9

代码及思路如下：#include

bool canFill(int a[9][9], int k, int n){

int i, j, row = k / 9, col = k % 9;

for(i = 0; i < 9; ++i){

if(a[i][col] == n){

return false;

}

}

for(j = 0; j < 9; ++j){

if(a[row][j] == n){

return false;

}

}

for(i = row - row % 3; i < row - row % 3 + 3; ++i){

for(j = col - col % 3; j < col - col % 3 + 3; ++j){

if(a[i][j] == n){

return false;

}

}

}

return true;

}

void fill(int a[9][9], int k = 0){

int i, j;

if(k == 81){

for(i = 0; i < 9; ++i){

for(j = 0; j < 9; ++j){

printf("%d ", a[i][j]);

}

printf("\n");

}

return;

}

int row = k / 9, col = k % 9;

if(a[row][col] == 0){

for(i = 1; i <= 9; ++i){

if(canFill(a, k, i)){

a[row][col] = i;

fill(a, k + 1);

a[row][col] = 0;

}

}

}else{

fill(a, k + 1);

}

}

int main(){

int i, j, a[9][9];

for(i = 0; i < 9; ++i){

for(j = 0; j < 9; ++j){

scanf("%d", &a[i][j]);

}

}

fill(a);

return 0;

}

5月4日3点温习重写代码如下：#include

int square[9][9];

int isEnabled(int k, int num){

int row = k / 9;

int col = k % 9;

for(int i = 0; i < 9; ++i){

if(square[row][i] == num || square[i][col] == num){

return false;

}

}

int m = row - row % 3;

int n = col - col % 3;

for(int i = m; i < m + 3; ++i){

for(int j = n; j < n + 3; ++j){

if(square[i][j] == num){

return false;

}

}

}

return true;

}

void fill(int k = 0){

int row = k / 9;

int col = k % 9;

if(k >= 81){

for(int i = 0; i < 9; ++i){

for(int j = 0; j < 9; ++j){

printf("%d ", square[i][j]);

}

printf("\n");

}

return;

}

if(square[row][col] > 0){

fill(k + 1);

return;

}

for(int i = 1; i <= 9; ++i){

if(isEnabled(k, i)){

square[row][col] = i;

fill(k + 1);

square[row][col] = 0;

}

}

}

int main(){

for(int i = 0; i < 9; ++i){

for(int j = 0; j < 9; ++j){

scanf("%d", &square[i][j]);

}

}

fill();

return 0;

}

如需转载请注明出处：蓝飞技术部落格