from functools import reduce;

def sindBedroht(zelle1,zelle2):
   (i,k)=zelle1;
   (m,n)=zelle2;
   return (k==n)or(i+k==m+n)or(i-k==m-n)or(i==m);
# end def

def istVertraeglichMit(damenListe,zelle):
   if damenListe==[]: return True;
   istSicher=[not sindBedroht(dame,zelle)
                  for dame in damenListe];
   return reduce(lambda x,y: x and y, istSicher);
# end def

def nDamenProblem(anzahlDamen):
   # Felderzahl=anzahlDamen*anzahlDamen
   def setzeDame(reihe):
       if reihe==0: return [[]];
       return([loesung+[(reihe,spalte)]
                 for loesung in setzeDame(reihe-1)
                 for spalte in range(1,anzahlDamen+1)
                 if istVertraeglichMit(loesung,(reihe,spalte))]);
   # end def
   return setzeDame(reihe=anzahlDamen);
# end def

#------------------------------------------------------------------------------#
#------------------------------------------------------------------------------#

if __name__ == '__main__':
   print('\n# Beginning Test ...\n');

#------------------------------------------------------------------------------#

   damen=[];
   istSicher=istVertraeglichMit(damen,(1,1));
   assert istSicher;
   damen=[(1,8),(2,4),(3,1),(4,3),(6,2),(7,7),(8,5)];
   istSicher=istVertraeglichMit(damen,(5,6));
   assert istSicher;
   istSicher=istVertraeglichMit(damen,(5,7));
   assert not istSicher;
   istSicher=istVertraeglichMit(damen,(5,1));
   assert not istSicher;
   istSicher=istVertraeglichMit(damen,(6,6));
   assert not istSicher;

   bedroht=sindBedroht((1,1),(1,8));
   assert bedroht;

   if False:
       nMax=13;
       for n in range(1,nMax):
           loesung=nDamenProblem(n);
           # print('\n',loesung,'\n\nN: ',n,' | Anzahl: ',len(loesung),'\n');
           print('N: ',n,' | Anzahl: ',len(loesung));

   if True:
       N=5;
       loesung=nDamenProblem(N);
       print('\n',loesung,'\n\nN: ',N,' | Anzahl: ',len(loesung),'\n');
   
#------------------------------------------------------------------------------#
#------------------------------------------------------------------------------#
   print('\n# Finished Test.\n');
# end if main

##    # Beginning Test ...
##
##    N:  1  | Anzahl:  1
##    N:  2  | Anzahl:  0
##    N:  3  | Anzahl:  0
##    N:  4  | Anzahl:  2
##    N:  5  | Anzahl:  10
##    N:  6  | Anzahl:  4
##    N:  7  | Anzahl:  40
##    N:  8  | Anzahl:  92
##    N:  9  | Anzahl:  352
##    N:  10  | Anzahl:  724
##    N:  11  | Anzahl:  2680
##    N:  12  | Anzahl:  14200
##
##    # Finished Test.