# Schachfeld



## discere (8. Dez 2012)

Ich muss Schachfeld programmieren, das N einliest und versucht möglichst viele Springer-Figuren auf einem Schachfeld der Größe N * N zu platzieren ohne dass diese sich gegenseitig bedrohen. Ich nutze Backtracking für die Implentierung. 

Das Programm kommt viele verschiedene Ergebnisse raus. Ich denke es muss nur ein Ergebnis rauskommen zu sein. Und, das Programm reagiert sich nur mit N =2 und N=3 nicht. Warum????:L???:L Danke


```
public class Field {

    public static void printQueens(int[] q) {
        int N = q.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (q[i] == j) System.out.print("o ");
                else           System.out.print(". ");
            }
            System.out.println();
        }  
        System.out.println();
        
    }
	
	public static boolean inConsistant(int [] s, int r) {
		for(int i = 0; i < r; i++) {
			if(s[i] == s[r]) return false; //same column
			if(s[i] + i == s[r] + r) return false; //same major diagonal
			if(s[i] - i == s[r] - r) return false; //same minor diagonal
		}
		return true;
	}
	
	public static void enumerate(int []s, int n) {
		if (n == 0) {
			printQueens(s);
			return;
		}
		
		int N = s.length;
		int r = N - n;
		
		for( int i = 0; i < N; i++) {
			s[r] = i;
			if(! inConsistant(s, r))
				continue;
			enumerate(s, n-1);
		}
	}
	
	public static void main(String[] args) {
		int N = Integer.parseInt(args [0]);
		int [] s = new int [N];
		enumerate(s, N);
		

	}

}
```


----------



## discere (8. Dez 2012)

Hallo, ich habe Problem. Man versucht möglichst viele Springer-Figuren auf einem Schachfeld der Größe N * N. Das heisst, ist mein Programmiert nicht richtig.


----------



## Firephoenix (8. Dez 2012)

Es fällt mir ziemlich schwer zu verstehen was du meinst.

Vom Code her vermute ich mal, dass es sich um das N-Damenproblem handelt.
Damenproblem ? Wikipedia

Dafür gibt es für die Feldgrößen 2x2 und 3x3 keine Lösungen (falls das unklar ist - aufmalen und versuchen eine Lösung zu finden).

Von dem Text her könnte es aber auch eine Adaption auf Springer sein (Springer => Figur die sich immer auf einer Achse um 1 Feld und auf einer 2. Achse um 2 Felder verschieben kann Schach ? Wikipedia).

Für beide Probleme gibt es mehrere Lösungen (Das Damenproblem auf 8x8 hat 92 bzw 12 eindeutige Lösungen), es kann also durchaus sein, dass dein Programm dir mehrere Lösungen ausgibt.
Falls das nicht dein eigenes Problem war: Bitte nochmal erklären was nicht funktioniert.

