001 package de.hska.info1.backtracking.achtdamen;
002
003 /**
004 * Löst das Acht-Damen-Problem mit Hilfe eines
005 * Backtracking-Algorithmus - es wird das verallgemeinerte n-Damen-Problem
006 * gelöst. Beim n-Damen-Problem sollen n-Damen auf ein n x n Schachbrett
007 * gesetzt werden, so dass keine Dame eine anderen schlagen kann.
008 *
009 * @author Christian Pape
010 */
011 public class AchtDamenProblem {
012
013
014 /**
015 * dameInZeile[z] == s, genau dann, wenn in Zeile z und
016 * Spalte s eine Dame gesetzt wurde. Ansonsten ist der
017 * Wert -1.
018 */
019 private int [] dameInZeile;
020
021 /**
022 * dameInSpalte[s] == true genau dann, wenn in Spalte s eine
023 * Dame gesetzt wurde
024 */
025 private boolean [] dameInSpalte;
026
027 /**
028 * dameInNebendiagonale[s + z] == true, wenn in der (s+z)-ten Nebendiagonale
029 * eine Dame gesetzt wurde
030 */
031 private boolean [] dameInNebendiagonale;
032
033 /**
034 * dameInHauptdiagonale[z - s + dameInZeile.length] == true, wenn
035 * in der entsprechenden Hauptdiagonale eine Dame gesetzt wurde
036 */
037 private boolean [] dameInHauptdiagonale;
038
039
040 /**
041 * Erzeugt ein Acht-Damen-Problem für ein 8 x 8 Schachbrett, so
042 * wie für die "klassische" Version.
043 */
044 public AchtDamenProblem() {
045 this(8);
046 }
047
048
049 /**
050 * Erzeugt ein n-Damen-Problem für ein n x n Schachbrett und n Damen.s
051 */
052 public AchtDamenProblem(int n) {
053 dameInZeile = new int[n];
054 for (int i = 0; i < dameInZeile.length; i++) {
055 dameInZeile[i] = -1;
056 }
057 dameInSpalte = new boolean[n];
058 dameInNebendiagonale = new boolean[2 * n + 1];
059 dameInHauptdiagonale = new boolean[2 * n + 1];
060 }
061
062 /**
063 * Sucht mit Backtracking eine Lösung für das n bzw. 8-Damen-Problem.
064 */
065 public boolean sucheLoesung(int zeile) {
066 for (int spalte = 0; spalte < dameInZeile.length; spalte++) {
067 if (! dameIstBedroht(zeile, spalte)) {
068 setzteDame(zeile, spalte);
069 if (zeile < dameInZeile.length - 1) {
070 if ( sucheLoesung(zeile + 1)) {
071 return true;
072 } else {
073 dameWegnehmen(zeile, spalte);
074 }
075 } else {
076 return true;
077 }
078 }
079 }
080
081 return false;
082 }
083
084 /**
085 * Nimmt die Dame von der gegebene zeile und spalte wieder weg.
086 */
087 private void dameWegnehmen(int zeile, int spalte) {
088 dameInZeile[zeile] = -1;
089 dameInSpalte[spalte] = false;
090 dameInNebendiagonale[zeile + spalte] = false;
091 dameInHauptdiagonale[zeile - spalte + dameInZeile.length] = false;
092 }
093
094
095 /**
096 * Setzt eine Dame in die gegeben zeile und spalte.
097 */
098 private void setzteDame(int zeile, int spalte) {
099 dameInZeile[zeile] = spalte;
100 dameInSpalte[spalte] = true;
101 dameInNebendiagonale[zeile + spalte] = true;
102 dameInHauptdiagonale[zeile - spalte + dameInZeile.length] = true;
103 }
104
105
106 /**
107 * Gibt true zurück, wenn die Dame in der gegebenen
108 * zeile und spalte von einer anderen Dame bedroht ist.
109 */
110 private boolean dameIstBedroht(int zeile, int spalte) {
111 return dameInZeile[zeile] != -1
112 || dameInSpalte[spalte]
113 || dameInNebendiagonale[zeile + spalte]
114 || dameInHauptdiagonale[zeile - spalte + dameInZeile.length];
115 }
116
117 /**
118 * Gibt die Lösung auf dem Bildschirm aus.
119 *
120 */
121 public void printLoesung() {
122 for (int zeile = 0; zeile < dameInZeile.length; zeile++) {
123 for (int spalte = 0; spalte < dameInZeile.length; spalte++) {
124 if (dameInZeile[zeile] == spalte) {
125 System.out.print("X|");
126 } else {
127 System.out.print(" |");
128 }
129 }
130 System.out.println();
131 }
132 System.out.println();
133 }
134
135 public static void main(String [] argv) {
136 AchtDamenProblem achtDamenProblem = new AchtDamenProblem(25);
137
138 achtDamenProblem.sucheLoesung(0);
139
140 achtDamenProblem.printLoesung();
141 }
142 }