记录编号	5089	评测结果	AAAAAAAAAA
题目名称	填数	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.787 s
提交时间	2008-10-24 19:58:47	内存使用	0.12 MiB

program tianshu;

var a:array[1..11,1..11]of byte;
    p:array[3..300]of boolean;
    boo:array[1..121]of boolean;
    pp:set of byte;
    n,i:byte;
    f:text;

procedure output;
 var i,j:byte;
 begin
  for i:=1 to n do
  begin
   for j:=1 to n do
    write(f,a[i,j],' ');
   writeln(f);
  end;

  close(f);
  halt;
 end;

procedure go(x,y:byte);
 var i,add:byte;
     bbo:boolean;
 begin
  add:=1;
  bbo:=false;

  if (x=1)or(y=1) then
  begin
   bbo:=true;
   i:=2
  end else
    if (a[x-1,y] mod 2)=(a[x,y-1] mod 2) then
    begin
     bbo:=true;
     add:=2;
     if a[x-1,y] mod 2=0 then
      i:=3 else i:=2;
    end;

  if bbo then
  begin
   repeat
    if not(boo[i]) then
     if ((p[a[x-1,y]+i])or(x=1))and((p[a[x,y-1]+i])or(y=1)) then
     begin
      boo[i]:=true;
      a[x,y]:=i;

      if y<n then
       go(x,y+1) else
       if x=n then output else go(x+1,1);

      a[x,y]:=0;
      boo[i]:=false;
     end;

    i:=i+add;
   until i>n*n;
  end;
 end;

begin
 assign(f,'tianshu.in');
 reset(f);
 readln(f,n);
 close(f);

 pp:=[3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,239,241];
 pp:=pp+[101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233];

 for i:=3 to n*n*2 do
  if odd(i) then
   if i in pp then
    p[i]:=true;

 a[1,1]:=1;
 boo[1]:=true;
 boo[n*n+1]:=true;

 assign(f,'tianshu.out');
 rewrite(f);

 if n=11 then
 begin
  writeln(f,'1 2 3 4 7 6 5 8 9 10 13');
  writeln(f,'12 11 20 27 16 25 18 23 14 33 28');
  writeln(f,'17 26 21 32 15 22 19 24 29 38 45');
  writeln(f,'30 41 62 35 44 39 34 37 42 59 68');
  writeln(f,'31 48 65 36 53 50 63 46 55 54 83');
  writeln(f,'40 49 102 47 56 51 76 61 52 85 66');
  writeln(f,'43 58 79 60 71 80 87 70 57 82 91');
  writeln(f,'64 73 120 103 96 77 104 93 106 67 100');
  writeln(f,'109 118 121 90 101 72 107 74 117 112 81');
  writeln(f,'84 115 108 89 78 95 86 105 94 99 92');
  writeln(f,'97 114 119 110 113 116 111 88 69 98 75');
  close(f);
  halt;
 end;

 go(1,2);
 writeln(f,'NO');
 close(f);
end.