(Und wenn man innerhalb von 30 Minuten mal keine Antwort bekommt muss man nicht gleich pushen. Das hier ist schließlich der Hausaufgabenbereich am Wochenende :gaen

Gruß


----------



## discere (9. Dez 2012)

Ja, es geht um Springer-Problem. N einliest und versucht möglichst viele Springer-Figuren auf einem Schachfeld der Größe N * N zu platzieren ohne dass diese sich gegenseitig bedrohen.

Ich habe Problem mit Backtracking zu finden. ???:L Ich habe auf Papier gezeichnet. Ich kapiere ja. Aber Backtracking zu programmieren. :rtfm:

Oben ist mein Program falsch. Es geht um Damen-Problem. Ich war verwirrt.


----------



## schlingel (9. Dez 2012)

Um was geht es jetzt?
Damen? Können sich waag- oder senkrecht bewegen. (vertikal, horizontal)
Springer oder auch Pferd genannt? Können sich L-förmer von ihrem aktuellen Feld aus weg bewegen.


----------



## discere (9. Dez 2012)

es geht nur um Springer. Viele Springer-Figuren auf einem Schachfeld der Größe N * N zu platzieren ohne dass diese sich gegenseitig bedrohen.

Bsp.: 
N=5: Board has 13 knights threatening 12 positions
+-----+
|o.o.o|
|.o.o.|
|o.o.o|
|.o.o.|
|o.o.o|
+-----+ 

N=6: Board has 18 knights threatening 18 positions
+------+
|o.o.o.|
|.o.o.o|
|o.o.o.|
|.o.o.o|
|o.o.o.|
|.o.o.o|

Ich habe Problem mit Backtracking zu lösen.


----------



## schlingel (9. Dez 2012)

Wie ist denn dein Ansatz?

Platzierst du einen Springer und erzeugst dann ein neues Spielfeld wo du auf einer beliebigen freien Kachel einen neuen platzierst, prüfst dann ob in einer der Möglichkeiten der neue geschlagen wird oder nicht, verwendest oder verwirfst dann das Ergebnis und beginnst von neuen oder wie darf ich mir das vorstellen? (Das wäre ja der primitivste Backtracking-Ansatz der mir jetzt einfällt.)

Was ist denn das Problem überhaupt? Herausfinden ob ein Springer einen anderen schlagen kann? Das Verwalten der möglichen Lösungen? Das Herausfinden der "besten" Lösung?

Ohne Details fällt das Helfen schwer.


----------



## discere (9. Dez 2012)

ja, ich habe mir auch vorgestellt. "Platzierst du einen Springer und erzeugst dann ein neues Spielfeld wo du auf einer beliebigen freien Kachel einen neuen platzierst, prüfst dann ob in einer der Möglichkeiten der neue geschlagen wird oder nicht, verwendest oder verwirfst dann das Ergebnis und beginnst von neuen" 

Aber Backtracking-Ansatz weiß ich net. Einfach kann ich auf Papier malen. Aber wie kann ich das Programm mit Backtracking-Ansatz progammieren.


----------



## schlingel (9. Dez 2012)

Genau so. Du brauchst eine Generator-Methode die dir alle Möglichkeiten erzeugt um auf einem Eingabespielfeld einen neuen Springer zu platzieren. 

Um das ganze etwas einfacher zu machen, prüfst du am besten bereits in der Generator-Methode ob der neu platzierte Springer einen anderen schlägt. Tut er das, gibst du das neue Feld in die Ergebnismenge, tut er das nicht kommt das Feld in die Eingabemenge für die Generator-Methode.

Das ganze rufst du so oft auf bis die Eingabemenge für den nächsten Generator-Methodeaufruf leer ist. Dann musst du im nächsten Schritt das beste Ergebnis suchen. Das gibst du dann zurück.

Spielfeld würde ich als doppeltes boolean Array definieren. boolean[][] wobei true für Springer, false für leer steht.
Ergebnis würde ich als Klasse definieren die ein Spielfeld enthält und außerdem die Anzahl der darin enthaltenen Springer.

Der Generator könnte dann so aussehen:

```
function generator(Eingabemenge, Ergebnismenge) {
   if(Eingabemenge is empty)
      return Ergebnismenge;

   für jedes Feld in Eingabemenge do {
      entferne Feld aus Eingabemenge
      var isFeldLösung = false;

      für i bis N do {
         für j bis N do {
            if(Feld[i][j] == false) {
               var neuesFeld = Feld;
               if(würdeSpringerAnStelleXYAndereSchlagen(Feld, i, j)) {
                  Ergebnismenge.add(Feld);
                  isFeldLösung = true;
               } else {
                  Eingabemenge.add(Feld);
               }
            }
         }
         
         if(!isFeldLösung)
           Ergebnismenge.add(Feld); 
      }
   }

   return generator(Eingabemenge, Ergebnismenge);
}
```

Ergebnis davon ist dann eine (unter Umständen sehr lange) Liste mit lauter Lösungen für das Problem. Du musst dann noch eine Methode schreiben die das Feld zurück gibt, mit den meisten true-Werten darin.


----------



## discere (9. Dez 2012)

ich habe andere Weg programmieren. Es gibt Problem. Es kompiliert und funktioniert für n=1 und 2 aber nicht für größere Zahlen. ???:L Ich habe lang versucht. 


```
public class Knights {
	static private enum State { free, occ/*upied*/, burnt };
	static private State[][] board, max;
	static private int size, num, maxnum, burnt, occ;

	public static void main(String[] a) {
		size = 2; //Integer.parseInt(a[0]);
		if(size == 2)
			num = 4;
		else if (size%2==0) {
			num = size*size/2; }
		else {
			num = size*size/2 + 1; }

		board  = new State[size][size];
		max = new State[size][size];
		for(int i = 0; i<size; i++){
			for(int j = 0; j<size; j++){
				board[i][j] = State.free;
				max[i][j] = State.free;
			}
		}

		Findibus(0, 0);
		print();
	}

	private static void Findibus (int x, int y) {
		while (occ+burnt<num) {
			pair next = getNextFree();
			if(next == null)
				break; // Backtracking goes here
			board = springen(next.getX(),next.getY());
			Findibus(next.getX(),next.getY());
		}
	}

	private static pair getNextFree() {
		for (int i = 0; i<size; i++) {
			for(int j = 0; j<size; j++) {
				if (board[i][j] == State.free) {
					return new pair(i,j);
				}
			}
		}
		// Alle Felder sind besetzt oder verbrannt
		return null;
	}

	private static State[][] springen(int i, int j){
		State[][] copy = arrayCopy(board);
		copy[i][j] = State.occ;
		if(i>1){
			if(j>0)
				if (copy[i-2][j-1] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else {
					copy[i-2][j-1] = State.burnt;
					burnt++;
				}

			if(j<size-1)
				if (copy[i-2][j+1] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else{
					copy[i-2][j+1] = State.burnt;
					burnt++;
				}
		}
		if(i>0){
			if(j>1)
				if (copy[i-1][j-2] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else {
					copy[i-1][j-2] = State.burnt;
					burnt++;
				}
			if(j<size-2)
				if (copy[i-1][j+2] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else {
					copy[i-1][j+2] = State.burnt;
					burnt++;
				}
		}
		if(i<size-1){
			if(j>1)
				if (copy[i+1][j-2] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else {
					copy[i+1][j-2] = State.burnt;
					burnt++;
				}
			if(j<size-2)
				if (copy[i+1][j+2] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else {
					copy[i+1][j+2] = State.burnt;
					burnt++;
				}
		}
		if(i<size-2){
			if(j>0)
				if (copy[i+2][j-1] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else{
					copy[i+2][j-1] = State.burnt;
					burnt++;
				}
			if(j<size-1)
				if (copy[i+2][j+1] == State.burnt){
					copy[i][j] = State.burnt;
					return copy;
				}
				else{
					copy[i+2][j+1] = State.burnt;
					burnt++;
				}
		}
		occ++;
		return copy;
	}

	private static State[][] arrayCopy (State[][] s){
		State[][] r = new State[size][size];
		for (int i = 0; i<size; i++) {
			for (int j = 0; j<size; j++) {
				r[i][j] = s[i][j];
			}
		} 
		return r;
	}

	private static void print(){
		System.out.println(occ);
		for(int i = 0; i < size; i++){
			for(int j = 0; j < size; j++){
				if(board[i][j] == State.occ)
					System.out.print("o");
				else
					System.out.print(".");
			}
			System.out.println();
		}
	}
}

class pair {
	int a;
	int b;
	public pair(int x, int y){
		a = x;
		b = y;
	}
	public int getX(){
		return a;
	}
	public int getY(){
		return b;
	}
}
```


----------



## Marcinek (9. Dez 2012)

Hättest du Lust soviel Code zu lesen und ggf kopieren und Compilieren, fachlich zu analysieren um dann auf den Fehler zu kommen, der bei dir Auftritt??

Wieso postest du nicht den Fehler, der kommt???

Bitte lese den link in meiner Signatur.


----------



## discere (9. Dez 2012)

ja, ich finde den Fehler nicht. Es geht nur bei N =1 und N=2. Was habe ich falsch gemacht. ???:L


----------



## Marcinek (9. Dez 2012)

Also für n=3 

Bekomme ich für num einen falschen Wert. 

Denn 3 mal 3 durch zwei +1 wird hier 4 ergeben. Erwarten würdest du hier aber 5,5 oder zumindest abgerundet. 

Das scheint die maximale Anzahl der Springer auf den Feld zu sein, ohne, dass die sich treffen. (Die theoretische Anzahl. 

Garantiert ohne das zu verifizieren wird das als Abbruch Bedingung genutzt. 

Und dann machst du zuwenig Schritte. 

--

Solche Fehler wird es bestimmt massenweise geben. 

Mein Rat: lerne Code debuggen oder schreibe zumindest ligausgaben an den wichtigen stellen.


----------

