数独问题就是给定一个9*9的矩阵，可能缺项，要求填入空缺的项并且满足下面三个条件：
1.每一行只能有1~9这9个数字全体各一次
2.每一列只能有1~9这9个数字全体各一次
3.把整个矩阵分成9个3*3的矩阵，这些小的矩阵中只能有1~9这9个数字全体各一次
最直观也是最简单的算法是回溯，下面是回溯的版本：
#include <iostream>
using namespace std;
int grid[9][9]= {0,0,8,0,0,6,5,0,0,
3,0,4,0,0,0,0,6,0,
6,0,0,0,1,0,0,0,7,
0,4,0,0,7,5,0,0,3,
0,2,0,0,0,3,0,0,4,
0,0,9,0,0,0,2,0,0,
0,6,0,5,0,0,0,2,0,
9,0,0,0,0,0,1,5,0,
0,0,2,0,0,8,4,0,0};
int nsol= 0;
void print_solution(){
int r, c;
printf("--- solution %d ---\n", ++nsol);
for( r= 0; r< 9; r++ ){
for( c= 0; c< 9; c++ )
printf("%d ",grid[r][c]);
putchar('\n');
}
}
int safe( int row, int col, int n ){
int r, c, br, bc;
if( grid[row][col]== n )
return 1;
if( grid[row][col]!= 0 )
return 0;
for( c= 0; c< 9; c++ )
if( grid[row][c]== n )
return 0;
for( r= 0; r< 9; r++ )
if( grid[r][col]== n )
return 0;
br= row/ 3, bc= col/ 3;
for( r= br* 3; r< (br+1)* 3; r++ )
for( c= bc* 3; c< (bc+1)* 3; c++ )
if( grid[r][c]== n )
return 0;
return 1;
}
void solve( int row, int col ){
int n, t;
if( row== 9 )
print_solution();
else
for( n= 1; n<= 9; n++ )
if( safe(row, col, n) ) {
t= grid[row][col];
grid[row][col] = n;
if( col== 8 )
solve(row+1,0);
else
solve(row,col+1);
grid[row][col] = t;
}
}
int main(){
solve(0,0);
return 0;
}
这是电脑的做法，可是我们自已在笔算的时候可做不到这一点，下面讨论更加贴近人的想法的算法，首先我们知道，每个格子有9种可能，我们可以通过排除的思想，有5步：
1.搜索只有一种可能的格子
2.搜索由于一行中所有其它格可能为某数的情况被排除的而得到此格值唯一的情况
3.搜索由于一列中所有其它格可能为某数的情况被排除的而得到此格值唯一的情况
4.搜索由于一小矩阵中所有其它格可能为某数的情况被排除的而得到此格值唯一的情况
5.若仍有不能确定的格子，任取一种可能的情况，再进行搜索
posted on 2009-07-07 19:08
古月残辉 阅读(323)
评论(0) 编辑 收藏 引用 所属分类:
Application