8 Damen Problem (Backtracking)

[alphatier]

Hallo liebe Java - Community

ich lerne für die Algorithmen Klausur und übe derzeit Backtracking Algorithmen. Als Übungsaufgabe habe ich versucht das 8 Damen Problem zu lösen, jedoch leider ohne Erfolg.

Hier ist der Algorithmus:

public class DamenProblem {
	
	public void clear(int [][]feld){
		for (int i=0; i<8; i++){
			for (int j=0; j<8; j++){
				feld[i][j]=0;
			}
		}
	}
	//Hauptmethode
	public int [] [] loese(int zeile, int spalte){
		int [][] feld = new int [8][8];
		clear(feld);
                //setzt die Startposition
		feld[zeile][spalte]=1;
		
		loeseProblem(feld,zeile+1,spalte+1,0);
		
		return feld;
	}
	
        //Rekursion 
        //cnt ist der counter der dafür sorgt das die methode aufhört falls kein geeignet platz in der spalte gefunden wird
	public void loeseProblem(int [][]feld,int zeile, int spalte, int cnt){
		zeile=zeile%8;
		spalte=spalte%8;

		//Falls Position ist günstig
		if(istOk(feld,zeile,spalte)){
			feld[zeile][spalte]=1;
			//Falls ergebnis erzielt
			if(spalte==7){return;}
			else{
				loeseProblem(feld, zeile+1, spalte+1, 1);
				//Schritt zurück
				feld[zeile][spalte]=0;
				//suche andere pos in spalte
				loeseProblem(feld, zeile+1, spalte, cnt+1);
			}
		}
		else{
                        //brich ab und gib nichts zurück
			if(cnt==8){}
			else{
				loeseProblem(feld, zeile+1, spalte, cnt+1);
			}
		}
	}

	private boolean istOk(int [][] feld,int zeile,int spalte){
		//Durchlaufe nach vorne
		for (int i=1;i<8;i++){
			if(feld[zeile][(spalte+i)%8]==1){
				return false;
			}
		}
		//Durchlaufe Diagonal
		//Unten Rechts
		for (int i=1; zeile+i<8 && spalte+i<8; i++){
			if(feld[zeile+i][(spalte+i)]==1){
				return false;
			}
		}
		//Oben Links
		for (int i=1; zeile-i>=0 && spalte-i>=0; i++){
			if(feld[zeile-i][(spalte-i)]==1){
				return false;
			}
		}
		//Oben Rechts
		for (int i=1; zeile-i>=0 && spalte+i<8; i++){
			if(feld[zeile-i][(spalte+i)]==1){
				return false;
			}
		}
		//Unten Links
		for (int i=1; zeile+i<8 && spalte-i>=0; i++){
			if(feld[zeile+i][(spalte-i)]==1){
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		DamenProblem alpha = new DamenProblem();
		int[][] assi = alpha.loese(0, 0);
		for (int i=0; i<assi.length; i++){
			for (int j=0; j<assi.length; j++){
				System.out.print(assi[i][j]+" ");
			}
			System.out.println();
		}
	}
}

Ich bin dem Programablauf teilweise mit nem Debugger durchgegangen, doch habe kein Fehler finden können, wollte aber auch nicht 2 Stunden debuggen.

Kann jemand helfen?

Viele Grüße

 

[SlaterB]

du läßt also lieber andere suchen? na gut, macht ja auch irgendwie Spass

zwei grundsätzliche Probleme sehe ich vorerst:
1. selbst wenn du was richtiges findest hast du immer noch den rekursiven Rückbau,
Zeile 37 wird das Ergebnis immer weitgehend löschen, ob richtig oder falsch

2. in Zeile 35 + 39 wird die sinnvolle Rekursion in zeile +1 forgeführt, dabei können auch die ersten Zeilen noch frei sein, starte immer bei Zeile 1

hier eine Version die zumindest ein Ergebnis liefert, falls du es nicht mit diesen Tipps alleine versuchen willst

    public int[][] loese(int zeile, int spalte)
    {
        int[][] feld = new int[8][8];
        clear(feld);
        // setzt die Startposition
        feld[zeile][spalte] = 1;
        loeseProblem(feld, 1, 1);
        return feld;
    }

    // Rekursion
    public boolean loeseProblem(int[][] feld, int zeile, int spalte)
    {
        if (zeile > 7)
        {
            return false;
        }

        boolean ok = istOk(feld, zeile, spalte);
        // Falls Position ist günstig
        if (ok)
        {
            feld[zeile][spalte] = 1;
            // Falls ergebnis erzielt
            if (spalte == 7)
            {
                return true; // richtiges Ergebnis gefunden
            }
            else
            {
                boolean found = loeseProblem(feld, 1, spalte + 1);
                if (found)
                {
                    return true; // fertig, nicht Dame wieder löschen
                }
                // Schritt zurück
                feld[zeile][spalte] = 0;
            }
        }
        // vereinfachte weitere Suche
        return loeseProblem(feld, zeile + 1, spalte);
    }

cnt habe ich entfernt, reicht doch auf zeile zu schauen,

der Anfang mit der Methode loese() ist etwas merkwürdig, wenn das nicht Feld 0/0 ist, dann wird der Rest wohl kaum klappen,
evtl. gehts wenn man die Rekursion besser startet, bei 0/0 statt Zeile 1 usw.

 

[alphatier]

Vielen Dank für die Hilfe.