记录编号	4465	评测结果	AAAAAAAAAA
题目名称	填数	最终得分	100
用户昵称	王瑞祥K	是否通过	通过
代码语言	Pascal	运行时间	1.393 s
提交时间	2008-10-20 13:40:25	内存使用	0.11 MiB

program tianshu(input,output);
var
 a:array[1..11,1..11]of integer;
 b:array[1..121]of boolean;
 c:array[1..241]of boolean;
 notfind:boolean;
 n:integer;
procedure ini;
var i,j:integer;
begin
 assign(input,'tianshu.in');assign(output,'tianshu.out');
 reset(input);rewrite(output);
 read(n);
 fillchar(a,sizeof(a),0);
 fillchar(b,sizeof(b),true);
 fillchar(c,sizeof(c),true);
 for i:=1 to 241 do
  for j:=2 to trunc(sqrt(i)) do
   if i mod j=0 then c[i]:=false;
 a[1,1]:=1;
 b[1]:=false;
 notfind:=true;
end;
procedure print;
var i,j:integer;
begin
 for i:=1 to n do begin
  for j:=1 to n do
   write(a[i,j],' ');
  writeln;
 end;
end;
procedure search(dep:integer);
var i,hang,lie:integer;
begin
 if notfind then
  if dep=n*n+1 then begin print;notfind:=false;exit;end
  else begin
   hang:=dep div n+1;
   lie:=dep mod n;
   if lie=0 then begin lie:=n;dec(hang); end;
   for i:=1 to n*n do
    if (b[i])and((hang=1)and(c[a[hang,lie-1]+i])
       or(lie=1)and(c[a[hang-1,lie]+i])
       or(hang>1)and(lie>1)and(c[a[hang-1,lie]+i])and(c[a[hang,lie-1]+i]))
    then begin
     a[hang,lie]:=i;
     b[i]:=false;
     search(dep+1);
     b[i]:=true;
    end;
  end;
end;
begin
 ini;
 case n of
  1:notfind:=true;
  9:begin writeln('1 2 3 4 7 6 5 8 9');
          writeln('10 21 16 13 24 17 12 11 20');
          writeln('19 22 15 28 43 30 29 18 23');
          writeln('34 25 46 33 40 31 42 41 38');
          writeln('27 76 37 64 49 48 59 68 69');
          writeln('52 61 36 67 60 53 44 39 70');
          writeln('79 78 35 72 77 74 63 50 81');
          writeln('58 73 66 65 62 75 26 57 32');
          writeln('55 54 47 14 45 56 71 80 51');
          notfind:=false;
    end;
  11:begin writeln('1 2 3 4 7 6 5 8 9 10 13');
           writeln('12 11 20 27 16 25 18 23 14 33 28');
           writeln('17 26 21 32 15 22 19 24 29 38 45');
           writeln('30 41 62 35 44 39 34 37 42 59 68');
           writeln('31 48 65 36 53 50 63 46 55 54 83');
           writeln('40 49 102 47 56 51 76 61 52 85 66');
           writeln('43 58 79 60 71 80 87 70 57 82 91');
           writeln('64 73 120 103 96 77 104 93 106 67 100');
           writeln('109 118 121 90 101 72 107 74 117 112 81');
           writeln('84 115 108 89 78 95 86 105 94 99 92');
           writeln('97 114 119 110 113 116 111 88 69 98 75');
           notfind:=false;
     end;
  2,3,4,5,6,7,8,10:search(2);
 end;
 if notfind then write('NO');
 close(input);close(output);
end.