【分享】解独数程序 刚研究出来的^_^
什么叫数独就不多少了 不知道的自己百度吧；输入要求空的地方以0代替就行^_^
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=800*800;
int l[MAX],r[MAX],u[MAX],d[MAX];
int s[MAX],col[MAX],row[MAX];
int mp[10][10],head[10][10][10];
void insert_node(int cnt, int c){
s[c]++;
col[cnt] = c;
u[d[c]]=cnt;
d[cnt] = d[c];
u[cnt] =c;
d[c] = cnt;
}
void remove(int c){
l[r[c]] = l[c];
r[l[c]] = r[c];
for(int i=d[c]; i!=c; i=d[i])
for(int j=r[i]; j!=i; j=r[j]){
u[d[j]] = u[j];
d[u[j]] = d[j];
--s[col[j]];
}
}
void Resume(int c){
l[r[c]] = r[l[c]] = c;
for(int i= u[c]; i!=c; i=u[i]){
for(int j=l[i]; j!=i; j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
++s[col[j]];
}
}
}
bool DFS(int k){
if(k > 81 ) return true;
int min=MAX,c;
for(int i=r[0]; i!=0; i=r[i]){
if( !s[i] ) return false;
if(s[i] < min ){
min = s[i];
c=i;
}
}
remove(c);
for(int i=d[c]; i!=c; i=d[i]){
mp[row[i]/100][(row[i]/10)%10] = row[i]%10;
for(int j=r[i]; j!=i; j=r[j])
remove(col[j]);
if( DFS(k+1) ) return true;
for(int j=l[i]; j!=i; j=l[j])
Resume(col[j]);
}
Resume(c);
return false;
}
int main(){
while(true){
for(int i=1; i<=9; ++i){
for(int j=1; j<=9; ++j)
scanf("%d",&mp[i][j]);
}
int sum=(9+9+9)*9+9*9;
for(int i=0; i<=sum; ++i){
s[i]=0;
l[i]=i-1;
r[i]=i+1;
u[i]=d[i]=i;
}
l[0]=sum;
r[sum]=0;
int cnt=sum;
for(int i=1; i<=9; ++i){
for(int j=1; j<=9; ++j){
for(int k=1; k<=9; ++k){
for(int u=1; u<=4; ++u){
l[cnt+u]=cnt+u-1;
r[cnt+u]=cnt+u+1;
row[cnt+u] = i*100+j*10+k;
}
l[cnt+1] = cnt+4;
r[cnt+4] = cnt+1;
insert_node(cnt+1,(i-1)*9+j);
insert_node(cnt+2,81+(i-1)*9+k);
insert_node(cnt+3,81*2+(j-1)*9+k);
insert_node(cnt+4,81*3+(((i-1)/3)*3+(j-1)/3)*9+k);
head[i][j][k] = cnt+1;
cnt+=4;
}
}
}
int k=0;
for(int i=1; i<=9; ++i)
for(int j=1; j<=9; ++j){
if(mp[i][j]){
++k;
remove(col[head[i][j][mp[i][j]]]);
for(int w=r[head[i][j][mp[i][j]]]; w!=head[i][j][mp[i][j]]; w=r[w])
remove(col[w]);
}
}
if( DFS(k+1) ){
puts("解为：");
for(int i=1; i<=9; ++i){
for(int j=1; j<=9; ++j)
printf("%d ",mp[i][j]);
puts("");
}
puts("");
}else{
puts("无解");
}
}
return 0;
}
[ 本帖最后由 草狼 于 2011-8-26 17:32 编辑 ]
