/*
 * "Grundkurs Programmieren in Java - Band 1 (4. Auflage, 2007)"
 * 2001-2007, Carl Hanser Verlag
 * Loesungsvorschlag zu Aufgabe 12.3 (Version 4.0)
 * (c) 2001-2007 D. Ratz, J. Scheffler, D. Seese, J. Wiesenberger
 *
 * Berechnet alle 92 Loesungen des Achtdamenproblems und speichert sie in
 * dem 3-dimensionalen boolean-Array 'loesung'. Um die Berechnung zu starten,
 * ist die Methode 'invoke' aufzurufen
 *
 */

public class AchtdamenEngine {

  public static boolean[][][] loesung = new boolean[92][][]; // fuer alle 92 Loesungen
  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 );   // teste die folgenden Spalten
    }

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

    return false;
  }



  // schreibt eine Loesung in das boolean-Feld 'loesung'
  public static void ausgabe(int[] brett) {
    boolean[][] feld;

    feld = new boolean[8][8];

    for (int i=0; i < 8; i++)       // Anzahl der Zeilen
      for (int j=0; j < 8; j++)      // Anzahl der Spalten
        if (i == brett[j])
          feld[i][j] = true;
        else
          feld[i][j] = false;

    loesung[anzLoesungen] = feld; // aktuelle Loesung im globalen feld speichern
    anzLoesungen++;
  }


  // startet Berechnung
  public static void invoke () {
    int[] feld = {0,0,0,0,0,0,0,0}; // Initialisiere das Spielfeld
    setze(feld,0); // Starte die Suche am linken Rand
  }


}