靶形数独是一个经典的NP完全问题，没有多项式算法，显然需要搜索，递归回溯会优于枚举。然而此题数据范围大，如果朴素搜索显然肯定TLE，于是我们就需要一些优化。
1.在搜索中，每次我们都需要查找当前格子的可填数字，如果用二进制数集存储的话，可以大大减少运行时间。对于一个格子(x,y)，可选数字为x行、y列、所在九宫格的可选数字集合的交集，用二进制存储，利用位运算实现，可过75%的数据。
2.贪心优化。如果是人做数独，必然先考虑可填数小的格子，本题也是如此。如果只是简单地从上往下搜索，会产生很多无用的状态，如果先填可填数小的格子，可以给其它的格子更多的限制，剪去许多不可行的分支。前面填的格子可能会对后面产生影响，因此可以每次都更新一遍，然后找到最小值。
具体程序见下面。
这题还有一个方法，用DLX（dancing links）。简单的说， Dancing Links 主要是用双向十字链表来存储稀疏矩阵，来达到在搜索中的优化。在搜索问题中，所需要存储的矩阵往往随着递归的加深会变得越来越稀疏，这种情况用Dancing Links 来存储矩阵，往往可以取得非常好的效果。DLX就是利用了双向链表的删除和重新插入的方便快速，把矩阵不断删除一些行和列，回溯时再恢复，使得在递归回溯中得到相当快的速度。具体程序也就不实现了。这方面的典型题目就是精确覆盖问题，很多数独问题也可以转化为此类问题。poj3074就可以用此方法。DLX是很通用的搜索优化方法，有兴趣的话，可以自己查找资料,http://sqybi.com/works/dlxcn/这是一篇中文版的论文。
View Code
1 const d:array[1..9,1..9]of longword=((1,1,1,1,1,1,1,1,1),
2 (1,2,2,2,2,2,2,2,1),
3 (1,2,3,3,3,3,3,2,1),
4 (1,2,3,4,4,4,3,2,1),
5 (1,2,3,4,5,4,3,2,1),
6 (1,2,3,4,4,4,3,2,1),
7 (1,2,3,3,3,3,3,2,1),
8 (1,2,2,2,2,2,2,2,1),
9 (1,1,1,1,1,1,1,1,1));
10 c:array[1..9,1..9]of longword=((1,1,1,2,2,2,3,3,3),
11 (1,1,1,2,2,2,3,3,3),
12 (1,1,1,2,2,2,3,3,3),
13 (4,4,4,5,5,5,6,6,6),
14 (4,4,4,5,5,5,6,6,6),
15 (4,4,4,5,5,5,6,6,6),
16 (7,7,7,8,8,8,9,9,9),
17 (7,7,7,8,8,8,9,9,9),
18 (7,7,7,8,8,8,9,9,9));
19 var i,j,n,m,k,l,min,x,y:longword;
20 a:array[0..9,0..9]of longword;
21 s1,s2,s3:array[0..9]of longword;
22 p:array[0..9,0..9]of boolean;
23 bo:boolean;
24 ans:longint;
25 function getnum(k:longword):longword;
26 begin
27 k:=(k and $55555555)+((k shr 1)and $55555555);
28 k:=(k and $33333333)+((k shr 2)and $33333333);
29 k:=(k and $0F0F0F0F)+((K shr 4)and $0F0F0F0F);
30 K:=(k and $00FF00FF)+((k shr 8)and $00FF00FF);
31 k:=(k and $0000FFFF)+((k shr 16)and $0000FFFF);
32 exit(k);
33 end;
34 procedure getmin(var x1,y1:longword);
35 var i,j,k,min,l:longword;
36 begin
37 min:=maxlongint;
38 for i:=1 to 9 do
39 for j:=1 to 9 do
40 if (a[i,j]=0) then
41 begin
42 k:=s1[i] or s2[j] or s3[c[i,j]];
43 k:=k xor 511;
44 k:=getnum(k);
45 if (k<min) then begin min:=k;x1:=i;y1:=j;end;
46 end;
47 end;
48 procedure go(step:longword);
49 var i,j,k,l,z,t,x,y:longword;
50 bak1,bak2,bak3:array[0..9]of longword;
51 begin
52 if step=m+1 then
53 begin
54 t:=0;
55 for i:=1 to 9 do
56 for j:=1 to 9 do
57 t:=t+a[i,j]*(d[i,j]+5);
58 if ans<t then ans:=t;
59 exit;
60 end;
61 getmin(x,y);
62 k:=511 xor(s1[x] or s2[y] or s3[c[x,y]]);
63 while k<>0 do
64 begin
65 l:=k and -k;
66 k:=k-l;
67 bak1:=s1;bak2:=s2;bak3:=s3;
68 s1[x]:=s1[x] or l;
69 s2[y]:=s2[y] or l;
70 s3[c[x,y]]:=s3[c[x,y]] or l;
71 case l of
72 1:j:=1;
73 2:j:=2;
74 4:j:=3;
75 8:j:=4;
76 16:j:=5;
77 32:j:=6;
78 64:j:=7;
79 128:j:=8;
80 256:j:=9;
81 end;
82 a[x,y]:=j;
83 go(step+1);
84 a[x,y]:=0;
85 s1:=bak1;s2:=bak2;s3:=bak3;
86 end;
87 end;
88 begin
89 assign(input,\'sudoku.in\');reset(input);
90 assign(output,\'sudoku.out\');rewrite(output);
91 fillchar(a,sizeof(a),0);
92 m:=81;
93 for i:=1 to 9 do
94 for j:=1 to 9 do
95 begin
96 read(a[i,j]);
97 if a[i,j]<>0 then
98 begin
99 s1[i]:=s1[i] or(1 shl(a[i,j]-1));
100 s2[j]:=s2[j] or(1 shl(a[i,j]-1));
101 s3[c[i,j]]:=s3[c[i,j]] or(1 shl(a[i,j]-1));
102 dec(m);
103 end;
104 end;
105 ans:=-1;
106 go(1);
107 writeln(ans);
108 close(input);close(output);
109 end.