/*
 * "Grundkurs Programmieren in Java - Band 1 (4. Auflage, 2007)"
 * 2001-2007, Carl Hanser Verlag
 * Loesungsvorschlag zu Aufgabe 7.4 (Version 4.0)
 * (c) 2001-2007 D. Ratz, J. Scheffler, D. Seese, J. Wiesenberger
 *
 * Programm gibt _alle_ Lösungen des 'Achtdamenproblems'
 * zusaetzlich: Zaehler fuer Anzahl der gefundenen Loesungen
 *
 */

public class AchtdamenAlle {

  public static int anzLoesungen = 0;

  /** Testet, ob eine der Damen eine andere schlagen kann. */
  //  ----------------------------------------------------
  public static boolean bedroht(int[] brett, int spalte) {
    // Teste als Erstes, ob eine Dame in derselben Zeile steht
    for (int i=0; i < spalte; i++)
      if (brett[i] == brett[spalte])
        return true;

    // Teste nun, ob in der oberen Diagonale eine Dame steht
    for (int i = spalte-1, j = brett[spalte]-1; i >= 0; i--,j--)
      if (brett[i] == j)
        return true;

    // Teste, ob in der unteren Diagonale eine Dame steht
    for (int i = spalte-1, j = brett[spalte]+1; i >= 0; i--,j++)
      if (brett[i] == j)
        return true;

    // Wenn das Programm hier angekommen ist, steht die Dame "frei"
    return false;
  }


  /** Sucht rekursiv eine Loesung des Problems. */
  //  -----------------------------------------
  public static boolean setze(int[] brett, int spalte) {
    // Sind wir fertig?
    if (spalte == 8) {
      ausgabe(brett);
      return true;
    }

    // Suche die richtige Position fuer die neue Dame
    for (int i=0; i < 8; i++) {
      brett[spalte] = i;         // Probiere jede Stelle aus
      if (bedroht(brett,spalte)) // Falls die Dame nicht frei steht
        continue; // versuche es an der naechsten Stelle
      boolean success = // moeglicher Kandidat gefunden? --
        setze(brett, spalte+1 /* ++spalte */ );   // teste die folgenden Spalten

        /*
        if (success)               // falls es geklappt hat
          return true;
          */
    }

    // Wenn das Programm hier angekommen ist,
    // stecken wir in einer Sackgasse

    return false;
  }



  /** Gibt das Schachbrett auf dem Bildschirm aus. */
  //  -------------------------------------------
  public static void ausgabe(int[] brett) {
    for (int i=0; i < 8; i++) {      // Anzahl der Zeilen
      for (int j=0; j < 8; j++)      // Anzahl der Spalten
        System.out.print("|" + ((i == brett[j]) ? 'D' : ' '));
      System.out.println("|");       // Zeilenende
    }
    System.out.println();
    anzLoesungen++;
  }


  /** Initialisiert das Schachbrett und
      ruft die Methode "setze" auf */
  //  ---------------------------------
  public static void main(String[] args) {
    int[] feld = {0,0,0,0,0,0,0,0}; // Initialisiere das Spielfeld
    setze(feld,0); // Starte die Suche am linken Rand

    System.out.println( "Anzahl der gefundenen Loesungen: " + anzLoesungen );
  }
}