记录编号	115897	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	筽邝	是否通过	通过
代码语言	Pascal	运行时间	3.480 s
提交时间	2014-08-23 14:52:48	内存使用	0.17 MiB

program cojs407;
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
  ans,t,count:longint;
  hang,lie,ge:array[1..9,1..9]of boolean;
  a:array[1..9,1..9]of longint;
  x,y:array[1 ..81]of longint;
  c:array[1..81]of boolean;

procedure init;
var
  i,j:longint;
begin
  ans:=-1; t:=0; count:=0;
  fillchar(hang,sizeof(hang),true);
  fillchar(lie,sizeof(lie),true);
  fillchar(ge,sizeof(ge),true);
  for i:=1 to 9 do
  for j:=1 to 9 do
  begin
    read(a[i,j]);
	if a[i,j]=0 then
	begin
	  inc(t);
	  x[t]:=i;
	  y[t]:=j;
	  c[t]:=true;
	end else begin
	  hang[i,a[i,j]]:=false;
	  lie[j,a[i,j]]:=false;
	  ge[z[i,j],a[i,j]]:=false;
	end;
  end;
end;

procedure calc;
var
  i,j,s:longint;
begin
  s:=0;
  for i:=1 to 9 do
  for j:=1 to 9 do
    inc(s,a[i,j]*fen[i,j]);
  if s>ans then ans:=s;
end;

procedure dfs(k:longint);
var
  xx,yy,i,j,min,w,p:longint;
begin
  inc(count);
  if count>10000000 then
  begin
    writeln(ans);
	close(input);close(output);
	halt;
  end;
  if k>t then
  begin
    calc;
	exit;
  end;
  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;
  xx:=x[p]; yy:=y[p]; c[p]:=false;
  for i:=1 to 9 do
  if hang[xx,i] and lie[yy,i] and ge[z[xx,yy],i] then
  begin
    a[xx,yy]:=i;
	hang[xx,i]:=false;
	lie[yy,i]:=false;
	ge[z[xx,yy],i]:=false;
	dfs(k+1);
	hang[xx,i]:=true;
	lie[yy,i]:=true;
	ge[z[xx,yy],i]:=true;
	a[xx,yy]:=0;
  end;
  c[p]:=true;
end;

begin
assign(input,'sudoku.in');reset(input);
assign(output,'sudoku.out');rewrite(output);

  init;
  dfs(1);
  writeln(ans);

close(input);close(output);
end.