Damenproblem

Dodo!

Mitglied
Ich habe folgende Aufgabe:
In dieser Aufgabe soll ein Java-Programm implementiert werden, das alle Lösungen des Damenproblems mit acht Damen ermittelt. Eine Platzierung wird durch ein Array aus acht Ganzzahlen dargestellt. Jedes Array-Element steht dabei für eine Zeile des Schachbretts. Der Wert des Array-Elements bezeichnet die Spalte in der die Dame dieser Zeile zu finden ist. Beachten Sie, dass bei Arrays die Zählung bei 0 beginnt und die Zeilen- und Spaltenindizes deshalb Zahlen von 0 bis 7 sind.

Implementieren Sie nun eine Methode boolean threatened(int i, int j), die überprüft, ob das Feld in Zeile i und Spalte j von einer Dame bedroht wird. Ist das Feld bedroht, soll sie true, andernfalls false zurückgeben. Zum Überprüfen verwendet die Methode die aktuelle Platzierung der Damen, die im Array conf gespeichert ist.

Implementieren Sie nun die Methode place(int i). Zur Überprüfung der Bedrohung soll die Methode threatened verwendet werden. Platzieren einer Dame entspricht einer Zuweisung des Werts h an das Array-Element mit Index i. Das Brett ist voll, wenn die Dame mit dem Index 7 platziert wurde. Ausgabe der Konfiguration erfolgt durch printConf(). Wenn Sie alles richtig gemacht haben, sollte ein Aufruf von place(0) 92 verschiedene, korrekte Konfigurationen ausgeben.


Ich habe nun Folgendes geschrieben, erhalte aber nicht das richtige Ergebnis und drehe mich gedanklich im Kreis:

Java:
import java.util.Arrays;

public class Queens {
	
	static int zaehler=0;
	static int conf [];
	
	Queens(int a){
		conf = new int[a];
	}

	static void printConf(){
		String a = Arrays.toString(conf);
		System.out.println(""+a);
	}
	
	static boolean threatened(int zeilen, int spalten){
        for (int i = 0; i<zeilen; i++){
            if(conf[zeilen-i]==spalten){
                return false;}
            if(conf[zeilen-i]==spalten-i){
                return false;}
            if(conf[zeilen-i]==(spalten+i)){
            	return false;}
            }
        return true;
    }
	
    static void place(int i){
    	for(int h=0; h<8 ; h++){
    		if(threatened(i, h)){
    			conf[i]=h;
    			if(i==7){
    				printConf();
                                zaehler++;
    			}
    			else{
    				place(i+1);
    			}
    		}
    	}
    }
	
public static void main(String[] args){
	
	Queens a = new Queens(8);
	a.printConf();
	a.place(0);
	System.out.print(zaehler);
	
}
}

Was sehe, oder verstehe ich nicht?
 
Zuletzt bearbeitet:

HarleyDavidson

Bekanntes Mitglied
Nachtrag: Interessant: Wieso instanziierst du ein Queens-Objekt, obwohl dieses garkeine Variablen und Methoden bereitstellt? Ist doch sonst alles static! ???:L

Schwer, da keine Kommentare dabei sind und man das nur schwer nachvollziehen kann (ich versuche es gleich, schreibe aber meinen ersten Gedanken dazu wie ich vorgegangen wäre).
Für die threatened - Check hätte ich es so gemacht:

Methode threatened(int zeile, int spalte)
Ich muss folgende Fälle abdecken:
  1. Ich befinde mich in der ersten Zeile ganz links: Ich muss nur nach rechts, unten und unten rechts schauen
  2. Ich befinde mich in der ersten Zeile: Ich muss nur nach links, rechts, unten links, unten und unten rechts schauen
  3. Ich befinde mich in der ersten Zeile ganz rechts: Ich muss nur nach links, unten und unten links schauen
  4. Ich befinde mich in einer mittleren Zeile ganz links: Ich muss nur nach oben, rechts oben, rechts, unten rechts und unten schauen
  5. Ich befinde mich in einer mittleren Zeile: Ich muss in alle Richtungen schauen
  6. Ich befinde mich in einer mittleren Zeile ganz rechts: Ich muss nur nach oben, links oben, links, links unten und unten schauen
  7. Ich befinde mich in der letzten Zeile ganz links: Ich muss nur nach rechts, oben und oben rechts schauen
  8. Ich befinde mich in der letzen Zeile: Ich muss nur nach links, rechts, oben links, oben und oben rechts schauen
  9. Ich befinde mich in der letzten Zeile ganz rechts: Ich muss nur nach links, oben und oben links schauen

