noip2009靶形数独讲讲算法思想,就是思路

Question

noip2009靶形数独
讲讲算法思想,就是思路

Answer 1

　　这个问题嘛,果断是DFS,就是深搜啦...
　　基本思想：一共9*9=81个格,每个格如果没有数就for t:=1 to 9 do 检查是否可填t,填入、递归,如果搜到了第82层,也就是完成了一个数独,就算一下,更新最大值.搜完后输出最大值就ok了.
　　不过这个是果断过不了的.
　　如果你刚刚学DFS,估计你能过6个点也就可以了（一共20个点啊）；
　　如果你比较熟练了,就加些优化,大概可以过15个点（已经很不错了）；
　　如果再加卡时的话,大概最好能过18个点（这是正着搜）；
　　接下来你就知道该干啥了吧——
　　呵呵...倒着搜哈（也可以随机搜额）...这样大概就可以AC了（但这个果断是利用了数据的漏洞,不算完全的AC）
　　如果你真的想完全AC,就上网上搜搜Dancing Links,这个可以省去for t:=1 to 9 do 时的耗时,只用从链表中取出一个数就ok了.
　　加油AC这道题吧,如果你写程序熟练,最多一个多小时就能AC...
　　为了防止楼主对我的答案不够满意,附上我的倒着搜的程序代码,加点注释,希望可以帮助你理解.
　　program sudoku;
　　type arr=array[1..9]of integer;
　　var a:array[1..9,1..9]of integer;
　　xp,yp,zp:array[1..9]of arr;{分别是横行,竖列,9个九宫格的布尔判重数组}
　　t,k,i,j,m,n,max:longint;
　　const p:array[1..9,1..9]of integer= {每个格的分值}
　　((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));
　　q:array[1..9,1..9]of integer= {表示每个格属于的九宫格编号}
　　((1,1,1,2,2,2,3,3,3),
　　(1,1,1,2,2,2,3,3,3),
　　(1,1,1,2,2,2,3,3,3),
　　(4,4,4,5,5,5,6,6,6),
　　(4,4,4,5,5,5,6,6,6),
　　(4,4,4,5,5,5,6,6,6),
　　(7,7,7,8,8,8,9,9,9),
　　(7,7,7,8,8,8,9,9,9),
　　(7,7,7,8,8,8,9,9,9));
　　procedure init(x,y,i:integer);{把进数独的数做上标记}
　　var t,k:longint;
　　begin
　　xp[x,i]:=1;
　　yp[y,i]:=1;
　　zp[q[x,y],i]:=1;
　　end;
　　procedure outit(x,y,i:integer);{取消标记}
　　var t,k:longint;
　　begin
　　xp[x,i]:=0;
　　yp[y,i]:=0;
　　zp[q[x,y],i]:=0;
　　end;
　　procedure sou(x,y,total:integer);{DFS哈...}
　　var t,k,i:longint;
　　begin
　　if (x=0)and(y=9) then
　　begin
　　if total>max then max:=total;
　　exit;
　　end;
　　if m>20000000 then {这个是卡时,具体卡多少节点要看评测机速度}
　　begin
　　writeln(max);
　　halt;
　　end;
　　if a[x,y]>0 then
　　begin
　　t:=x;
　　k:=y-1;
　　if y=1 then
　　begin
　　dec(t);
　　k:=9;
　　end;
　　inc(m);
　　sou(t,k,total+a[x,y]*p[x,y]);
　　end
　　else
　　begin
　　t:=x;
　　k:=y-1;
　　if y=1 then
　　begin
　　dec(t);
　　k:=9;
　　end;
　　for i:=1 to 9 do
　　if (xp[x][i]=0)and(yp[y][i]=0)and(zp[q[x,y],i]=0) then
　　begin
　　inc(m);
　　init(x,y,i);
　　sou(t,k,total+i*p[x,y]);
　　outit(x,y,i);
　　end;
　　end;
　　end;
　　begin
　　for t:=1 to 9 do
　　begin
　　for k:=1 to 9 do
　　begin
　　read(a[t,k]);
　　if a[t,k]>0 then init(t,k,a[t,k]);
　　end;
　　readln;
　　end;
　　sou(9,9,0);{横坐标,纵坐标,当前得分}
　　if max=0 then max:=-1; {特判}
　　writeln(max);
　　end.
　　如果楼主对我的回答满意,就加点分奖励奖励吧,这个绝对是原创啊...