经典回溯算法问题:九宫格
杰拉斯 | 时间:2012-12-18, Tue | 22,239 views编程算法
九宫格是在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<stdio.h> 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; }
2013年5月4日3点温习重写代码如下:
#include<stdio.h> 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; }