记录编号	79869	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	752505176	是否通过	通过
代码语言	Pascal	运行时间	3.380 s
提交时间	2013-11-06 15:34:59	内存使用	0.17 MiB

program sudoku(input,output);
const
  z:array[1..9,1..9]of longint=
  ((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));
  fen:array[1..9,1..9]of longint=
  ((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));
var
  i,j,ans,l,u,sum,t:longint;
  m:array[0..9,0..9]of longint;
  hang,lie,ge:array[1..9,1..9]of boolean;
  x,y:array[0..81]of longint;
  c:array[0..81]of boolean;
  
procedure try(dep:longint);
var
  x1,y1,i,min,w,j,p:longint;
begin
  if dep>t then 
   begin
    sum:=0;
    for i:=1 to 9 do
     for j:=1 to 9 do
      sum:=sum+fen[i,j]*m[i,j];
    if sum>ans then ans:=sum;
   exit; 
  end
  else 
   begin
    min:=maxlongint;
    for i:=1 to t do
     if c[i] then
      begin
       w:=0;
       for j:=1 to 9 do
        if hang[x[i],j] and lie[y[i],j] and ge[z[x[i],y[i]],j] then
         begin
          inc(w);
          if w>=min then break;
         end;
       if w<min then 
        begin
         p:=i;
         min:=w;
        end;
      end;
   x1:=x[p];
   y1:=y[p];
   c[p]:=false;
   for i:=1 to 9 do
    if hang[x1,i] and lie[y1,i] and ge[z[x1,y1],i] then
     begin
      m[x1,y1]:=i;
      hang[x1,i]:=false;
      lie[y1,i]:=false;
      ge[z[x1,y1],i]:=false;
      try(dep+1);
      hang[x1,i]:=true;
      lie[y1,i]:=true;
      ge[z[x1,y1],i]:=true;
      m[x1,y1]:=0;
     end;
   c[p]:=true;
   end;
end;

begin
  assign(input,'sudoku.in');
  assign(output,'sudoku.out');
  reset(input);
  rewrite(output);
  ans:=-1;
  t:=0;
  for l:=1 to 9 do
   for u:=1 to 9 do
    begin
     hang[l,u]:=true;
     lie[l,u]:=true;
	end;
	fillchar(ge,sizeof(ge),true);
     for i:=1 to 9 do
      begin
       for j:=1 to 9 do
         begin
          read(m[i,j]);
          if m[i,j]=0 then 
           begin
            inc(t);
			x[t]:=i;
            y[t]:=j;
            c[t]:=true;
           end
          else 
           begin
            hang[i,m[i,j]]:=false;
            lie[j,m[i,j]]:=false;
            ge[z[i,j],m[i,j]]:=false;
           end
         end;
    readln;
   end;
  try(1);
   writeln(ans);
   close(input);
   close(output);
end.