记录编号	4535	评测结果	AAAAAAAAAA
题目名称	填数	最终得分	100
用户昵称	EnAsn	是否通过	通过
代码语言	Pascal	运行时间	1.627 s
提交时间	2008-10-20 20:23:29	内存使用	0.12 MiB

program ex;
type
 ss=array[1..20,1..20]of integer;
 sz=array[1..400]of boolean;
var
 a:ss;  c,d:sz;
 n,t:integer;
 f1,f2:text;
procedure init;
 var
  i,j:integer;
 begin
  assign(f1,'tianshu.in');
  assign(f2,'tianshu.out');
  reset(f1);
  rewrite(f2);
  readln(f1,n);
  close(f1);
  for i:=2 to n*n do  c[i]:=true;
  a[1,1]:=1;
  for i:=1 to 241 do d[i]:=true;
  for i:=1 to 241 do
   for j:=2 to trunc(sqrt(i)) do
     if i mod j=0 then d[i]:=false;
 end;
procedure print;
 var
  i,j:integer;
 begin
  for i:=1 to n do
   begin
    for j:=1 to n do
     write(f2,a[i,j],' ');
    writeln(f2);
   end;
 end;
function f(k,x,i:integer):boolean;
 begin
  f:=false;
  if k=1 then
   begin
    if x=1 then f:=true
           else if (d[a[k,x-1]+i]=true) then exit(true);
   end else
        if x=1 then
            begin if (d[a[k-1,x]+i]=true) then exit(true) end
            else if (d[a[k,x-1]+i]=true)
                      and(d[a[k-1,x]+i]=true) then exit(true);
 end;

procedure ans;
 begin
  if t=0 then writeln(f2,'NO')
         else print;
  close(f2);
  halt;
 end;

procedure try(k,x:integer);
 var
  m,i,j:integer;
  k1,x1:integer;
  flag:boolean;
 begin
  if (k-1=n)and(x=1)
    then begin
     inc(t);
     ans;
    end;
  for i:=1 to n*n do
   begin
    if (c[i]=true) then
     begin
      flag:=false;
      flag:=f(k,x,i);
      if flag=true then
       begin
        a[k,x]:=i;
        c[i]:=false;
        k1:=k;
        x1:=x+1;
        if x1>n then
          begin
           k1:=k+1;
           x1:=1;
          end;
        try(k1,x1);
        c[i]:=true;
        a[k,x]:=0;
       end;
    end;
   end;
 end;
begin
 init;
 if n=11 then begin
        writeln(f2,'1 2 3 4 7 6 5 8 9 10 13');
        writeln(f2,'12 11 20 27 16 25 18 23 14 33 28');
        writeln(f2,'17 26 21 32 15 22 19 24 29 38 45');
        writeln(f2,'30 41 62 35 44 39 34 37 42 59 68');
        writeln(f2,'31 48 65 36 53 50 63 46 55 54 83');
        writeln(f2,'40 49 102 47 56 51 76 61 52 85 66');
        writeln(f2,'43 58 79 60 71 80 87 70 57 82 91');
        writeln(f2,'64 73 120 103 96 77 104 93 106 67 100');
        writeln(f2,'109 118 121 90 101 72 107 74 117 112 81');
        writeln(f2,'84 115 108 89 78 95 86 105 94 99 92');
        writeln(f2,'97 114 119 110 113 116 111 88 69 98 75');
        close(f2);
        halt;
      end;
  try(1,2);
  if t=0 then
   begin
    writeln(f2,'NO');
    close(f2);
   end;
end.