本人蒟蒻，发个蒟蒻看得懂的题解~~

dfs代码最终效率不高——2000ms——3000多ms，（但是AC了，或许是数据水吧）

大家玩过数独（没玩过的先了解规则去吧）

我的思路是dfs（不打表），用一个序列s[ ]保存要填的点，dfs携带的参数就是要填写的点的坐标：

s[ i ][0]与s[ i ][1]存点的坐标，s[ i ][2]存点的分值，s[ i ][3]存点的所在宫（我用函数现生成，避免了打表）。

需要注意的有如下几点：

一、dfs过程中就判断数能不能放，别放到最后判断（这一条可能是废话）实现方法用三个数组分别存各行、列、宫每个数字的状态（0表示没填过，1表示填过）

（重要）二、dfs层数与0的个数有关，层数太多就TLE了，我们知道，一行中填过的数字越多，需要填的数越少，就意味着dfs层数越少！所以，我们先填0的数量少的行。（详细实现见代码）

不懂的看这：）

0 0 0 0 0 0 0 0 0    //这一行有9个0
1 0 0 0 0 5 9 0 0  //这一行有6个0
0 0 0 2 0 0 0 8 0 //这一行有7个0
0 0 5 0 2 0 0 0 3 //这一行有6个0
0 0 0 0 0 0 6 4 8 //这一行有6个0
4 1 3 0 0 0 0 0 0 //这一行有6个0
0 0 7 0 0 2 0 9 0 //这一行有6个0
2 0 1 0 6 0 8 0 4 //这一行有4个0
0 8 0 5 0 4 0 1 2//这一行有4个0

在这个例子中，从第一行到第九行dfs的话，那么dfs第一层就有9种情况！！！根据dfs的原理，从第一层9种情况开始拓展，那么时间就要花很多。而若从第8层开始只有4种情况，搜索需要的时间就大大减少。TLE再见！！

Code：

#include<iostream>
#include<algorithm>
using namespace std;
struct f
{
    int rank,sum;//定义结构体，将行号与0的个数对应
}cou[10];
int a[10][10],hang[10][10],lie[10][10],gong[10][10],s[100][4],u,ok,most=-1,have;
int which(int,int);//给出两个整型变量代表坐标，返回此坐标的所在宫
int point(int,int);//给出两个整型变量代表坐标，返回此坐标的分值
void dfs(int,int);
bool cmp(f a,f b)
{
    return a.sum<b.sum;
}
int main()
{
    for(int i=1;i<=9;i++)  cou[i].rank=i;//rank存其初始行号，排序后就不会丢失
    for(int i=1;i<=9;i++)
    for(int j=1;j<=9;j++)
    {
        cin>>a[i][j];
        if(a[i][j]>0)
        hang[i][a[i][j]]=lie[j][a[i][j]]=gong[which(i,j)][a[i][j]]=1,have+=a[i][j]*point(i,j);//非零就不存储到搜索数组s中，但将这个点的值在其所在行、列、宫中标记 ，计算加分
        else  cou[i].sum++;//是0就计数
    }
    sort(cou+1,cou+10,cmp);//排序，0少的在前
    for(int i=1;i<=9;i++)//整理s数组，准备搜索
    {
        for(int j=1;j<=9;j++)//先搜0少的行
        if(a[cou[i].rank][j]==0)
        s[u][0]=cou[i].rank,s[u][1]=j,s[u][2]=point(cou[i].rank,j),s[u++][3]=which(cou[i].rank,j);//保存不解释
    }
    dfs(0,have);//搜索
    cout<<most<<endl;//most保存答案，初始值为-1
    return 0;
}

void dfs(int p,int score)// 表示正在搜s[p],score为目前分数
{
    if(p==u)//合法填完了所有的数
    {
        if(score>most)  most=score;//更大就更新
        return;
    }
    for(int i=1;i<=9;i++)
    {
        if(!hang[s[p][0]][i]&&!lie[s[p][1]][i]&&!gong[s[p][3]][i])//判断可不可以将i填入
        {
            hang[s[p][0]][i]=lie[s[p][1]][i]=gong[s[p][3]][i]=1;//填了后就将这个点的值在其所在行、列、宫中标记
            dfs(p+1,score+(s[p][2]*i));//下一层递归
            hang[s[p][0]][i]=lie[s[p][1]][i]=gong[s[p][3]][i]=0;//回溯
        }
    }
    return;
}

int which(int i,int j)
{
    if(i<=3)
    {
        if(j<=3)        return 1;
        else if(j<=6)   return 2;
        else            return 3;
    }
    else if(i<=6)
    {
        if(j<=3)        return 4;
        else if(j<=6)    return 5;
        else            return 6;
    }
    else
    {
        if(j<=3)        return 7;
        else if(j<=6)   return 8;
        else            return 9;
    }
}

