Acht-Damen-Problem in Java
Dieses Tutorial demonstriert das Acht-Damen-Problem in Java.
Acht-Damen-Problem in Java
Das Acht-Damen-Problem besteht darin, dass wir acht Damen auf einem 8x8-Schachbrett so platzieren müssen, dass sie sich nicht gegenseitig angreifen. Das bedeutet, dass sich keine zwei Damen in derselben Reihe, Spalte oder Diagonale befinden können, da sich die Damen beim Schach darin bewegen können.
Backtracking kann verwendet werden, um das Acht-Damen- oder N-Damen-Problem in Java zu lösen. Lassen Sie uns also zuerst den Backtracking-Algorithmus besprechen.
Verwenden Sie den Back-Tracking-Algorithmus für das Acht-Damen-Problem
Die Idee, das Acht-Damen-Problem mit dem Backtracking-Algorithmus zu lösen, besteht darin, die Damen einzeln in verschiedenen Spalten zu platzieren, beginnend mit der Spalte ganz links. Wir setzen eine Dame in eine Spalte und prüfen dann auf die Kollision mit anderen Damen, die zuvor platziert wurden.
Dann markieren wir in einer Spalte, wenn eine Zeile nicht in der Kollision ist, sowohl Spalte als auch Zeile als Teil der Lösung des Acht-Damen-Problems. Das Backtracking wird verwendet, wenn wir keine Situation finden, die nicht in Konflikt steht, und wir geben false zurück.
Hier ist der Schritt-für-Schritt-Prozess zur Lösung des Acht-Damen-Problems mit dem Backtracking-Algorithmus:
-
Beginnen Sie zunächst mit der Spalte ganz links.
-
Machen Sie eine Bedingung, dass der Code wahr zurückgibt, wenn alle Damen platziert sind.
-
Gehen Sie nun wie folgt vor und probieren Sie jede Zeile in einer Spalte aus:
- Wenn eine Dame sicher in einer Reihe platziert ist, dann wird diese Reihe und Spalte als der Teil der Lösung markiert, der rekursiv auf andere Lösungen überprüft wird.
- Wenn eine Dame sicher in einer Reihe platziert ist, dann true zurückgeben.
- Wenn eine Dame nicht sicher in einer Reihe platziert ist, heben Sie die Markierung der Reihe und Spalte auf, gehen Sie die Lösung zurück, gehen Sie zurück zur ersten Option und wenden Sie die Lösung auf andere Reihen an.
-
Wenn wir alle Zeilen überprüft haben und es keine Lösung gibt, sollten wir false zurückgeben, um den Backtracking-Algorithmus auszulösen.
Versuchen wir nun, ein Beispiel basierend auf den obigen Schritten zu implementieren:
package delftstack;
public class EightQueen {
// Size of the board should be 8x8 for the eight queens problem
public static final int SIZE_OF_BOARD = 8;
boolean[][] BOARD_BOOLEAN;
// For an empty place
public static final boolean EMPTY_PLACE = false;
// For a place that contains a queen
public static final boolean QUEEN_PLACE = true;
// The number of moves
public static final int MOVES_NUMBER = 4;
// The horizontal moves
int[] Horizontal_Moves;
// The Vertical moves
int[] Vertical_Moves;
public int Queens = 0;
public EightQueen() {
// Constructor creates an empty board
BOARD_BOOLEAN = new boolean[SIZE_OF_BOARD][SIZE_OF_BOARD];
for (int row = 0; row < BOARD_BOOLEAN.length; row++) {
for (int col = 0; col < BOARD_BOOLEAN[row].length; col++) {
BOARD_BOOLEAN[row][col] = EMPTY_PLACE;
}
}
Horizontal_Moves = new int[MOVES_NUMBER];
Vertical_Moves = new int[MOVES_NUMBER];
// move up right
Horizontal_Moves[0] = -1;
Vertical_Moves[0] = 1;
// move down left
Horizontal_Moves[1] = 1;
Vertical_Moves[1] = -1;
// move up left
Horizontal_Moves[2] = -1;
Vertical_Moves[2] = -1;
// move down right
Horizontal_Moves[3] = 1;
Vertical_Moves[3] = 1;
}
public boolean Queens_Placing(int Board_Column) {
if (Board_Column >= SIZE_OF_BOARD) {
return true;
} else {
boolean Queen_Placed = false;
int Board_Row = 0;
while (!Queen_Placed && Board_Row < SIZE_OF_BOARD) {
if (Queen_UnderAttack(Board_Row, Board_Column)) {
++Board_Row;
} else {
Set_Queen(Board_Row, Board_Column);
Queen_Placed = Queens_Placing(Board_Column + 1);
if (!Queen_Placed) {
Remove_Queen(Board_Row, Board_Column);
++Board_Row;
}
}
}
return Queen_Placed;
}
}
private void Remove_Queen(int Board_Row, int Board_Column) {
BOARD_BOOLEAN[Board_Row][Board_Column] = EMPTY_PLACE;
// Remove the comment from the code below to check which place the queen was removed.
// System.out.printf("The queen is REMOVED from [%d][%d]\n", Board_Row, Board_Column);
--Queens;
}
private void Set_Queen(int Board_Row, int Board_Column) {
BOARD_BOOLEAN[Board_Row][Board_Column] = QUEEN_PLACE;
// Remove the comments from the code below to check where the queen was placed
// System.out.printf("The queen is PLACED in [%d][%d]\n", Board_Row, Board_Column);
++Queens;
}
public boolean Queen_UnderAttack(int Board_Row, int Board_Column) {
boolean Queen_Condition = false;
// check the row
for (int Column = 0; Column < SIZE_OF_BOARD; Column++) {
if ((BOARD_BOOLEAN[Board_Row][Column] == true)) {
Queen_Condition = true;
}
}
// check the column
for (int Row = 0; Row < BOARD_BOOLEAN.length; Row++) {
if (BOARD_BOOLEAN[Row][Board_Column] == true) {
Queen_Condition = true;
}
}
// check the diagonal
for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column < 8;
Row += Horizontal_Moves[0], Column += Vertical_Moves[0]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column >= 0;
Row += Horizontal_Moves[1], Column += Vertical_Moves[1]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column >= 0;
Row += Horizontal_Moves[2], Column += Vertical_Moves[2]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column < 8;
Row += Horizontal_Moves[3], Column += Vertical_Moves[3]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
return Queen_Condition;
}
public void Display_Board() {
int Count = 0;
for (int Board_Row = 0; Board_Row < BOARD_BOOLEAN.length; Board_Row++) {
for (int Board_Column = 0; Board_Column < BOARD_BOOLEAN[Board_Row].length; Board_Column++) {
if (BOARD_BOOLEAN[Board_Row][Board_Column] == true) {
System.out.printf("|%s| ", " Q ");
Count++;
} else {
System.out.printf("|%s| ", " X ");
}
}
System.out.println();
}
System.out.printf("%d queens problem is solved, the queens are placed.\n", Count);
}
public static void main(String[] arg) {
EightQueen EightQueen_Problem = new EightQueen();
EightQueen_Problem.Queens_Placing(0);
EightQueen_Problem.Display_Board();
}
}
Der obige Code implementiert das Acht-Damen-Problem unter Verwendung der Backtracking-Algorithmus-Lösung. Es wird die Königinnen dort platzieren, wo sie sich nicht gegenseitig töten können.
Sehen Sie sich die Ausgabe an, in der Q die Damen bezeichnet:
| Q | | X | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | Q | | X |
| X | | X | | X | | X | | Q | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | X | | Q |
| X | | Q | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | Q | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | Q | | X | | X |
| X | | X | | Q | | X | | X | | X | | X | | X |
8 queens problem is solved, the queens are placed.
Die Zeitkomplexität für den obigen Algorithmus ist O(N!) und der Hilfsraum ist O(N2).
Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.
LinkedIn Facebook