QQ及邮箱：1 4 2 3 1 7 3 7 8 3 @qq.com
//本代码用于测试dlx dfs算法，后来写的recover_part_graph()可谓一箭三雕 时空降低，且不用重复delete
//最后把惯用的system("pause") 是因为计算机并行测试多个算法，去掉后运行完自动退出程序释放全局变量中的一部分内存。
//解出题后用两原则检测，45 ，每个小集团内部互异
//也暴露了两个问题，在这里不需要解决它们，1：使用了挺多全局变量 2：如何delete一个图的各个节点，要有条不紊
#include<iostream>
#include<time.h>
#include<cstdlib>
#include<vector>
#include<fstream>
#include<stdio.h>
using namespace std;
#define K 3
#define BLANKS 59
#define FAIL 20
#define ROW (K*K*K*K*K*K)
#define COL (K*K*K*K*3)
int table[K*K+1][K*K+1],table_for_solve[K*K+1][K*K+1],solves=0;
int pro_k_col[K*K+2][K*K*K*K],pro_col_k[K*K*K*K][K*K+1],probable[K*K][K*K],num=0;
FILE* out_stream; //pro_col_k probable 是为了调试方便设置的，考虑到时空复杂度影响很小把它保留了下来
int int_start[K*K*K*K];
vector<int> must_add1; vector<vector<int>> must_add2;
typedef struct node{
unsigned int tailvex,headvex;
struct node *tlink1,*tlink2,*hlink1,*hlink2; // in out这里用十字链表的含义，在node ylist[]中这个含义发生了变化。
};
node* a[COL];
typedef struct {
node vexnode[ROW+COL];
node head;
}graph;
graph G;
int room(int row,int col);
void cregraph(graph G);
void recover_part_graph();
void init();
void subtraction(int pos,int k);
void add(int k);
bool DFS();
void remove(int c);
void resume(int c);
void print_storage();
bool fun( int array[10]);
bool test();
void shuffle(int arr[]);
bool test(int x, int y, int v);
bool put(int line, int index);
bool put_line(int line);
void print_all();
void dfs();
int check(int y,int x,int *mark) ; //求probable[y][x] 并且mark[]中为0的元素说明可以试探
int solve();
bool create_game(int blanks);
void print_all(int k); //输出到文件
void copy(int a[K*K+1][K*K+1],int b[K*K+1][K*K+1]);
int room(int row,int col)
{
return(row/K*K+col/K);
}
void cregraph()
{
G.head.tailvex=G.head.headvex=65535; //初始化head
G.head.hlink1=G.head.hlink2=G.head.tlink1=G.head.tlink2=NULL;
for(int i=0;i<=COL-1;i++) //初始化列头那一行
{
G.vexnode[i].tailvex=0; G.vexnode[i].headvex=i;
G.vexnode[i].hlink1=G.vexnode[i].hlink2=G.vexnode[i].tlink1=G.vexnode[i].tlink2=NULL;
}
for(int i=COL;i<=ROW+COL-1;i++) //初始化行头那一列
{
G.vexnode[i].tailvex=i-COL; G.vexnode[i].headvex=0;
G.vexnode[i].hlink1=G.vexnode[i].hlink2=G.vexnode[i].tlink1=G.vexnode[i].tlink2=NULL;
}
for(int i=ROW+COL-1;i>=COL;i--) //建十字单向链表
{
int pos,row,col,rom,col1,col2,col3;
pos=(i-COL)/(K*K); row=pos/(K*K); col=pos%(K*K); rom=room(row,col);
col1=row*K*K+col;
col2=K*K*K*K+K*K*col+row;
col3=2*K*K*K*K+K*K*rom+(row-row/K*K)*K+col-col/K*K;
node* p= new node;
p->tailvex=i-COL;
p->headvex=col3;
p->tlink1=G.vexnode[i].tlink1;
p->hlink1=G.vexnode[col3].hlink1;
G.vexnode[i].tlink1=G.vexnode[col3].hlink1=p;
node* q= new node;
q->tailvex=i-COL;
q->headvex=col2;
q->tlink1=G.vexnode[i].tlink1;
q->hlink1=G.vexnode[col2].hlink1;
G.vexnode[i].tlink1=G.vexnode[col2].hlink1=q;
node* r= new node;
r->tailvex=i-COL;
r->headvex=col1;
r->tlink1=G.vexnode[i].tlink1;
r->hlink1=G.vexnode[col1].hlink1;
G.vexnode[i].tlink1=G.vexnode[col1].hlink1=r;
}
for(int i=0;i<=COL-1;i++) //每一列的单链表变为双链表
{
int j=0; node* t=&G.vexnode[i];
do
{
t->hlink1->hlink2=t;
t=t->hlink1;
j++;
}while(j<K*K);
G.vexnode[i].hlink2=t;
t->hlink1=&G.vexnode[i];
}
for(int i=COL;i<=ROW+COL-1;i++) //每一行的单链表变为双链表
{
int j=0; node* t=&G.vexnode[i];
do
{
t->tlink1->tlink2=t;
t=t->tlink1;
j++;
}while(j<3);
G.vexnode[i].tlink2=t;
t->tlink1=&G.vexnode[i];
}
G.head.tlink1=&G.vexnode[0]; G.head.tlink2=&G.vexnode[K*K*K*K-1]; //将head节点和vexnode[0]---vexnode[K*K*K*K-1]用双链表
G.vexnode[0].tlink2=&G.head; G.vexnode[0].tlink1=&G.vexnode[1];
for(int i=1;i<=K*K*K*K-2;i++)
{
G.vexnode[i].tlink2=&G.vexnode[i-1];
G.vexnode[i].tlink1=&G.vexnode[i+1];
}
G.vexnode[K*K*K*K-1].tlink2=&G.vexnode[K*K*K*K-2];
G.vexnode[K*K*K*K-1].tlink1=&G.head;
for(int i=0;i<=COL-1;i++) //把列头那一行的指针存储在a[]中，subtraction时不需要移动很多次指针
a[i]=&G.vexnode[i];
}
void recover_part_graph()
{
G.head.tlink1=&G.vexnode[0]; G.head.tlink2=&G.vexnode[K*K*K*K-1]; //将head节点和vexnode[0]---vexnode[K*K*K*K-1]用双链表
G.vexnode[0].tlink2=&G.head; G.vexnode[0].tlink1=&G.vexnode[1];
for(int i=1;i<=K*K*K*K-2;i++)
{
G.vexnode[i].tlink2=&G.vexnode[i-1];
G.vexnode[i].tlink1=&G.vexnode[i+1];
}
G.vexnode[K*K*K*K-1].tlink2=&G.vexnode[K*K*K*K-2];
G.vexnode[K*K*K*K-1].tlink1=&G.head;
}
void init()
{
for(int i=0;i<=K*K-1;i++)
for(int j=0;j<=K*K-1;j++)
probable[i][j]=K*K;
for(int i=0;i<=K*K*K*K-1;i++)
pro_k_col[0][i]=K*K;
for(int i=0;i<=K*K*K*K-1;i++)
for(int j=1;j<=K*K;j++)
pro_k_col[j][i]=1;
for(int i=0;i<=K*K*K*K-1;i++)
pro_col_k[i][0]=K*K;
for(int i=0;i<=K*K*K*K-1;i++)
for(int j=1;j<=K*K;j++)
pro_col_k[i][j]=1;
for(int i=0;i<=K*K*K*K-1;i++)
if(int_start[i]!=0)
{
remove(i);
pro_k_col[K*K+1][i]=int_start[i];
subtraction(i,int_start[i]);
}
}
void subtraction(int pos,int k)
{
int row=pos/(K*K),col=pos%(K*K);
int rom=row/K*K+col/K,scol1,scol2,scol3;
scol1=K*K*row; scol2=K*K*K*K+K*K*col; scol3=K*K*K*K*2+rom*K*K;
node* t;
for(int j=scol1;j<=scol1+K*K-1;j++)
if(pro_k_col[k][j]==1)
{
pro_k_col[k][j]--;
pro_k_col[0][j]--;
pro_col_k[j][k]--;
pro_col_k[j][0]--;
probable[row][j%(K*K)]--;
must_add1.push_back(j);
}
for(int j=scol2;j<=scol2+K*K-1;j++)
{
t=a[j];
int c;
for(int i=0;i<=k-1;i++)
t=t->hlink1;
c=t->tlink2->headvex;
if(pro_k_col[k][c]==1)
{
pro_k_col[k][c]--;
pro_k_col[0][c]--;
pro_col_k[c][k]--;
pro_col_k[c][0]--;
probable[c/(K*K)][c%(K*K)]--;
must_add1.push_back(c);
}
}
for(int j=scol3;j<=scol3+K*K-1;j++)
{
t=a[j];
int c;
for(int i=0;i<=k-1;i++)
t=t->hlink1;
c=t->tlink2->tlink2->headvex;
if(pro_k_col[k][c]==1)
{
pro_k_col[k][c]--;
pro_k_col[0][c]--;
pro_col_k[c][k]--;
pro_col_k[c][0]--;
probable[c/(K*K)][c%(K*K)]--;
must_add1.push_back(c);
}
}
if(must_add1.size()==0) must_add1.push_back(K*K*K*K);
must_add2.push_back(must_add1);
must_add1.clear();
} // 我做了16*16 代码中的选择速度要慢，可能规模还是不大没体现它的优势，可是16*16已经把内存几乎都用光了
void add(int k)
{
int num=must_add2.size()-1;
if(must_add2[num][0]==K*K*K*K) return;
for(int j=must_add2[num].size()-1;j>=0;j--)
{
pro_k_col[k][must_add2[num][j]]++;
pro_k_col[0][must_add2[num][j]]++;
pro_col_k[must_add2[num][j]][k]++;
pro_col_k[must_add2[num][j]][0]++;
probable[must_add2[num][j]/(K*K)][must_add2[num][j]%(K*K)]++;
}
must_add2.pop_back();
}
bool DFS()
{
node* t=&G.head;
int count=K*K+1,c=-1;
if(t->tlink1==&G.head) return (true);
while(t->tlink1!=&G.head)
{
t=t->tlink1;
if(pro_k_col[0][t->headvex]<=count)
{
count=pro_k_col[0][t->headvex];
c=t->headvex;
}
}
remove(c);
for(int i=1;i<=K*K;i++)
if(pro_k_col[i][c]==1)
{
subtraction(c,i);
pro_k_col[K*K+1][c]=i;
if(DFS()==true) return(true);
add(i);
}
resume(c);
return(false);
}
void remove(int c)
{
a[c]->tlink2->tlink1=a[c]->tlink1;
a[c]->tlink1->tlink2=a[c]->tlink2;
}
void resume(int c)
{
a[c]->tlink2->tlink1=a[c];
a[c]->tlink1->tlink2=a[c];
}
void print_storage()
{
int row,col,node[K*K][K*K];
for(int i=0;i<=K*K*K*K-1;i++)
{
row=i/(K*K); col=i%(K*K);
node[row][col]=pro_k_col[K*K+1][i];
}
for(int i=0;i<=K*K-1;i++)
{
if(i%K==0) fprintf(out_stream,"\n");
for(int j=0;j<=K*K-1;j++)
if(j%K==0) fprintf(out_stream," %d",node[i][j]);
else fprintf(out_stream,"%d",node[i][j]);
fprintf(out_stream,"\n");
}
fprintf(out_stream,"\n");fprintf(out_stream,"\n");
}
bool fun( int a[10])
{
int i,j;
for(i=1;i<=8;i++)
{
if(*(a+i)==0) continue;
for(j=i+1;j<=9;j++)
if(*(a+i)==*(a+j)) return (false);
}
return (true);
}
bool test()
{
int row,col,node[K*K][K*K],aray[10];
for(int i=0;i<=K*K*K*K-1;i++)
{
row=i/(K*K); col=i%(K*K);
node[row][col]=pro_k_col[K*K+1][i];
}
int sum=0;
for(int i=1;i<=9;i++)
{
sum=0;
for(int j=1;j<=9;j++)
{ sum+=node[i-1][j-1]; aray[j]=node[i-1][j-1];}
if(sum!=45) return(false);
if(!fun(aray)) return (false);
}
for(int j=1;j<=9;j++)
{
sum=0;
for(int i=1;i<=9;i++)
{ sum+=node[i-1][j-1]; aray[i]=node[i-1][j-1];}
if(sum!=45) return(false);
if(!fun(aray)) return (false);
}
int rom_row,rom_col;
for(int rom=1;rom<=9;rom++)
{
sum=0;
int sub=1;
rom_row=(rom-1)/3*3+1; rom_col=(rom-1)%3*3+1;
for(int i=rom_row;i<=rom_row+2;i++)
for(int j=rom_col;j<=rom_col+2;j++)
{ sum+=node[i-1][j-1]; aray[sub++]=node[i-1][j-1];}
if(sum!=45) return(false);
if(!fun(aray)) return (false);
}
return(true);
}
void shuffle(int arr[])
{
int tmp, rd;
for(int i = 1; i <= K*K; i++)
{
rd = rand() % (K*K)+1;
tmp = arr[rd];
arr[rd] = arr[i];
arr[i] = tmp;
}
}
bool test(int x, int y, int v)
{
int _x = (x-1) / K * K+1;
int _y = (y-1) / K * K+1;
for(int i = _x; i < _x + 3; i++) //测试3 * 3矩阵内是否有重复的数
for(int j = _y; j < _y + 3; j++)
if(table[i][j] == v)
return false;
for(int i = 1; i <= K*K; i++) //测试横向、纵向是否有重复的数
{
if(table[x][i] == v || table[i][y] == v)
return false;
}
return true;
}
bool put(int line, int index)
{
if(index > K*K)
return true;
int num[K*K+1];
for(int i=1;i<=K*K;i++)
num[i]=i;
shuffle(num);
for(int i = 1; i <= K*K; i++)
//测试数字是否允许填入当前方格
if( test(line, index, num[i]) == true )
{
table[line][index] = num[i];
//填入成功则处理下一个方格
if( put(line, index + 1) == true )
return true;
}
table[line][index] = 0; //失败后复位
return false;
}
bool put_line(int line)
{
if(line > K*K)
return true;
if( put(line, 1) == true )
//当前一行添入完成后，进入下一行再重复处理。
if( put_line(line + 1) == true )
return true;
for(int i = 1; i <=K*K; i++)
table[line][i] = 0;
return false;
}
void print_all()
{
cout<<"print storage"<<endl;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
cout<<table[i-1][j-1]<<" ";
if(j%3==0) cout<<" ";
}
cout<<endl;
if(i%3==0) cout<<endl;
}
cout<<endl<<endl;
}
void dfs()
{
int i,j,im=-1,jm,min=100;
int mark[K*K+1];
for(i=1;i<=K*K;++i)
for(j=1;j<=K*K;++j)
{
if(table_for_solve[i][j])
continue;
int c=check(i,j,mark);
if(c==0)
return;
if(c<min)
{
im=i;
jm=j;
min=c;
}
}
if(im==-1)
{
solves++;
if(solves==2)
throw(1); //如果解法不唯一，不会等到所有解都出来才结束运行， 保留下面的return又能确定是不是只有唯一解。
return;
}
check(im,jm,mark);
for(i=1;i<=K*K;++i)
if(mark[i]==0)
{
table_for_solve[im][jm]=i;
dfs();
}
table_for_solve[im][jm]=0;
}
int solve()
{
try
{
dfs();
solves=0; //调试后发现
return(1);
}
catch(int)
{
solves=0; //调试后发现，solves是全局变量，以后solves越来越大永远不可能等于2
return(2);
}
}
int check(int y,int x,int *mark) //求probable[y][x]
{
int i,j,is,js,count=0;
for(i=1;i<=K*K;++i)
mark[i]=0;
for(i=1;i<=K*K;++i)
mark[table_for_solve[y][i]]=1;
for(i=1;i<=K*K;++i)
mark[table_for_solve[i][x]]=1;
is=(y-1)/K*K+1;
js=(x-1)/K*K+1;
for(i=0;i<K;++i)
for(j=0;j<K;++j)
mark[table_for_solve[is+i][js+j]]=1;
for(i=1;i<=K*K;++i)
if(mark[i]==0)
count++;
return count;
}
bool create_game(int blanks)
{
int i,k,row,col,tmp;
for( i=1;i<=blanks;i++)
{
int num=0;
do
{
do
{
k=rand()%(K*K*K*K)+1;
row=(k-1)/(K*K)+1;
col=k-K*K*(row-1);
tmp=table[row][col];
}while(tmp==0);
table[row][col]=0;
copy(table_for_solve,table);
num++;
if(num==FAIL) return(false);
}while((solve()==2)? table[row][col]=tmp : 0);
}
if(i==blanks+1) return (true);
}
void create_gameover()
{
for(int i=1;i<=K*K;i++)
for(int j=1;j<=K*K;j++)
table[i][j]=0;
for(int i = 1; i <=K*K; i++)
table[1][i] = i ;
shuffle(table[1]);
//从第二行开始添入数字
while(!put_line(2)) ;
}
void print_all(int k)
{
for(int i=0;i<=K*K-1;i++)
{
if(i%K==0) fprintf(out_stream,"\n");
for(int j=0;j<=K*K-1;j++)
if(j%K==0) fprintf(out_stream," %d",table[i+1][j+1]);
else fprintf(out_stream,"%d",table[i+1][j+1]);
fprintf(out_stream,"\n");
}
fprintf(out_stream,"\n");fprintf(out_stream,"\n");
}
void copy(int a[K*K+1][K*K+1],int b[K*K+1][K*K+1])
{
for(int i=1;i<=K*K;i++)
for(int j=1;j<=K*K;j++)
a[i][j]=b[i][j];
}
int main()
{
out_stream=fopen("d:\\my documents\\visual studio 2010\\projects\\测试算法\\测试dfs dls.txt","w+");
long time1,time2;
time1=clock();
cregraph();
srand((unsigned int)time(NULL));
for(unsigned op=1;op<=1000000;op++)
{
create_gameover();
while(!create_game(BLANKS))
create_gameover();
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
int_start[(i-1)*9+j-1]=table[i][j];
recover_part_graph();
init();
DFS();
if(test()) ;
else
{
fprintf(out_stream,"第%u题出错\n",op);
print_all(1);
}
}
time2=clock();
fprintf(out_stream,"耗时%u s,%d ms\n",(time2-time1)/1000,(time2-time1)%1000);
fclose(out_stream);
}