Schachbrett: 8 Damen Problem

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Schachbrett: 8 Damen Problem

    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:

    Quellcode

    1. /**
    2. * @author Sebastian Schmitt
    3. *
    4. * Das Programm errechnet, wie auf einem nxn Schachfeld n Damen aufgestellt werden<br>
    5. * koennen, so dass sie sich nicht gegenseitig schlagen.
    6. */
    7. package Aufgabe03;
    8. public class Schachspiel {
    9. /**
    10. * @param args
    11. * Kommandozeilenparameter
    12. */
    13. public static void main(String[] args) {
    14. int n = 24; // nxn Schachfeld, n Damen
    15. int[] a = new int[n];
    16. setzeDame(a, 0);
    17. }
    18. /**
    19. *
    20. * @param a
    21. * array
    22. * @param n
    23. * zeile
    24. */
    25. static void setzeDame(int[] a, int n) {// n= jeweilige Zeile
    26. if (n == a.length) { // wenn n den Wert a.length erhällt, sind alle
    27. int z = 1; // Damen korrekt gesetzt!
    28. for (int x : a)
    29. System.out.println("in reihe " + z++ + ", pos:" + (x + 1));
    30. System.exit(-1);
    31. }
    32. else {
    33. for (int i = 0; i < a.length; i++) {// durchlauft alle felder einer
    34. // Zeile
    35. if (n == 0) { // fuer die erste Zeile
    36. a[0] = n;
    37. setzeDame(a, n + 1);
    38. }
    39. int x = 0;
    40. for (int j = 0; j < n; j++) { // durchlauft alle Zeilen
    41. // kleiner als aktuelle Zeile
    42. if (a[j] != i) // alle zeilen vorher muessen andere Werte haben
    43. if (a[j] != i + (n - j)) // diagonale pruefen, rechts
    44. if (a[j] != i - (n - j))// diagonale pruefen, links
    45. x++; // wenn alles zutrifft, erhoehe x
    46. }
    47. if (x == n) {// wenn x fuer alle zeilen erhoeht wurde, setze
    48. a[n] = i; // Dame und mach weiter in nächster Zeile
    49. setzeDame(a, n + 1);
    50. /*
    51. * sollte dieser rekursive Aufruf nicht zum Ergebniss führen,
    52. * wird die schleife (mit j) weitergeführt ...
    53. */
    54. }
    55. }
    56. }
    57. }
    58. }
    Alles anzeigen