// Achtdamenproblem
// Idee: Spalten sukzessive durchprobieren
#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
  int n, s, i, j, k;
  int D[8];	/* Feld von 0 bis 7 für Damenposition:
  		   Vorteil: bessere Berechnung als 2-dim. Feld
		   Index = Spaltenposition der Dame (0..7)
		   Elementwert = Zeilenposition der Dame (1..8)
  		*/

  cout << "Lösung des Achtdamenproblems\n\n";
  n = 0;	// Anzahl der bisher gefundenen Lösungen

  D[0] = 1;	// erste Dame auf Position 1 setzen
  // restliche Spalten besitzen noch keine Damen und 
  // werden entsprechend initialisiert mit 0
  for (k=1; k<8; k++)  
  	D[k] = 0;

  s = 1;	// Spaltenzähler auf 1 (2.Spalte)
  do {
  	// Dame eine Zeile innerhalb Spalte s verschieben
	D[s]++;	
	// nachfolgende Spalten alle leeren, um immer nach 
	// neuer Variante zu suchen (Rückwärtsgehen ermöglichen)
	for (k=s+1; k<8; k++)  
		D[k] = 0;
	// wenn Dame nicht mehr auf das Feld passt...
	if ( D[s] == 9 )    
		s--;	// ... dann gehe einen Schritt zurück
	// andernfalls
	else {
		// Kollisionstest mit allen bisher gesetzten Damen
		// in aktueller Probevariante: Damen D[0] bis D[s-1]
	     	// k gibt an, bis zu welcher Spalte alles in Ordnung ist
	     	for (k=0; k<s; k++) 
			// wenn zwei Damen in selber Zeile oder
			// wenn zwei Damen auf einer Diagonalen,
			// dann gibt es eine Kollision
			if (( D[k]==D[s] ) || (abs(D[k]-D[s]) == abs(k-s)))   
				break;
	     	// wenn keine Kollision,...
	     	if (k==s)  {
			// gib Zwischenlösungen aus
			cout << "--- ";
			for (i=0; i<8; i++) 
					cout << D[i];
			cout << endl;
			s++;	// ... dann gehe eine Spalte weiter
			// wenn letzte Spalte erreicht,
			// ist aktuelle Variante gültig
			if ( s == 8 ) {
				// Zähler gültiger Lösungen erhöhen
				n++;	
				cout << n << '\t';
				// Ausgeben aller Besetzungen
				for (i=0; i<8; i++) 
					cout << D[i];
				cout << endl;
				// eine Spalte zurück gehen
				s--;
			}
	        }
	}
  }
  // solange wiederholen, bis Dame in erster Spalte überläuft
  while( D[0] < 9 ); 
  
  return 0;
}