Hallo liebe Community. Bin neu hier, also erstmal Gruß an alle
Ich habe folgendes Problem:
Zum Damen-Problem muss ich eine Klasse schreiben und dazu eine statische Methode angeben, die die Anzahl der möglichen Lösungen mit Hilfe von Backtracking ermittelt und ausgibt.
Ich habe das wie folgt gelöstQuelltext siehe unten)
Problem1: Ich weiss, dass der Algorithmus doppelte Einträge nicht herausfiltert, denke aber das ich das noch hinbekommen werde.
Problem2 ist viel wichtiger: Mein Programm terminiert nicht! Ich habe mir meinen Quelltext schon 20 Mal durchgesehen, etliche Fehler behoben und nun stehe ich auf dem Schlauch???:L;(
Ich sitze seit geschlagenen 8 std dran. Bitte seid so nett und helft mir! Danke
Wenn ich etwas schlecht kommentiert haben sollte tut mir das Leid. Bin noch ein Anfänger.
Ich habe folgendes Problem:
Zum Damen-Problem muss ich eine Klasse schreiben und dazu eine statische Methode angeben, die die Anzahl der möglichen Lösungen mit Hilfe von Backtracking ermittelt und ausgibt.
Ich habe das wie folgt gelöst
Quelltext siehe unten)Problem1: Ich weiss, dass der Algorithmus doppelte Einträge nicht herausfiltert, denke aber das ich das noch hinbekommen werde.
Problem2 ist viel wichtiger: Mein Programm terminiert nicht! Ich habe mir meinen Quelltext schon 20 Mal durchgesehen, etliche Fehler behoben und nun stehe ich auf dem Schlauch???:L;(
Ich sitze seit geschlagenen 8 std dran. Bitte seid so nett und helft mir! Danke
Wenn ich etwas schlecht kommentiert haben sollte tut mir das Leid. Bin noch ein Anfänger.
Java:
import java.awt.Point;
import java.util.ArrayList;
public class checkers {
public boolean[][] brett;
//Konstruktor
public checkers (int anz)
{
brett = new boolean[anz][anz];
}
//markiert die Stellen auf dem Brett mit true, wo andere durch die Dame im übergebenen Punkt Damen gefährdet sind
public void besetze(Point D)
{
//besetzt die Zeilen des Schachbretts
for (int i = 0; i < this.brett.length; i++)
{
this.brett[i][D.x]=true;
}
//besetzt die Spalten des Schachbretts
for (int i = 0; i < this.brett.length; i++)
{
this.brett[D.y][i] = true;
}
//besetzt die 1. Diagonale des Schachbretts
Point X = new Point();
X.x = D.x;
X.y = D.y;
//geht die Diagonale "zurück" bis zur 0. Spalte oder 0. Zeile
while (X.x>0 && X.y>0)
{
X.x -= 1;
X.y -= 1;
}
//besetzt die Diagonale
while (X.x < this.brett.length - 1 && X.y < this.brett.length - 1)
{
this.brett[X.x][X.y]=true;
X.x += 1;
X.y += 1;
this.brett[X.x][X.y]=true;
}
//besetzt die 2. Diagonale des Schachbretts
//geht die Diagonale "zurück" bis zur 0. Spalte oder 8. Zeile
Point Y = new Point();
Y.x = D.x;
Y.y = D.y;
while (Y.x > 0 && Y.y < this.brett.length - 1)
{
Y.x -= 1;
Y.y += 1;
}
//besetzt die Diagonale
while (Y.x < this.brett.length - 1 && Y.y > 0)
{
this.brett[Y.x][Y.y] = true;
Y.x += 1;
Y.y -= 1;
this.brett[Y.x][Y.y] = true;
}
}
//Methode, die die Position des nächsten Kästchens des übergebenen Punktes bestimmt
public Point moveNext(Point p)
{
if(p.x < this.brett.length - 1 && p.y <= this.brett.length - 1)
{
p.x = p.x + 1;
}
if(p.x == this.brett.length - 1 && p.y < this.brett.length - 1)
{
p.x = 0;
p.y = p.y + 1;
}
return p;
}
public ArrayList<ArrayList<Point>> loese()
{
ArrayList<ArrayList<Point>> lmenge = new ArrayList<ArrayList<Point>>();
ArrayList<Point> l = new ArrayList<Point>();
Point Null = new Point(0,0);
Point Punkt = new Point(0,0);
Point Start = new Point(0,0);
Point Nullpunkt = new Point(0,0);
for (int i = 1; i <= this.brett.length * this.brett.length; i++)
{
//Methode zur Ermittlung einer Lösung
//führt die Schleife für n Damen durch
for (int iy = 0; i < this.brett.length; iy++)
{
//Wenn die Stelle noch frei, besetze sie und schreibe die Koordinaten in eine Liste
if (this.brett[Start.x][Start.y]==false)
{
besetze(Start);
l.add(Start);
}
//gehe bis zur nächsten freien Stelle
for (int j = 1; j < this.brett.length * this.brett.length; j++)
{
if(this.brett[Null.x][Null.y] == true)
{
moveNext(Null);
}
}
Start.x = Null.x;
Start.y = Null.y;
Null.x = 0;
Null.y = 0;
}
if(l.size() == this.brett.length)lmenge.add(l);
l.clear();
//setzt das komplette Schachbrett zurück auf leer (unbesetzt)
for (int j = 1; j < (this.brett.length) * (this.brett.length); j++)
{
this.brett[Nullpunkt.x][Nullpunkt.y] = false;
moveNext(Nullpunkt);
}
Nullpunkt.x = 0;
Nullpunkt.y = 0;
moveNext(Punkt).x = Start.x;
moveNext(Punkt).y = Start.y;
}
return lmenge;
}
public static int numberSolutions(int n)
{
checkers test = new checkers(n);
return test.loese().size();
}
public static void main(String[] args)
{
System.out.println(numberSolutions(3));
}
}
