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
|