利用 Dancing Link 来解数独
详细的能够看 lrj 的训练指南 和 《 Dancing Links 在搜索中的应用 》这篇论文
Dancing Link 来求解数独 ， 是通过求解精确覆盖
精确覆盖就是给出一个 01 矩阵 ， 要求我们选择一些行 ， 使得每一列有且仅有一个 1
对于数独问题 ， 行就是我们的选择 ， 即在第 i 行 第 j 列 放上 数字 k ， 所以我们最多有 i * j * k 中选择
假设某些位置( x , y )已经放了数字 a ， 那么我们的选择仅仅能是 ( x , y , a ) , 否则的话， 我们能够选择 ( x , y , 1 ~ 9 )
对于列 ， 也就是我们须要满足的条件 ， 这里有 4 大类条件:
1. 第 x 行 第 y 列要有 数字
2. 第 x 行 要有 数字 y
3. 第 x 列 要有 数字 y
4. 第 x 个宫要有数字 y
所以总共同拥有 9*9*4 列 ( 如果 9*9*4 的数独的话 )
然后我们仅仅要进行DLX即可了
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std; const int maxn = 9 * 9 * 4 + 10 ;
const int maxr = 9 * 9 * 9 + 10 ;
const int maxnode = maxr * 4 + maxr + 10 ; #define FOR( i , A , s ) for( int i = A[s] ; i != s ; i = A[i] ) struct DLX{
// maxn 列数 , maxnode 总节点数 , maxr 行数
int n , sz ;
int S[maxn] ; int row[maxnode] , col[maxnode] ;
int L[maxnode] , R[maxnode] , U[maxnode] , D[maxnode] ;
int H[maxr] ; int ansd , ans[maxr] ; void init( int N ) {
n = N ;
// 第一行的虚拟结点
for( int i = 0 ; i <= n ; i ++ ) {
U[i] = D[i] = i ;
L[i] = i - 1 ;
R[i] = i + 1 ;
}
R[n] = 0 ; L[0] = n ;
sz = n + 1 ;
// 每一列的个数
memset( S , 0 , sizeof(S) ) ;
// H[i] = -1 表示这一行还没有 1
// 否则表示第一个 1 的 sz 是多少
memset( H , -1 , sizeof(H)) ;
} // 在第r行第c列加入一个1
void Link( int r , int c ) {
row[sz] = r ;
col[sz] = c ;
S[c] ++ ; D[sz] = c ; U[sz] = U[c] ;
D[U[c]] = sz ; U[c] = sz ; if( H[r] < 0 ) { H[r] = L[sz] = R[sz] = sz ; }
else{
R[sz] = H[r] ;
L[sz] = L[H[r]] ;
R[L[sz]] = sz ;
L[R[sz]] = sz ;
} sz ++ ; } // 删除 第 c 列
void remove ( int c ) {
// 删除虚拟结点中的 c 列
L[R[c]] = L[c] ;
R[L[c]] = R[c] ;
// 从 c 列向下遍历
FOR( i , D , c ) {
// 删除遍历到的行
FOR( j , R , i ) {
D[U[j]] = D[j] ;
U[D[j]] = U[j] ;
-- S[col[j]] ;
}
}
} // 恢复第 c 列
void restore( int c ) {
FOR( i , U , c ) {
FOR( j , L , i ) {
++S[col[j]] ;
U[D[j]] = D[U[j]] = j ;
}
}
L[R[c]] = R[L[c]] = c ;
} bool dfs( int d ) {
// 假设已经没有列了 ， 算法结束
if( R[0] == 0 ) {
ansd = d ;
return true ;
} // 找到 s 最小的列 , 加快搜索的速度
int c = R[0] ;
FOR( i , R , 0 ) {
if( S[i] < S[c] ) c = i ;
} // 删除第 c 列
remove( c ) ; // 遍历选中列中有1的行
FOR( i , D , c ) {
ans[d] = row[i] ;
// 删除选中行中有1的列
FOR( j , R , i ) {
remove( col[j] ) ;
}
if( dfs( d + 1 ) ) return true ;
// 回复删除掉的列
FOR( j , L , i ) {
restore( col[j] ) ;
}
}
restore( c ) ;
return false ;
} bool solve() {
if( !dfs(0) ) return false ;
return true ;
}
} dlx ; int ans[15][15] ; const int SLOT = 0 ;
const int ROW = 1 ;
const int COL = 2 ;
const int SUB = 3 ; inline int encode ( int a , int b , int c ) {
return a * 9 * 9 + b * 9 + c + 1 ;
} int main(){
char str[5] ;
int casn = 0 ;
while( scanf( "%s" , str ) != EOF ) { if( str[0] == '?' ) {
ans[0][0] = 0 ;
}else{
ans[0][0] = str[0] - '0' ;
}
for( int i = 0 ; i < 9 ; i ++ ) {
for( int j = 0 ; j < 9 ; j ++ ) {
if( i == 0 && j == 0 ) continue ;
scanf( "%s" , str ) ;
if( str[0] == '?' )
ans[i][j] = 0 ;
else
ans[i][j] = str[0] - '0' ;
}
} if( casn ++ ) {
puts( "" ) ;
} dlx.init( 9 * 9 * 4 ) ; for( int i = 0 ; i < 9 ; i ++ ) {
for( int j = 0 ; j < 9 ; j ++ ) {
for( int k = 0 ; k < 9 ; k ++ ) {
int rr = encode( i , j , k ) ;
if( ans[i][j] == 0 || ans[i][j] == k + 1 ) {
dlx.Link( rr , encode( SLOT , i , j ) ) ;
dlx.Link( rr , encode( ROW , i , k ) ) ;
dlx.Link( rr , encode( COL , j , k ) ) ;
dlx.Link( rr , encode( SUB , ( i / 3 ) * 3 + j / 3 , k ) ) ; }
}
}
} dlx.solve() ;
for( int i = 0 ; i < dlx.ansd ; i ++ ) {
int r , c , v ;
int t = dlx.ans[i] ;
t -- ;
v = t % 9 ;
t /= 9 ;
c = t % 9 ;
t /= 9 ;
r = t ;
ans[r][c] = v + 1 ;
}
for( int i = 0 ; i < 9 ; i ++ ) {
for( int j = 0 ; j < 9 ; j ++ ) {
printf( j == 8 ?"%d\n" : "%d " , ans[i][j] ) ;
}
}
}
return 0 ;
}