记录编号	1802	评测结果	AAAAAAAAAA
题目名称	[USACO 1.5.4] 跳棋的挑战	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	96.000 s
提交时间	2008-09-08 19:50:18	内存使用	0.00 MiB

{
PROB:checker
LANG:PASCAL
}

program cch(input,output,f1,f2);
var
 f1,f2:text;
 n,ans,sum,q:longint;
 a:array[1..20] of longint;

procedure test(row,ld,rd:longint);
var
 pos,p:longint;
begin
 if row<>ans then
  begin
   pos:=ans and not(row or ld or rd);
   while pos<>0 do
    begin
     p:=pos and -pos;
     pos:=pos-p;
     test(row+p,(ld+p)shl 1,(rd+p) shr 1);
    end;
  end
 else inc(sum);
end;

procedure solve(k:integer);
var
 i,j:integer;
 flag:boolean;
begin
 if k=n+1 then begin
  inc(q);
  if q<=3 then begin
   for j:=1 to n-1 do write(f2,a[j],' ');
   writeln(f2,a[n]);
  end;
  if q=3 then begin
   writeln(f2,sum);
   close(f1); close(f2);
   halt;
  end;
  exit;
 end;
 for i:=1 to n do
  begin
   flag:=true;
   for j:=1 to k-1 do
    if (a[j]=i)or(abs(a[j]-i)=abs(j-k)) then flag:=false;
   if flag then begin
    a[k]:=i;
    solve(k+1);
   end;
  end;
end;
begin
 assign(f1,'checker.in');
 assign(f2,'checker.out');
 reset(f1);
 rewrite(f2);
 readln(f1,n);
 ans:=(1 shl n)-1;
 sum:=0;
 test(0,0,0);
 q:=0;
 solve(1);
 close(f1);
 close(f2);
end.