N-Damen-Problem unter Verwendung von Backtracking in Java/C++
Wenn du gerne Schach spielst, wirst du es genießen, etwas über das N-Damen-Problem zu lernen. Es ist ein gutes Problem, um Backtracking zu verstehen.
Was ist Backtracking?
Beim Backtracking beginnen wir mit einem möglichen Zug aus vielen verfügbaren Zügen. Dann versuchen wir, das Problem zu lösen.
Wenn wir in der Lage sind, das Problem mit dem gewählten Zug zu lösen, dann werden wir die Lösung ausdrucken. Andernfalls werden wir zurückverfolgen und einen anderen Zug auswählen und versuchen, es zu lösen.
Wenn keiner der Züge funktioniert, behaupten wir, dass es keine Lösung für das Problem gibt.
Was ist das N-Damen-Problem?
How can N queens be placed on an NxN chessboard so that no two of them attack each other?Dieses Problem tritt häufig bei N=4 und N=8 auf.
Schauen wir uns ein Beispiel an, bei dem N=4
Bevor man das Problem löst, muss man über die Bewegung der Dame im Schach Bescheid wissen.
Eine Königin kann sich beliebig viele Felder in jede Richtung bewegen. Die einzige Einschränkung ist, dass sie ihre Richtung während der Bewegung nicht ändern darf.
Eines, das beim Betrachten der Bewegung der Königin klar wird, ist, dass keine zwei Königinnen in derselben Reihe oder Spalte stehen können.
Das ermöglicht es uns, nur eine Königin in jede Reihe und jede Spalte zu setzen.
Wenn N=4, sieht die Lösung wie folgt aus :
Aber wie bekommen wir diese Vereinbarung?
Lösung des N-Damen-Problems
Die Art, wie wir versuchen, dies zu lösen, besteht darin, eine Königin an einer Position zu platzieren und zu versuchen, die Möglichkeit auszuschließen, dass sie angegriffen wird. Wir platzieren eine Königin in jeder Reihe/Spalte.
Wenn wir sehen, dass die Königin an ihrer gewählten Position angegriffen wird, versuchen wir die nächste Position.
Wenn eine Dame in allen Positionen einer Reihe angegriffen wird, gehen wir zurück und ändern die Position der zuvor zur aktuellen Position gesetzten Dame.
Wir wiederholen diesen Prozess des Platzierens einer Königin und des Rückwärtsgehens, bis alle N Damen erfolgreich platziert sind.
Das schrittweise Zurückverfolgen wird wie folgt gezeigt:
Das rote Kreuz markiert die Positionen, die von einer Dame angegriffen werden. Immer wenn wir einen Zustand erreichen, in dem wir eine Dame platzieren müssen, aber alle Positionen in den Reihen angegriffen werden, gehen wir zurück.
Dies ist nicht die einzige mögliche Lösung für das Problem. Wenn Sie jede Königin einen Schritt vorwärts im Uhrzeigersinn bewegen, erhalten Sie eine weitere Lösung.
In diesem Beispiel haben wir die Damen nach Reihen platziert, wir können dasselbe auch spaltenweise tun. In diesem Fall wird jede Dame zu einer Spalte gehören.
Implementierung des N-Damen-Problems in C++ und Java
Implementierung des N-Damen-Problems in C++:
#define N 4
#include <stdbool.h>
#include <stdio.h>
//function to print the solution
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
}
// function to check whether the position is safe or not
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
// The function that solves the problem using backtracking
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
// driver program to test above function
int main()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return 0;
}
printSolution(board);
return true;
return 0;
} Implementierung des N-Damen-Problems in Java:
package com.JournalDev;
public class Main {
static final int N = 4;
// print the final solution matrix
static void printSolution(int board[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j]
+ " ");
System.out.println();
}
}
// function to check whether the position is safe or not
static boolean isSafe(int board[][], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
// The function that solves the problem using backtracking
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}
public static void main(String args[])
{
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (!solveNQueen(board, 0)) {
System.out.print("Solution does not exist");
return;
}
printSolution(board);
}
} Output :
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0 
Für N=8 ist die Ausgabe :
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
Verstehen der Code-Implementierung
Um zu überprüfen, ob eine Position angegriffen wird oder nicht, haben wir eine Funktion namens isSafe erstellt.
Die Funktion gibt true zurück, wenn die Positionen vor jeglichem Angriff sicher sind.
static boolean isSafe(int board[][], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}Die erste for-Schleife überprüft entlang der Spalte, die zweite und dritte for-Schleife überprüfen entlang der beiden Diagonalen.
Der folgende Codeabschnitt ist dafür verantwortlich, die Damen an ihren Positionen zu platzieren und Backtracking durchzuführen. Um die Position einer Dame zu markieren, setzen wir diese Zelle in der Matrix auf 1. Bevor wir die Dame platzieren, rufen wir isSafe auf, um sicherzustellen, dass die Position sicher ist.
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}Der rekursive Aufruf übergibt das Brett und setzt die Spalte auf col+1. Wenn der rekursive Aufruf false zurückgibt, machen wir einen Backtrack, indem wir den Eintrag auf 0 zurücksetzen.
Fazit
So löst man das N-Damen-Problem mithilfe von Backtracking. Um mehr über Backtracking zu lernen, versuchen Sie, das Sudoku-Problem zu lösen.