//
// C++-programma om dames op schaakbord te zetten
// Opleiding Informatica, Universiteit Leiden
// Zie http://www.liacs.nl/home/kosters/pm/dam.html
//

#include <iostream>
using namespace std;

const int MAX = 20;  // grootte bord moet kleiner dan MAX zijn

bool geenaanval (int rij, int S[ ]) {
  // Geeft true precies dan als de dame in de rij-de rij
  // geen ruzie heeft met eerdere dames in S
  bool veilig = true; 
  int hulprij = 1;
  while ( veilig && ( hulprij < rij ) ) {
    veilig = ( ( S[rij] != S[hulprij] )  // verschillende kolom en diagonaal
             && ( S[rij] - S[hulprij] != rij - hulprij ) 
             && ( S[rij] - S[hulprij] != hulprij - rij ) );
    hulprij++; }  // while
  return veilig;
}  // geenaanval

void drukaf (int grootte, int S[ ]) {
  // Druk stand S op grootte bij grootte bord netjes af
  for ( int i = 1; i <= grootte; i++ )
    cout << S[i] << " ";  // kolomnummer van i-de dame
  cout << endl;
}  // drukaf

void zetdames (int grootte, int rij, int S[ ], int& teller) {
  // Tot en met rij-1 zijn reeds op grootte bij grootte bord goed dames gezet.
  // Ga nu verder, te beginnen op de rij-de rij; backtracking.
  // teller telt goede standen; voorbeeldaanroep: zetdames (8,1,S,teller);
  int kolom;
  if ( rij == grootte + 1 ) {
    drukaf (grootte,S);
    teller++; 
  }  // if
  else
    for ( kolom = 1; kolom <= grootte; kolom++ ) {
      S[rij] = kolom;
      if ( geenaanval (rij,S) )
        zetdames (grootte,rij+1,S,teller); 
    }  // for
}  // zetdames

int main ( ) {  
  int S[MAX]; 
  int grootte = 0; 
  int teller = 0;
  do {
    cout << "Geef grootte van het schaakbord ( < " << MAX << " ) .. ";
    cin >> grootte; 
  } while ( grootte >= MAX );
  zetdames (grootte,1,S,teller);
  cout << endl << "Aantal: " << teller << endl << endl;
  return 0;
}  // main