http://blog.sina.com.cn/s/blog_51cea4040100gxn1.html 下面内容是此链接的作者发给我的，可能是ccy自己写的也可能是她的朋友写的。
QQ及邮箱：1 4 2 3 1 7 3 7 8 3 @qq.com 欢迎吹毛求疵。
//这一版的特点是dfs时是按照 影响因子（存储在f[][]中) 顺序搜索的。 fenlan那题耗时约270ms
#include <iostream>
#include<cstdlib>
#include<time.h>
#define s 3
#define ss s*s
using namespace std;
int f[ss][ss],all=0,g[ss*ss][2],h[ss][ss],ans,tot=0;
bool b[ss][ss+1],c[ss][ss+1],d[ss][ss+1],e[ss][ss];
int a[9][9]={
8,0,0,0,0,0,0,0,0,
0,0,3,6,0,0,0,0,0,
0,7,0,0,9,0,2,0,0,
0,5,0,0,0,7,0,0,0,
0,0,0,0,4,5,7,0,0,
0,0,0,1,0,0,0,3,0,
0,0,1,0,0,0,0,6,8,
0,0,8,5,0,0,0,1,0,
0,9,0,0,0,0,4,0,0};
void make(int i,int j,bool o)
{
int z;
z=a[i][j];
b[i][z]=o;
c[j][z]=o;
d[i/s*s+j/s][z]=o;
}
void get(int x,int& a,int& b)
{
if (x<3)
{
a=0;
b=2;
}
else if (x<6)
{
a=3;
b=5;
}
else
{
a=6;
b=8;
}
}
void mark(int x,int y)
{
int i,j,o,p,u,v;
e[x][y]=true;
for (i=0;i<ss;i++)
{
f[x][i]++;
f[i][y]++;
}
get(x,u,v);
get(y,o,p);
for (i=u;i<=v;i++)
for (j=o;j<=p;j++)
f[i][j]++;
}
bool work(int k,int r)
{
int i,x=g[k][0],y=g[k][1];
if (k==ss*ss-all)
{
ans=r;
return(true);
}
for (i=1;i<=ss;i++)
if (!b[x][i]&&!c[y][i]&&!d[x/s*s+y/s][i])
{
a[x][y]=i;
make(x,y,true);
if(work(k+1,r+i*h[x][y])) return(true);
make(x,y,false);
a[x][y]=0;
}
return(false);
}
void score()
{
int i,j;
for (i=0;i<ss;i++)
for (j=0;j<ss;j++)
{
if (i==0||j==0||i==8||j==8)
h[i][j]=6;
else if (i==1||j==1||i==7||j==7)
h[i][j]=7;
else if (i==2||j==2||i==6||j==6)
h[i][j]=8;
else if (i==3||j==3||i==5||j==5)
h[i][j]=9;
else
h[i][j]=10;
tot+=h[i][j];
}
}
int main()
{
int i,j,r=0,u,v,k,ma;
long time1,time2;
time1=clock();
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
memset(e,0,sizeof(e));
memset(f,0,sizeof(f));
score();
for (i=0;i<ss;i++)
for (j=0;j<ss;j++)
{
if (a[i][j]>0)
{
all++;
make(i,j,true);
mark(i,j);
r+=a[i][j]*h[i][j];
}
}
for (k=0;k<ss*ss-all;k++)
{
ma=0;
for (i=0;i<ss;i++)
for (j=0;j<ss;j++)
if (!e[i][j] && f[i][j]>ma)
{
ma=f[i][j];
u=i;
v=j;
}
mark(u,v);
g[k][0]=u;
g[k][1]=v;
}
work(0,r);
time2=clock();
if (!ans)
printf("No answer!\n");
else
printf("%d\n",ans);
printf("%d\n",time2-time1);
system("pause");
}