Diese Fälle muss die Methode abdecken.
Und dann ist das Platzieren kein Problem mehr.
 
Zuletzt bearbeitet:

Dodo!

Mitglied
Nachtrag: Interessant: Wieso instanziierst du ein Queens-Objekt, obwohl dieses garkeine Variablen und Methoden bereitstellt? Ist doch sonst alles static!

Habe die erst einmal statisch initialisiert um das Hauptproblem zu lösen. Später soll der Konstruktor das Spielfeld initialisieren.
Meiner Meinung nach übeprüfe ich ja schon alle Richtungen, hier kurz mit Erklärung, was ich denke, was mein Code macht:

[Java]static boolean threatened(int zeilen, int spalten){
for (int i = 0; i<zeilen; i++){
if(conf[zeilen-i]==spalten){//überpüft, ob "oben" dran in der gleichen Spalte schon eine Dame steht.
return false;}
if(conf[zeilen-i]==spalten-i){//Überprfüt, die Diagonale nach links.
return false;}
if(conf[zeilen-i]==(spalten+i)){//Überprüft die Diagonale nach rechts.
return false;}
}
return true;
}[/code]

Als Ergebnis sollte eben place(0) 92 verschiedene, korrekte Konfigurationen ausgeben. Bei mir sieht das allerdings wie folgt aus:

[...]
[7, 6, 4, 7, 0, 3, 5, 2]
[7, 7, 1, 4, 2, 0, 6, 3]
[7, 7, 2, 0, 6, 4, 1, 5]
[7, 7, 3, 0, 2, 5, 1, 6]
[7, 7, 3, 0, 6, 1, 5, 2]
[7, 7, 3, 0, 6, 4, 1, 5]
[7, 7, 3, 6, 0, 5, 1, 4]
[7, 7, 4, 2, 0, 6, 1, 5]
[7, 7, 5, 0, 2, 4, 6, 3]
[7, 7, 5, 3, 0, 6, 4, 2]
1048
 
Zuletzt bearbeitet:

DrZoidberg

Top Contributor
Also der Code hier liefert 92 Lösungen

Java:
import java.util.Arrays;

public class Queens {
    
    static int zaehler=0;
    static int conf[];
    
    Queens(int a){
        conf = new int[a];
    }
 
    static void printConf(){
        String a = Arrays.toString(conf);
        System.out.println(a);
    }
    
    static boolean threatened(int z, int s){
        for (int i = 0; i<z; i++){
            int d = z-i;
            if(conf[i]==s || conf[i]==s-d || conf[i]==s+d) {
                return true;
            }
        }
        return false;
    }
    
    static void place(int z) {
        for(int s=0; s<conf.length ; s++){
            if(!threatened(z, s)){
                conf[z]=s;
                if(z==conf.length-1){
                    printConf();
                    zaehler++;
                } else{
                    place(z+1);
                }
            }
        }
    }
    
    public static void main(String[] args){
        Queens a = new Queens(8);
        a.printConf();
        a.place(0);
        System.out.print(zaehler);
    }
}
 

Dodo!

Mitglied
Vielen Dank!

Sollte jemand via Google oder Suchfunktion auf diesen Beitrag stoßen hier nochmal der gesamte Code:

Java:
import java.util.Arrays;

public class Queens{
	
	int zaehler;
	int[] conf;
	
	Queens(){
		this.zaehler=0;
		this.conf = new int [8] ;}

	void printConf(){
		String a = Arrays.toString(conf);
		System.out.println("Konfiguration Nr. " +(zaehler+1)+ ": "+a);
	}
	
	boolean threatened(int zeilen, int spalten){
		for (int i = 0; i<zeilen; i++){
            int d = zeilen-i;
            if(conf[i]==spalten || conf[i]==spalten-d || conf[i]==spalten+d){
                return true;}
            }
        return false;
	}
	
   void place(int i){
    	for(int s=0; s<conf.length ; s++){
            if(!threatened(i, s)){
                this.conf[i]=s;
                if(i==conf.length-1){
                    printConf();
                    zaehler++;
                } 
                else{
                    place(i+1);
                 	}
            }
        }
    }
	
   public static void main(String[] args){
	
	   Queens a = new Queens();
	   a.place(0);
	   System.out.println("\n**********************************************\n*    Es gibt " +a.zaehler+ " mögliche Konfigurationen!    *\n**********************************************");
	
   }
}
 

Ähnliche Java Themen

Neue Themen


Oben