靶形数独是一个经典的NP完全问题，没有多项式算法，显然需要搜索，递归回溯会优于枚举。然而此题数据范围大，如果朴素搜索显然肯定TLE，于是我们就需要一些优化。

    1.在搜索中，每次我们都需要查找当前格子的可填数字，如果用二进制数集存储的话，可以大大减少运行时间。对于一个格子(x,y)，可选数字为x行、y列、所在九宫格的可选数字集合的交集，用二进制存储，利用位运算实现，可过75%的数据。

    2.贪心优化。如果是人做数独，必然先考虑可填数小的格子，本题也是如此。如果只是简单地从上往下搜索，会产生很多无用的状态，如果先填可填数小的格子，可以给其它的格子更多的限制，剪去许多不可行的分支。前面填的格子可能会对后面产生影响，因此可以每次都更新一遍，然后找到最小值。

    具体程序见下面。

    这题还有一个方法，用DLX（dancing links）。简单的说， Dancing Links 主要是用双向十字链表来存储稀疏矩阵，来达到在搜索中的优化。在搜索问题中，所需要存储的矩阵往往随着递归的加深会变得越来越稀疏，这种情况用Dancing Links 来存储矩阵，往往可以取得非常好的效果。DLX就是利用了双向链表的删除和重新插入的方便快速，把矩阵不断删除一些行和列，回溯时再恢复，使得在递归回溯中得到相当快的速度。具体程序也就不实现了。这方面的典型题目就是精确覆盖问题，很多数独问题也可以转化为此类问题。poj3074就可以用此方法。DLX是很通用的搜索优化方法，有兴趣的话，可以自己查找资料,这是一篇中文版的论文。

   

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
      
       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.