/*
Datei............: Aufg0733.java
Projekt..........: Einführung in die Java-Programmierung
Erstellt.........: 04.11.97, Guido Krüger
Geändert.........: --
Aufgabe..........: Musterlösung zu Aufgabe 07.33
Kommentare.......:

Das Programm zur Lösung des 8-Damen-Problems verwendet ein 
Verfahren, daß als "Backtracking" bezeichnet wird. Die Lösung
wird dabei schrittweise angenähert, bis das Ziel erreicht ist,
oder bis es nicht mehr weitergeht. Steckt das Programm in einer 
Sackgasse, wird der letzte Schritt rückgängig gemacht und eine 
andere Variante ausprobiert.

Wichtig für das Verständnis des Algorithmus ist die Kenntnis
der Darstellung des Spielplans. Dieser wird als eindimensionales
Array dargestellt, bei dem das n-te Arrayelement die Plazierung
der Dame in Spalte n angibt. Der Inhalt des Arrayelements ist
genau die Nummer der Zeile, in der die Dame steht. Die Damen
werden dabei grundsätzlich von links nach rechts auf dem Brett
plaziert, die variable anzdamen gibt an, wieviele Damen gerade
auf dem Brett sind.
*/
import java.io.*;

public class Aufg0733
{
  public static void main(String args[])
  {
	AchtDamenProblem problem = new AchtDamenProblem();
	problem.loese();
  }
}

class AchtDamenProblem
{
  //Konstanten
  final int MAXSIZE = 8;

  //Instanzmerkmale
  int brett[];
  int anzdamen;

  /**
   * Der Konstruktor erzeugt lediglich das (leere) Spielfeld.
   */
  public AchtDamenProblem()
  {
	brett = new int[MAXSIZE];
  }

  /**
   * Diese Methode löst das 8-Damen-Problem. Sie leert zunächst das
   * Brett und plaziert dann schrittweise von links nach rechts
   * die Damen auf dem Spielfeld. Ist eine gültige Stellung erreicht,
   * wird die nächste Dame in der nächsten Spalte plaziert, andernfalls
   * wird die letzte Dame eine Zeile nach unten gesetzt. Steht die
   * letzte Dame in der letzten Zeile, so setzt das Backtracking ein
   * und es werden (von rechts beginnend) soviele Damen vom Feld 
   * entfernt, bis die ganz rechts stehende Dame nach unten bewegt
   * werden kann.
   */
  public void loese()
  {
	boolean lOK;
	int anzloesungen = 0;

	anzdamen = 0;
	lOK = true;
	int anzsteps = 0;
	while (plaziereDame(lOK)) {
	  ++anzsteps;
	  lOK = gueltigeStellung();
	  if (lOK && anzdamen == MAXSIZE) {
		System.out.println(
		  "Lösung " + (++anzloesungen) + " (nach " + 
           anzsteps + " Schritten):"
        );
		druckeStellung();
		lOK = false;
	  }
	}
  }

  /**
   * Setzt die nächste Dame. Falls lNeueSpalte auf true steht, wird
   * die Dame in der nächsten freien Spalte in die erste Zeile
   * gesetzt. Andernfalls wird die ganz rechts stehende Dame eine
   * Zeile nach unten geschoben. Ist dies nicht möglich (weil sie
   * schon in der letzten Zeile steht), so setzt das oben beschriebene
   * Backtracking ein. Gibt es keine weiteren Züge (weil die Dame der
   * ersten Spalte in der letzten Zeile steht), so gibt die Methode
   * false zurück und zeigt so das Ende der Backtracking-Möglichkeiten an.
   */
  private boolean plaziereDame(boolean lNeueSpalte)
  {
	boolean lRet = true;
	if (lNeueSpalte) {
	  brett[anzdamen++] = 0;
	} else {
	  while (anzdamen > 1 && brett[anzdamen - 1] == MAXSIZE - 1) {
		--anzdamen;
	  }
	  if (anzdamen == 1 && brett[0] == MAXSIZE - 1) {
		System.out.println("Keine weiteren Stellungen -> Abbruch!");
		lRet = false;
	  } else {
		++brett[anzdamen - 1];
	  }
	}
	return lRet;
  }

  /**
   * Überprüft, ob die ganz rechts stehende Dame mit einer der weiter
   * links stehenden Damen des Spielfeldes kollidiert. Ist dies der
   * Fall, gibt die Methode false zurück, andernfalls liefert sie true.
   */
  private boolean gueltigeStellung()
  {
	int zeile1;
	int zeile2 = brett[anzdamen - 1];
	for (int i = anzdamen - 2; i >= 0; --i) {
	  zeile1 = brett[i];
	  if (zeile1 == zeile2) {
		return false;
	  }
	  if (anzdamen - 1 - i == Math.abs(zeile2 - zeile1)) {
		return false;
	  }
	}
	return true;
  }

  /**
   * Gibt den aktuellen Spielplan mit den darauf plazierten Damen aus.
   */
  private void druckeStellung()
  {
	for (int i = 0; i < MAXSIZE; ++i) {
	  for (int j = 0; j < MAXSIZE; ++j) {
		if (j < anzdamen && brett[j] == i) {
		  System.out.print("X");
		} else {
        System.out.print("-");
		}
	  }
	  System.out.println();
	}
	System.out.println();
  }
}