QQ及邮箱：1 4 2 3 1 7 3 7 8 3 @qq.com
// 本代码用DLX算法解决9*9数独，特点是覆盖了前81列，战斗就解决了，把战斗浓缩在前81列。缺点是用了new 调试不方便，new的数组不好观测
//解题填空顺序存储在O[]中 舞池本来应该用双向十字链表做材料，本代码用二维数组模拟
//检查只有45原则，但一旦测试失败会输出题目和结果
#include<iostream>
#include<cstdlib>
#include<time.h>
#include<fstream>
using namespace std;
#define BLANKS 59
#define FAIL 20
fstream out_stream;
int table[9][9],table_for_solve[9][9],solves=0;
int node[10][10];
long time1,time2;
int O[82],S[82],a[730][244],O_sub=1;// O[]依次存储覆盖每一列用的行号，行号隐藏了哪一个格子填了哪一个候选数
int *U=new int[729967]; //S[82]存放前81列的候选数可能数，对应于每个格子的候选数
int *D=new int[729967]; //a[][]用来表示跳舞的舞池 U[] D[] R[] L[] 是舞池的设置
int *R=new int[729967];
int *L=new int[729967];
void shuffle(int arr[], int n);
bool test(int x, int y, int v);
bool put(int line, int index);
bool put_line(int line);
void dfs();
int check(int y,int x,int *mark) ; //求probable[y][x] 并且mark[]中为0的元素说明可以试探
int solve22();
bool create_game(int blanks);
void create_gameover();
void print_all(int k); //输出到文件
void copy(int a[9][9],int b[9][9]);
void remove(int c); //用来覆盖列
void resume(int c); //用来恢复列
bool DFS(int k); //每次优先覆盖候选数可能数最少的列
int room(int row,int col); // 给定行号，列号，求宫号
void init(); //预先处理：布置公共舞池，
void predo(); //对于特定的舞会（特定的数独题）还要事先做些准备工作
void print_all(); //把结果输出到相应的文件，即每个格子填什么数
void subtraction(int pos,int k); //减候选数 并取消某一格子对应的某一候选数 所对应的行的覆盖资格
void add(int pos,int k); //与上一函数相反
int row_room(int rom); //给定宫号，求宫的开始行号
int col_room(int rom); //给定宫号，求宫的开始列号
bool test();
void shuffle(int arr[], int n)
{
int tmp, rd;
for(int i = 0; i < n; i++)
{
rd = rand() % 9;
tmp = arr[rd];
arr[rd] = arr[i];
arr[i] = tmp;
}
}
bool test(int x, int y, int v)
{
int _x = x / 3 * 3;
int _y = y / 3 * 3;
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 = 0; i < 9; i++) //测试横向、纵向是否有重复的数
{
if(table[x][i] == v || table[i][y] == v)
return false;
}
return true;
}
bool put(int line, int index)
{
if(index > 8)
return true;
int num[] = {1,2,3,4,5,6,7,8,9};
//打乱当前准备写入数字的前后顺序
shuffle(num, 9);
for(int i = 0; i < 9; 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 > 8)
return true;
if( put(line, 0) == true )
//当前一行添入完成后，进入下一行再重复处理。
if( put_line(line + 1) == true )
return true;
for(int i = 0; i < 9; i++)
table[line][i] = 0;
return false;
}
void dfs()
{
int i,j,im=-1,jm,min=10;
int mark[10];
for(i=0;i<9;++i)
for(j=0;j<9;++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<=9;++i)
if(mark[i]==0)
{
table_for_solve[im][jm]=i;
dfs();
}
table_for_solve[im][jm]=0;
}
int solve22()
{
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<=9;++i)
mark[i]=0;
for(i=0;i<9;++i)
mark[table_for_solve[y][i]]=1;
for(i=0;i<9;++i)
mark[table_for_solve[i][x]]=1;
is=y/3*3;
js=x/3*3;
for(i=0;i<3;++i)
for(j=0;j<3;++j)
mark[table_for_solve[is+i][js+j]]=1;
for(i=1;i<=9;++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()%81;
row=k/9;
col=k-9*row;
tmp=table[row][col];
}while(tmp==0);
table[row][col]=0;
copy(table_for_solve,table);
num++;
if(num==FAIL) return(false);
}while((solve22()==2)? table[row][col]=tmp : 0);
}
if(i==blanks+1) return (true);
}
void create_gameover()
{
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
table[i][j]=0;
for(int i = 0; i < 9; i++)
table[0][i] = i + 1;
shuffle(table[0], 9);
//从第二行开始添入数字
while(!put_line(1)) ;
}
void print_all(int k)
{
for(int i=1;i<=9;i++)
{
if(i%3==1) out_stream<<endl;
for(int j=1;j<=9;j++)
{
if(j%3==1) out_stream<<" ";
out_stream<<table[i-1][j-1];
}
out_stream<<endl;
}
out_stream<<endl<<endl;
}
void copy(int a[9][9],int b[9][9])
{
for(int i=0;i<=8;i++)
for(int j=0;j<=8;j++)
a[i][j]=b[i][j];
}
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])
{
if(j%1000==0) continue;
U[D[j]]=U[j];
D[U[j]]=D[j];
//S[j%1000]--; 这里保留原来的痕迹 后来改动的原因是，减候选数只会会减前81列，原来不光subtraction会减remove也会减，remove不会减前81列候选数，这里删掉耗时肯定变少，S[244]-->S[82]空间消耗也变少，别小看耗时少了5ms
}
}
void resume(int c)
{
for(int i=U[c];i!=c;i=U[i])
for(int j=L[i];j!=i;j=L[j])
{
if(j%1000==0) continue;
U[D[j]]=j;
D[U[j]]=j;
//S[j%1000]++;
}
L[R[c]]=c;
R[L[c]]=c;
}
bool DFS(int k)
{
if(!R[0]) return(true);
int count=100,c;
for(int i=R[0];i<=81;i=R[i])//i改为i<=81
if(S[i]<count)
{
count=S[i];
c=i;
if(count==1) break;
}
remove(c);
for(int i=D[c];i!=c;i=D[i])
{
if(L[i]%1000==0)
{
int pos=(i/1000-1)/9+1,k1;//1<=pos<=81
k1=i/1000-9*(pos-1);
O[k]=i/1000;
subtraction(pos,k1);
for(int j=R[i];j%1000>0 && j%1000<244;j=R[j])//j!=i改为j!=0 && j!=1又改为j>1000 又改为j!=1000 && j!=2000
remove(j%1000);
if(DFS(k+1)) return (true);
for( int j=L[L[i]];j!=i;j=L[j])
resume(j%1000);
add(pos,k1);
}
}
resume(c);
return(false);
}
int room(int row,int col)
{
return((row-1)/3*3+1+(col-1)/3);
}
void init()
{
int row,col;
memset(U,0,729967*4);
memset(D,0,729967*4);
memset(R,0,729967*4);
memset(L,0,729967*4);
for(col=0;col<=243;col++)
{
L[col]=col-1;
R[col]=col+1;
}
L[0]=243; R[243]=0;
for(int i=1;i<=81;i++)
S[i]=9;
for( row=1;row<=729;row++)
{
int k=(row-1)/9+1;
int row1=(k-1)/9+1,col1=(k%9==0)?9:(k%9);
int acol1,acol2,acol3;
acol1=9*(row1-1)+col1;
acol2=9*(9+col1-1)+row1;
acol3=9*(18+room(row1,col1)-1)+(row1-(room(row1,col1)-1)/3*3-1)*3+col1-((room(row1,col1)-1)%3*3);
a[row][acol1]=1; a[row][acol2]=1; a[row][acol3]=1;
}
for(col=1;col<=243;col++)
{
int tmp;
row=1;
while(a[row][col]==0)
{ row++; } ;
tmp=row; ;
D[col]=1000*row+col;
U[1000*row+col]=col;
for(int i=row+1;i<=row+8;i++)//i<=729改为row+8 实验证明耗时降了1ms
if(a[i][col]==0) continue;
else
{
D[1000*tmp+col]=1000*i+col;
U[1000*i+col]=1000*tmp+col;
tmp=i;
}
D[1000*tmp+col]=col;
U[col]=1000*tmp+col;
}
for(row=1;row<=729;row+=9) //for循环内的内容经过替换 耗时减少大概0.5ms 不小心把原来for循环中的内容删掉了
{
int row0,col0,rom0,col1,col2,col3;
col1=(row-1)/9+1;
row0=(col1-1)/9+1;
col0=col1-9*(row0-1);
rom0=room(row0,col0);
col2=9*(9+col0-1)+row0;
col3=9*(18+rom0-1)+(row0-row_room(rom0))*3+(col0-col_room(rom0)+1);
for(int i=row;i<=row+8;i++)
{
R[i*1000]=i*1000+col1; L[i*1000+col1]=i*1000;
R[i*1000+col1]=i*1000+col2; L[i*1000+col2]=i*1000+col1;
R[i*1000+col2]=i*1000+col3; L[i*1000+col3]=i*1000+col2;
R[i*1000+col3]=i*1000; L[i*1000]=i*1000+col3;
}
}
}
void predo(int start[82])
{
for(int i=1;i<=81;i++)
if(start[i]!=0)
{
int row1=(i-1)/9+1,col1=(i%9==0)?9:(i%9);
int acol1,acol2,acol3;
acol1=9*(row1-1)+col1;
acol2=9*(9+col1-1)+row1;
acol3=9*(18+room(row1,col1)-1)+(row1-(room(row1,col1)-1)/3*3-1)*3+col1-(room(row1,col1)-(room(row1,col1)-1)/3*3-1)*3;
O[O_sub++]=9*(i-1)+start[i];
subtraction(i,start[i]);//原来是放在三个remove后 DFS中也要做相应调整
remove(acol1);
remove(acol2);
remove(acol3);
}
}
void print_all()
{
out_stream<<"print storage"<<endl;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
out_stream<<node[i][j]<<" ";
if(j%3==0) out_stream<<" ";
}
out_stream<<endl;
if(i%3==0) out_stream<<endl;
}
out_stream<<endl<<endl;
}
void subtraction(int pos,int k)
{
int row=(pos-1)/9+1,col=(pos%9==0)? 9:(pos%9);
int rom=room(row,col),scol1,scol2,scol3;
scol1=9*(row-1)+1; scol2=9*(9+col-1)+1; scol3=9*(18+rom-1)+1;
for(int j=scol1;j<=scol1+8;j++)
{
int m=D[j];//后来加的，发现j按原来代码j一下子变得很大，就出了循环 ，改过后for循环的代码看起来也更易理解
if(D[j]==j) continue; //这一列以前被remove掉，不该处理的不处理，该处理的一定处理
S[j]--;
while(L[m]/1000-(L[m]/1000-1)/9*9!=k) m=D[m];
L[m]+=244;R[L[m]]=m;L[L[m]]=R[R[m]]; R[R[R[m]]]=L[m];
}
for(int j=scol2;j<=scol2+8;j++)
{
int m=D[j];
if(D[j]==j) continue;
while(L[L[m]]/1000-(L[L[m]]/1000-1)/9*9!=k)
m=D[m];
if(L[m]%1000!=pos) S[L[m]%1000]--;
L[L[m]]+=244;R[L[L[m]]]=L[m];L[L[L[m]]]=R[m]; R[R[m]]=L[L[m]];
}
for(int j=scol3;j<=scol3+8;j++)
{
int m=D[j];
if(D[j]==j) continue;
while(R[m]/1000-(R[m]/1000-1)/9*9!=k) m=D[m];
if(((L[L[m]]/1000-1)/9)+1!=row && L[L[m]]%1000-(L[L[m]]%1000-1)/9*9!=col) S[L[L[m]]%1000]--;//if(((L[L[m]]/1000-1)/9)/9+1!=row)改为if(((L[L[m]]/1000-1)/9)/9+1!=row && L[L[m]]%1000-(L[L[m]]%1000-1)/9*9!=col)
R[m]+=244;L[R[m]]=m;R[R[m]]=L[L[m]]; L[L[L[m]]]=R[m]; //这样改使得同一个候选数不会使某个格子的probable值减两次，如果减两次下次选择覆盖列就不是最优化，我预测这样改会降低时间复杂度。
} //实际上耗时反而增加了，改前1674ms 改后3636ms 我还是觉得随着数独规模的增大比如16*16,25*25数独，改后的代码时间复杂度会更好
}
void add(int pos,int k)
{
int row=(pos-1)/9+1,col=(pos%9==0)? 9:(pos%9);
int rom=room(row,col),scol1,scol2,scol3;
scol1=9*(row-1)+1; scol2=9*(9+col-1)+1; scol3=9*(18+rom-1)+1;
for(int j=scol3+8;j>=scol3;j--)
{
int m=D[j];
if(D[j]==j) continue;//不该恢复的不恢复，该恢复的一定恢复，不管处理了几次恢复到原样
while(R[m]/1000-(R[m]/1000-1)/9*9!=k) m=D[m];
R[m]-=244;L[R[m]]=m;R[R[m]]=L[L[m]]; L[L[L[m]]]=R[m];
if(((L[L[m]]/1000-1)/9)+1!=row && L[L[m]]%1000-(L[L[m]]%1000-1)/9*9!=col) S[L[L[m]]%1000]++;
}
for(int j=scol2+8;j>=scol2;j--)
{
int m=D[j];
if(D[j]==j) continue;
while(L[L[m]]/1000-(L[L[m]]/1000-1)/9*9!=k) m=D[m];
L[L[m]]-=244;R[L[L[m]]]=L[m];L[L[L[m]]]=R[m]; R[R[m]]=L[L[m]];
if(L[m]%1000!=pos) S[L[m]%1000]++;
}
for(int j=scol1+8;j>=scol1;j--)
{
int m=D[j];
if(D[j]==j) continue;
while(L[m]/1000-(L[m]/1000-1)/9*9!=k) m=D[m];
L[m]-=244;R[L[m]]=m;L[L[m]]=R[R[m]]; R[R[R[m]]]=L[m];
S[j]++;
}
}
int row_room(int rom)
{
return((rom-1)/3*3+1);
}
int col_room(int rom)
{
return((rom-1)%3*3+1);
}
bool test()
{
int sum=0;
for(int i=1;i<=9;i++)
{
sum=0;
for(int j=1;j<=9;j++)
sum+=node[i][j];
if(sum!=45) return(false);
}
for(int j=1;j<=9;j++)
{
sum=0;
for(int i=1;i<=9;i++)
sum+=node[i][j];
if(sum!=45) return(false);
}
int rom_row,rom_col;
for(int rom=1;rom<=9;rom++)
{
sum=0;
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][j];
if(sum!=45) return(false);
}
return(true);
}
int main()
{
int int_start[82]; //开始用于存储从文件中读取的题目，后来用来存储解题结果
out_stream.open("d:\\my documents\\visual studio 2010\\projects\\测试算法\\测试 dlx 数组.txt");
time1=clock();
srand(time(0));
for(unsigned op=1;op<=1000000;op++)
{
create_gameover();
while(!create_game(BLANKS))
create_gameover();
int index=1;
for(int i=0;i<=8;i++)
for(int j=0;j<=8;j++)
int_start[index++]=table[i][j];
init();
predo(int_start);
DFS(O_sub);
for(int i=1;i<=81;i++)
int_start[(O[i]-1)/9+1]=O[i]-(O[i]-1)/9*9;
for(int i=1;i<=81;i++)
{
int row,col;
row=(i-1)/9+1;
col=(i%9==0)?9:(i%9);
node[row][col]=int_start[i];
}
if(test()) ;
else { out_stream<<"测试第"<<op<<"个题目失败"<<endl; print_all(1); print_all();}
O_sub=1;
}
time2=clock();
out_stream<<(time2-time1)/1000<<"s"<<(time2-time1)%1000<<"ms"<<endl;
delete[] U;
delete[] D;
delete[] R;
delete[] L;
}