PROGRAM	nqueen(input,output);
CONST
  nmax=100;
VAR
  x:ARRAY[1..nmax] OF integer;     {存放每个皇后位置的数组}
  a:ARRAY[1..nmax] OF boolean;     {用于表示该列是否可放置的数组}
  b:ARRAY[2..nmax*2] OF boolean;   {用于表示正对角线位置是否可放置的数组}
  c:ARRAY[-nmax..nmax] OF boolean; {用于表示反对角线位置是否可放置的数组}
  count,n:integer;
PROCEDURE print;
  VAR
    k:integer;
  BEGIN
    count:=count+1;
    FOR k:= 1 TO n DO
      write(x[k]:4);
    writeln;
  END;
PROCEDURE try(i:integer);
  VAR
    j:integer;
  BEGIN
    FOR j:= 1 TO n DO
      IF a[j] AND b[i+j] and c[i-j]   {只有当三个位置都没有冲突时才可放置}
         THEN BEGIN
               x[i]:=j;
               a[j]:=false;
               b[i+j]:=false;
               c[i-j]:=false;
               IF i<n                 {若n个皇后没有放满，则递归放下一个}
                  THEN try(i+1)
                  ELSE print;
                a[j]:=true;           {出栈时恢复状态}
                b[i+j]:=true;
                c[i-j]:=true;
               END{if}
   END;{try}
BEGIN{mian}
  assign(input,'nqueen.in');
  reset(input);
  assign(output,'nqueen.out');
  rewrite(output);
  readln(n);
  count:=0;
  fillchar(a,sizeof(a),true);
  fillchar(b,sizeof(b),true);
  fillchar(c,sizeof(c),true);
  try(1);
  writeln(count);
  close(input);
  close(output);
END.

//delphi/7188