Backtracking Schach

[Ivan_aus_Berlin]

Hallo,
ich versuche mich gerade ein wenig an JAVA und versuche ein Programm mithilfe von Rekursion zu schreiben, welches folgende Aufgabe bewältigen soll:

Das Programm soll alle möglichen Aufstellungen finden, bei der beliebige nxn Felder mit Pferden (Schach) vollgestellt werden, so dass auf jedem Feld ein Pferd steht, sich jedoch keines der Pferde gegenseitig bedroht.

Meine Idee war mir das erste freie Feld zu nehmen (Methode "freies") und dann dieses oder eines der Felder die dieses bedrohen (Methode "moegliche") mit einem Pferd zu besetzen. Dass soll solange wiederholt werden, bis kein freies Feld mehr da ist und die Positionen in Ergebnisse abspeichern.

(if ( (int)M.getFirst()==(-2) ) {Ergebnisse.add(Springer);})

<- es gibt kein freies feld mehr

Ich bastel jetzt schon ne ganze weile am code komme aber jetzt nicht mehr weiter.

Hier noch die verbale form meines codes:
ich rufe rekursion auf (die Übergabe von feld ist denke ich inzwischen überflüssig geworden)
ich erstelle mir ein freies spielfeld
ich blockiere alle felder auf denen ein Springer steht oder die ein Springer bedroht
ich setze M als mein nächstes freies Feld (wenn es keine freien Felder gibt, ist M=(-2,-2))
ich überprüfe ob ich fertig bin und speicher mein ergebnis in einer globalen Variable ab
wenn ich nicht fertig bin:
ich schaue ich mir die felder an, die als nächstes belegt werden könnten (msl)
für jedes Feld speicher ich es ab und rufe rekursion auf

hier kommt dann mein Problem, nachdem die rekrsion fertig ist, soll er das feld ja wieder wegnehmen, damit er die anderen felder probieren kann, wenn ich dass mache, landet in Ergebnisse nix. wenn ich das mit dem löschen des letzten einfach weglasse, schreibt er mir bei nem 8x8 feld 41 mal die selbe lange Liste mit Positionen in Ergebnisse rein.



Hier ist mein Quellcode für die Rekursion

	public static void rekursion(boolean[][] feld, List<Tupel> Springer){
		boolean[][] nf = new boolean[n][n];
		for (int k=0;k<Springer.size();k++){
			nf=belege(nf,Springer.get(k));
		}
		Tupel M = freies(nf);
		if ( (int)M.getFirst()==(-2) ){
			Ergebnisse.add(Springer);
		}
		else {
			List<Tupel> msl = moegliche(nf,M);
			for(int i=0;i<msl.size();i++){
				Springer.add(msl.get(i));
				rekursion(feld,Springer);
				Springer.remove(Springer.size()-1);
			}
		}
		
		
	}

bei bedarf kann ich auch gern den vollständigen code reinstellen. Ich hab jedoch alle untermethoden getesten und das programm läuft auch fehlerfrei. Leider macht es nur noch nicht was ich möchte.

 

[SlaterB]

> Ergebnisse.add(Springer);
hier musst du wahrscheinlich eine Kopie anlegen,
womöglich reicht bereits
> Ergebnisse.add(new ArrayList(Springer));

Variablen klein schreiben!

wofür übergibst du den Parameter feld, wird nirgendwo genutzt?
jedesmal ein neues 2D-Array ist aber in der Tat unschön, fülle lieber das nach und nach, dazu remove einzelner Positionen und als Ergebnis kopieren

die Aufgabe habe ich persönlich noch nicht verstanden, werden Springer von Schwarz und Weiß gesetzt oder nur eine Farbe?
sind am Ende alle 64 Felder mit Springern befüllt oder wie definiert sich 'kein freies Feld', 'mit Pferden (Schach) vollgestellt werden, so dass auf jedem Feld ein Pferd steht' usw?
wozu dann Rekursion, warum nicht alle 64 Felder voll und fertig, was wird überhaupt gesucht, was ist mit der Bedrohung?
aber auch egal

 

[Marco13]

Schau auch mal in http://www.java-forum.org/hausaufgaben/145033-schachfeld.html ...

 

[Ivan_aus_Berlin]

@SlaterB: Super, jetzt läuft es.

 

[Bleiglanz]

Wollte das schon die ganze Woche als Fingerübung erledigen.

Dabei findet mein Programm immer Lösungen, bei denen 32 Springer alle auf Feldern gleicher Farbe bestehen, sagen wir 32 schwarze Springer.

Klar dass die sich nicht gegenseitig bedrohen, ein schwarzer Springer kann nur weiße Felder bedrohen.

Und mehr als 32 Springer kann man auch nicht hinstellen wegen eines 4x2 Arguments (in einem 4x2 Teilrechteck haben maximal 4 Springer Platz, jeder besetzt 1 und bedroht 1...)

Frage: gibt es überhaupt Lösungen mit 32 Springern, wenn diese nicht alle auf der gleichen Farbe stehen?

 

[SlaterB]

bestimmt nicht, mathematisch versiert gesprochen
zwei benachbarte Springer hinterlassen ein desaströses (Schlacht)Feld/Brett von bis zu 16 gesperrten Feldern,
die sollten sich schon besser alle überlappen

keine große Hürde ist wohl das (augenscheinliche) Maximum von gleichzeitig auf den Spielfeld vorhandenden Schwarzfeld- + Weißfeld-Springern gleicher Anzahl,
gibt zusammen bei mir eine weihnachtliche Zahl, dann kann man es erwähnen