Das folgende Programm errechnet mit dem Backtracking Verfahren, wie n Damen auf einem nxn Schachbrett angeordnet werden müssen, damit sie sich nicht gegenseitig schlagen.
Das Schachfeld wird durch ein int-Array repräsentiert. Dabei zegt eine Zahl x am Index i des Arrays, dass auf dem Schachbrett in Reihe i, position x eine Dame steht:
Alles anzeigen
Das Schachfeld wird durch ein int-Array repräsentiert. Dabei zegt eine Zahl x am Index i des Arrays, dass auf dem Schachbrett in Reihe i, position x eine Dame steht:
Quellcode
- /**
- * @author Sebastian Schmitt
- *
- * Das Programm errechnet, wie auf einem nxn Schachfeld n Damen aufgestellt werden<br>
- * koennen, so dass sie sich nicht gegenseitig schlagen.
- */
- package Aufgabe03;
- public class Schachspiel {
- /**
- * @param args
- * Kommandozeilenparameter
- */
- public static void main(String[] args) {
- int n = 24; // nxn Schachfeld, n Damen
- int[] a = new int[n];
- setzeDame(a, 0);
- }
- /**
- *
- * @param a
- * array
- * @param n
- * zeile
- */
- static void setzeDame(int[] a, int n) {// n= jeweilige Zeile
- if (n == a.length) { // wenn n den Wert a.length erhällt, sind alle
- int z = 1; // Damen korrekt gesetzt!
- for (int x : a)
- System.out.println("in reihe " + z++ + ", pos:" + (x + 1));
- System.exit(-1);
- }
- else {
- for (int i = 0; i < a.length; i++) {// durchlauft alle felder einer
- // Zeile
- if (n == 0) { // fuer die erste Zeile
- a[0] = n;
- setzeDame(a, n + 1);
- }
- int x = 0;
- for (int j = 0; j < n; j++) { // durchlauft alle Zeilen
- // kleiner als aktuelle Zeile
- if (a[j] != i) // alle zeilen vorher muessen andere Werte haben
- if (a[j] != i + (n - j)) // diagonale pruefen, rechts
- if (a[j] != i - (n - j))// diagonale pruefen, links
- x++; // wenn alles zutrifft, erhoehe x
- }
- if (x == n) {// wenn x fuer alle zeilen erhoeht wurde, setze
- a[n] = i; // Dame und mach weiter in nächster Zeile
- setzeDame(a, n + 1);
- /*
- * sollte dieser rekursive Aufruf nicht zum Ergebniss führen,
- * wird die schleife (mit j) weitergeführt ...
- */
- }
- }
- }
- }
- }