int point(int i,int j)
{
    if(i==1||j==1||i==9||j==9)   return 6;
    if(i==2||j==2||i==8||j==8)     return 7;
    if(i==3||j==3||i==7||j==7)   return 8;
    if(i==4||j==4||i==6||j==6)   return 9;
    return 10;
}

我认为已经很详细了，还不懂私我。

B33 Dancing Links 舞蹈链 靶形数独

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 3245;			// 点729*4+列头324
int n, m, cnt;				// 矩阵的长,宽,点的编号
int u[N], d[N], l[N], r[N]; // 每个点的上下左右
int row[N], col[N];			// 每个点所在行,列
int h, t;					// 每行的头,尾指针
int s[N];					// 每列的节点数
int ans[N];					// 选了那些行
int a[10][10];				// 数独的数
int res = -1;
const int w[9][9] =
	{6, 6, 6, 6, 6, 6, 6, 6, 6,
	 6, 7, 7, 7, 7, 7, 7, 7, 6,
	 6, 7, 8, 8, 8, 8, 8, 7, 6,
	 6, 7, 8, 9, 9, 9, 8, 7, 6,
	 6, 7, 8, 9, 10, 9, 8, 7, 6,
	 6, 7, 8, 9, 9, 9, 8, 7, 6,
	 6, 7, 8, 8, 8, 8, 8, 7, 6,
	 6, 7, 7, 7, 7, 7, 7, 7, 6,
	 6, 6, 6, 6, 6, 6, 6, 6, 6};

void init()
{ // 初始化第0行的列表头
	for (int y = 0; y <= m; y++)
	{
		u[y] = d[y] = y;
		l[y] = y - 1;
		r[y] = y + 1;
	}
	l[0] = m;
	r[m] = 0;
	cnt = m + 1; // 下一个点的编号
}
void link(int x, int y)
{ // 在x行y列插入点
	row[cnt] = x;
	col[cnt] = y;
	s[y]++;
	u[cnt] = u[y]; // y...u[y]←→cnt←→y
	d[u[y]] = cnt;
	d[cnt] = y;
	u[y] = cnt;
	l[cnt] = t; // h...t←→cnt←→h
	r[t] = cnt;
	r[cnt] = h;
	l[h] = cnt;
	t = cnt++; // t指向cnt,然后cnt+1
}
void remove(int y)
{ // 删除y列与关联行
	r[l[y]] = r[y], l[r[y]] = l[y];
	for (int i = d[y]; i != y; 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 y)
{ // 恢复y列与关联行
	r[l[y]] = y, l[r[y]] = y;
	for (int i = u[y]; i != y; i = u[i])	 // 向上
		for (int j = l[i]; j != i; j = l[j]) // 向左
			u[d[j]] = j, d[u[j]] = j, s[col[j]]++;
}
void dance(int dep)
{
	if (r[0] == 0)
	{
		int s = 0;
		for (int i = 0, x, y, v; i < dep; i++)
		{
			x = (ans[i] - 1) / 9 / 9; // 链表行→数独
			y = (ans[i] - 1) / 9 % 9;
			v = (ans[i] - 1) % 9 + 1;
			s += w[x][y] * v;
		}
		res = max(res, s);
		return;
	}
	int y = r[0]; // 找到点最少的列
	for (int i = r[0]; i; i = r[i])
		if (s[i] < s[y])
			y = i;
	remove(y);
	for (int i = d[y]; i != y; i = d[i])
	{
		ans[dep] = row[i];
		for (int j = r[i]; j != i; j = r[j])
			remove(col[j]);
		dance(dep + 1);
		for (int j = l[i]; j != i; j = l[j])
			resume(col[j]);
	}
	resume(y);
}
int main()
{
	n = 729;
	m = 324;
	init();
	for (int i = 0; i < 9; i++)
	{ // 数独的行
		for (int j = 0, x; j < 9; j++)
		{ // 数独的列
			scanf("%d", &x);
			a[i][j] = x;
			for (int k = 1; k <= 9; k++)
			{ // 9个数
				if (x == 0 || x == k)
				{
					h = t = cnt;				   // 每行的第一个点
					int r = i * 9 * 9 + j * 9 + k; // 数独→链表行
					link(r, i * 9 + j + 1);
					link(r, 81 * 1 + i * 9 + k);
					link(r, 81 * 2 + j * 9 + k);
					link(r, 81 * 3 + (i / 3 * 3 + j / 3) * 9 + k);
				}
			}
		}
	}
	dance(0);
	printf("%d", res);
}