首页 > 代码库 > poj--2676--回溯
poj--2676--回溯
很久很久前 就做过数独了 当时一直没做出来了
这次 也磕磕绊绊 终于过了.... 数独题 真的很好 对于回溯的理解 很有帮助
一下子 觉得 全垒打的节奏...
touch me
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 15; 6 bool flag; 7 int sudu[size][size]; 8 bool rowHas[size][size]; 9 bool colHas[size][size]; 10 11 void dfs( int u ) 12 { 13 bool end = false; 14 int x = u/9; 15 int y = u%9; 16 if( u==81 ) 17 { 18 flag = true; 19 return; 20 } 21 if( sudu[x][y] ) 22 { 23 dfs( u+1 ); 24 } 25 else 26 { 27 for( int i = 1 ; i<=9 ; i++ ) 28 { 29 if( rowHas[x][i] ) 30 { 31 continue; 32 } 33 else if( colHas[y][i] ) 34 { 35 continue; 36 } 37 else 38 { 39 int xx = u/9/3*3; 40 int yy = u%9/3*3; 41 for( int j = xx ; j<xx+3 ; j++ ) 42 { 43 for( int k = yy ; k<yy+3 ; k++ ) 44 { 45 if( sudu[j][k] == i ) 46 { 47 end = true; 48 break; 49 } 50 } 51 if( end ) 52 break; 53 } 54 } 55 if( end ) 56 { 57 end = false; 58 continue; 59 } 60 sudu[x][y] = i; 61 rowHas[x][i] = true; 62 colHas[y][i] = true; 63 dfs( u+1 ); 64 if( flag ) 65 { 66 return; 67 } 68 rowHas[x][i] = false; 69 colHas[y][i] = false; 70 sudu[x][y] = 0; 71 } 72 } 73 } 74 75 int main() 76 { 77 int n; 78 char ch; 79 while( cin >> n ) 80 { 81 while(n--) 82 { 83 flag = false; 84 memset( rowHas , false , sizeof(rowHas) ); 85 memset( colHas , false , sizeof(colHas) ); 86 for( int i = 0 ; i<9 ; i++ ) 87 { 88 for( int j = 0 ; j<9 ; j++ ) 89 { 90 cin >> ch; 91 sudu[i][j] = ch-‘0‘; 92 if( sudu[i][j] ) 93 { 94 rowHas[i][ sudu[i][j] ] = true; 95 colHas[j][ sudu[i][j] ] = true; 96 } 97 } 98 } 99 dfs( 0 );100 for( int i = 0 ; i<9 ; i++ )101 {102 for( int j = 0 ; j<9 ; j++ )103 {104 cout << sudu[i][j];105 }106 cout << endl;107 }108 }109 } 110 return 0;111 }
today:
十年前 我要生如夏花
十年后 我要平凡一生
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。