n-Damen-Problem

[Startseite]


Vorwort ] Voraussetzungen ] JAVA ] Implementierung von Klassen ] Erste Programme ] Klassenbibliothek ] Installation ] Applets ] Mehr JAVA ] Inside stiftUndCo ] Beispiele ] Downloads ]
Programmgesteuertes Zeichnen
Freihandzeichnen
Das Ballprojekt
Autorennen
Weitere Beispiele
Der Zug
n-Damen-Problem
Drucken mit stiftUndCo
Türme von Hanoi
Das n-Damen-Problem

Das n-Damen-Problem ist ein klassisches Beispiel für Backtracking. Das folgende Applet zeigt alle Lösungen für das n-Damen-Problem für n= 4..10.

Quelltext:

import stiftUndCo.*;


public class NDamenApplet extends EreignisApplet
{

	private int[] plazierung; 
	private int anzahlDamen,maxDamen;
	private int anzahlLösungen;
	private boolean suchmodus,weitererlaubt;
	
	public void initApplet()
	{

		int i;
		suchmodus=false;
		weitererlaubt=true;
		maxDamen=10;
		plazierung = new int[maxDamen+1];
		
		for ( i=1; i<= maxDamen;i=i+1)
		{
			plazierung[i]=0;
		} // Ende for	
		anzahlDamen=3;
		anzahlLösungen=0;
		stift().bewegeBis(10,15);
		stift().schreibe("Das n-Damen-Problem");
		stift().bewegeBis(10,30);
		stift().schreibe("n=4,...,"+maxDamen);

		this.stift().bewegeBis(10,180);
		this.stift().normal();
		this.stift().schreibe("Weiter mit Mausklick");	
	} // Ende Konstruktor NDamen

	public void bearbeiteMausDruck(int x, int y)
	{
		if (weitererlaubt)
		{
			this.stift().bewegeBis(10,45);
			this.stift().radiere();
			this.stift().schreibe("n="+anzahlDamen+" Lösung Nr.:"+anzahlLösungen);
			if (anzahlDamen<maxDamen) 
			{
				anzahlDamen++;
			
			}
			this.gitter();
			anzahlLösungen=0;
			suchmodus=true;
			weitererlaubt=false;
		}
			
	} // Ende bearbeiteMausDruck

	public void zeichneDame(int i, int j)
	{
		this.stift().bewegeBis(10*i,10*j+50);
		this.stift().normal();
		this.stift().zeichneKreis(4);
	} // Ende zeichneDame

	public void loescheDame(int i, int j)
	{
		this.stift().bewegeBis(10*i,10*j+50);
		this.stift().radiere();
		this.stift().zeichneKreis(4);
	}// Ende loescheDame

	private void gitter()
	{ int i;
		for (i=0; i<= anzahlDamen; i=i+1)
		{
			this.stift().normal();
			this.stift().hoch();
			this.stift().bewegeBis(10*i+5,55);
			this.stift().runter();
			this.stift().bewegeBis(10*i+5,55+anzahlDamen*10);
			this.stift().hoch();

		} // Ende for
		for (i=0; i<= anzahlDamen; i=i+1)
		{
			this.stift().normal();
			this.stift().hoch();
			this.stift().bewegeBis(5,10*i+55);
			this.stift().runter();
			this.stift().bewegeBis(anzahlDamen*10+5,10*i+55);
			this.stift().hoch();

		} // Ende for
	} // Ende gitter


	public void bearbeiteAndereEreignisse()
	{
		if (suchmodus) { 
			this.stift().bewegeBis(10,180);
			this.stift().radiere();
			this.stift().schreibe("Weiter mit Mausklick");			
			suchmodus=false;
			this.such(1);
			weitererlaubt=true;
			if (anzahlDamen<maxDamen) 
			{
				this.stift().bewegeBis(10,180);
				this.stift().normal();
				this.stift().schreibe("Weiter mit Mausklick");			
			}

		}
	}
	/* Das eigentliche Backtracking */
	private void such(int i)
	{   int j;
		for (j=1;j<=anzahlDamen;j=j+1)
		{
			if (this.passt(i,j))
			{
				plazierung[i]=j;
				this.zeichneDame(i,j);

				if (i==anzahlDamen)  // Lösung ist gefunden
				{
					this.stift().bewegeBis(10,45);
					this.stift().radiere();
					this.stift().schreibe(("n="+anzahlDamen+" Lösung Nr.:"+anzahlLösungen));
					
					anzahlLösungen=anzahlLösungen+1;
					this.stift().bewegeBis(10,45);
					this.stift().normal();
					this.stift().schreibe(("n="+anzahlDamen+" Lösung Nr.:"+anzahlLösungen));
					if (anzahlDamen <= 8) {Hilfe.warte(500);}
					} 
				else 
				{ 
					such(i+1); // weiter mit der nächsten Dame
				} // Ende if

				this.loescheDame(i,j);
			} // Ende if
		} // Ende for
		
	} // Ende such



	private boolean passt(int i, int j)
	{
		boolean hilf, ende;
		int k;
		hilf=true;
		ende=false;
		k=1;		
		
		if (i==1) 
		{
			return true;
		} // Ende if
		// paßt die i-Dame auf Zeile j ?
		while (hilf && ! ende)
		{
			hilf = (plazierung[k]!=j) ;
			k=k+1;
			ende = (k==i);
		} // Ende while
		// Überprüfung der absteigenden Diagonalen
		ende=false;
		k=1;
		while (hilf && ! ende)
		{
			hilf = (plazierung[k]-k!=j-i) ;
			k=k+1;
			ende = (k==i);
		} // Ende while
		// Überprüfung der aufsteigenden Diagonalen
		ende=false;
		k=1;
		while (hilf && ! ende)
		{
			hilf = (plazierung[k]+k!=j+i) ;
			k=k+1;
			ende = (k==i);
		} // Ende while
		return hilf;
	}


} // Ende NDamen

 


Seitenanfang

© Georg Dick