Wir haben diskutiert Rittertour Und Ratte in einem Labyrinth Problem früher als Beispiele für Backtracking-Probleme. Lassen Sie uns N Queen als ein weiteres Beispielproblem diskutieren, das mithilfe von Backtracking gelöst werden kann.
Was ist das N-Queen-Problem?
Der N Königin ist das Problem der Platzierung N Schachköniginnen auf einem N×N Schachbrett, damit sich nicht zwei Damen gegenseitig angreifen.
Das Folgende ist beispielsweise eine Lösung für das 4-Queen-Problem.
Die erwartete Ausgabe erfolgt in Form einer Matrix mit „ Q steht für die Blöcke, in denen Damen platziert sind, und die leeren Felder werden durch dargestellt '.' . Das Folgende ist beispielsweise die Ausgabematrix für die obige 4-Queen-Lösung.
Empfohlen: Bitte lösen Sie es auf ÜBEN zuerst, bevor wir zur Lösung übergehen.. Q . .
. . . Q
Q . . .
. . Q .
N Queen Problem bei der Verwendung Zurückverfolgen :
Die Idee besteht darin, die Damen nacheinander in verschiedenen Spalten zu platzieren, beginnend mit der Spalte ganz links. Wenn wir eine Königin in einer Spalte platzieren, prüfen wir, ob es zu Konflikten mit bereits platzierten Königinnen kommt. Wenn wir in der aktuellen Spalte eine Zeile finden, für die es keinen Konflikt gibt, markieren wir diese Zeile und Spalte als Teil der Lösung. Wenn wir eine solche Reihe aufgrund von Zusammenstößen nicht finden, machen wir einen Rückzieher und kehren zurück FALSCH .
Unten ist der rekursive Baum des obigen Ansatzes:
Rekursiver Baum für das N-Queen-Problem
Befolgen Sie die unten aufgeführten Schritte, um die Idee umzusetzen:
- Beginnen Sie in der Spalte ganz links
- Wenn alle Damen platziert sind, wird „true“ zurückgegeben
- Probieren Sie alle Zeilen in der aktuellen Spalte aus. Gehen Sie für jede Zeile wie folgt vor.
- Wenn die Königin sicher in dieser Reihe platziert werden kann
- Dann markieren Sie dies [Zeile Spalte] als Teil der Lösung und prüfen Sie rekursiv, ob die Platzierung der Königin hier zu einer Lösung führt.
- Wenn die Königin eingesetzt wird [Zeile Spalte] führt zu einer Lösung und dann zurück WAHR .
- Wenn das Platzieren der Königin nicht zu einer Lösung führt, heben Sie die Markierung auf [Zeile Spalte] Gehen Sie dann zurück und versuchen Sie es mit anderen Zeilen.
- Wenn alle Zeilen ausprobiert wurden und keine gültige Lösung gefunden wurde, kehren Sie zurück FALSCH Backtracking auszulösen.
- Wenn die Königin sicher in dieser Reihe platziert werden kann
Eine bessere Visualisierung dieses Backtracking-Ansatzes finden Sie hier 4-Königin-Problem .
Notiz: Wir können dieses Problem auch lösen, indem wir die Königinnen ebenfalls in Reihen platzieren.
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
Java verkettet Zeichenfolgen
C++
// C++ program to solve N Queen Problem using backtracking> #include> #define N 4> using> namespace> std;> // A utility function to print solution> void> printSolution(>int> board[N][N])> {> >for> (>int> i = 0; i for (int j = 0; j if(board[i][j]) cout << 'Q '; else cout<<'. '; printf('
'); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens bool isSafe(int board[N][N], int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row][i]) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) return false; // Überprüfen Sie die untere Diagonale auf der linken Seite auf (i = Zeile, j = Spalte; j>= 0 && i if (board[i][j]) return false; return true; } // Eine rekursive Dienstprogrammfunktion zum Lösen von N // Queen-Problem boolsolveNQUtil(int board[N][N], int col) { // Basisfall: Wenn alle Königinnen platziert sind // dann true zurückgeben if (col>= N) return true; // Betrachten Sie diese Spalte und versuchen Sie, // diese Königin nacheinander in allen Reihen zu platzieren for (int i = 0; i // Prüfen Sie, ob die Königin auf // board[i][col] platziert werden kann if (isSafe(board, i, col) ) { // Platziere diese Königin in Board[i][col] board[i][col] = 1; // recur, um die restlichen Damen zu platzieren if (solveNQUtil(board, col + 1)) return true; Wenn das Platzieren der Königin auf dem Brett[i][col] // nicht zu einer Lösung führt, dann // entferne die Königin vom Brett[i][col] board[i][col] = 0; // BACKTRACK } } // Wenn die Königin in keiner Zeile // dieser Spalte platziert werden kann, dann return false return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking. Sie verwendet hauptsächlichsolveNQUtil(), um // das Problem zu lösen . Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. boolsolveNQ() { 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) { cout<< 'Solution does not exist'; return false; } printSolution(board); return true; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> |
>
>
C
// C program to solve N Queen Problem using backtracking> #define N 4> #include> #include> // A utility function to print solution> void> printSolution(>int> board[N][N])> {> >for> (>int> i = 0; i for (int j = 0; j if(board[i][j]) printf('Q '); else printf('. '); } printf('
'); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens bool isSafe(int board[N][N], int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row][i]) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) return false; // Überprüfen Sie die untere Diagonale auf der linken Seite auf (i = Zeile, j = Spalte; j>= 0 && i if (board[i][j]) return false; return true; } // Eine rekursive Dienstprogrammfunktion zum Lösen von N // Queen-Problem boolsolveNQUtil(int board[N][N], int col) { // Basisfall: Wenn alle Königinnen platziert sind // dann true zurückgeben if (col>= N) return true; // Betrachten Sie diese Spalte und versuchen Sie, // diese Königin nacheinander in allen Reihen zu platzieren for (int i = 0; i // Prüfen Sie, ob die Königin auf // board[i][col] platziert werden kann if (isSafe(board, i, col) ) { // Platziere diese Königin in Board[i][col] board[i][col] = 1; // Wiederholen, um die restlichen Damen zu platzieren if (solveNQUtil(board, col + 1)) return true; Wenn das Platzieren der Königin auf dem Brett[i][col] // nicht zu einer Lösung führt, dann // entferne die Königin vom Brett[i][col] board[i][col] = 0; // BACKTRACK } } // Wenn die Königin in keiner Zeile // dieser Spalte platziert werden kann, dann return false return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking. Sie verwendet hauptsächlichsolveNQUtil(), um // das Problem zu lösen . Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. boolsolveNQ() { 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('Lösung existiert nicht'); falsch zurückgeben; } printSolution(board); return true; } // Treiberprogramm zum Testen der obigen Funktion int main() {solvNQ(); 0 zurückgeben; } // Dieser Code wurde von Aditya Kumar (adityakumar129) beigesteuert> |
>
>
Java
// Java program to solve N Queen Problem using backtracking> public> class> NQueenProblem {> >final> int> N =>4>;> >// A utility function to print solution> >void> printSolution(>int> board[][])> >{> >for> (>int> i =>0>; i for (int j = 0; j if (board[i][j] == 1) System.out.print('Q '); else System.out.print('. '); } System.out.println(); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens boolean isSafe(int board[][], int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row][i] == 1) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j] == 1) return false; // Überprüfen Sie die untere Diagonale auf der linken Seite auf (i = Zeile, j = Spalte; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Eine rekursive Dienstprogrammfunktion um N zu lösen // Königinproblem booleansolveNQUtil(int board[][], int col) { // Basisfall: Wenn alle Königinnen platziert sind // dann true zurückgeben if (col>= N) return true; // Bedenken Sie dies Spalte und versuchen Sie, // diese Königin nacheinander in allen Zeilen zu platzieren for (int i = 0; i // Prüfen Sie, ob die Königin auf // board[i][col] platziert werden kann if (isSafe(board, i, col )) { // Platziere diese Dame in Board[i][col] board[i][col] = 1; // Wiederholen, um die restlichen Damen zu platzieren if (solveNQUtil(board, col + 1) == true) return true; // Wenn das Platzieren der Königin auf dem Brett[i][col] // nicht zu einer Lösung führt, dann // entferne die Königin vom Brett[i][col] board[i][col] = 0; BACKTRACK } } // Wenn die Königin in keiner Zeile // dieser Spalte platziert werden kann, dann return false; return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking // das Problem lösen. Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. booleansolveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { System.out.print('Lösung existiert nicht'); falsch zurückgeben; } printSolution(board); return true; } // Treiberprogramm zum Testen der oben genannten Funktion public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // Dieser Code wurde von Abhishek Shankhadhar beigesteuert> |
>
>
Python3
# Python3 program to solve N Queen> # Problem using backtracking> global> N> N>=> 4> def> printSolution(board):> >for> i>in> range>(N):> >for> j>in> range>(N):> >if> board[i][j]>=>=> 1>:> >print>(>'Q'>,end>=>' '>)> >else>:> >print>(>'.'>,end>=>' '>)> >print>()> # A utility function to check if a queen can> # be placed on board[row][col]. Note that this> # function is called when 'col' queens are> # already placed in columns from 0 to col -1.> # So we need to check only left side for> # attacking queens> def> isSafe(board, row, col):> ># Check this row on left side> >for> i>in> range>(col):> >if> board[row][i]>=>=> 1>:> >return> False> ># Check upper diagonal on left side> >for> i, j>in> zip>(>range>(row,>->1>,>->1>),> >range>(col,>->1>,>->1>)):> >if> board[i][j]>=>=> 1>:> >return> False> ># Check lower diagonal on left side> >for> i, j>in> zip>(>range>(row, N,>1>),> >range>(col,>->1>,>->1>)):> >if> board[i][j]>=>=> 1>:> >return> False> >return> True> def> solveNQUtil(board, col):> ># Base case: If all queens are placed> ># then return true> >if> col>>=> N:> >return> True> ># Consider this column and try placing> ># this queen in all rows one by one> >for> i>in> range>(N):> >if> isSafe(board, i, col):> ># Place this queen in board[i][col]> >board[i][col]>=> 1> ># Recur to place rest of the queens> >if> solveNQUtil(board, col>+> 1>)>=>=> True>:> >return> True> ># If placing queen in board[i][col> ># doesn't lead to a solution, then> ># queen from board[i][col]> >board[i][col]>=> 0> ># If the queen can not be placed in any row in> ># this column col then return false> >return> False> # This function solves the N Queen problem using> # Backtracking. It mainly uses solveNQUtil() to> # solve the problem. It returns false if queens> # cannot be placed, otherwise return true and> # placement of queens in the form of 1s.> # note that there may be more than one> # solutions, this function prints one of the> # feasible solutions.> def> solveNQ():> >board>=> [[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>]]> >if> solveNQUtil(board,>0>)>=>=> False>:> >print>(>'Solution does not exist'>)> >return> False> >printSolution(board)> >return> True> # Driver Code> if> __name__>=>=> '__main__'>:> >solveNQ()> # This code is contributed by Divyanshu Mehta> |
>
>
C#
// C# program to solve N Queen Problem> // using backtracking> using> System;> > class> GFG> {> >readonly> int> N = 4;> >// A utility function to print solution> >void> printSolution(>int> [,]board)> >{> >for> (>int> i = 0; i { for (int j = 0; j { if (board[i, j] == 1) Console.Write('Q '); else Console.Write('. '); } Console.WriteLine(); } } // A utility function to check if a queen can // be placed on board[row,col]. Note that this // function is called when 'col' queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens bool isSafe(int [,]board, int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row,i] == 1) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i,j] == 1) return false; // Überprüfe die untere Diagonale auf der linken Seite auf (i = Zeile, j = Spalte; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Eine rekursive Dienstprogrammfunktion für lösen N // Königinproblem boolsolveNQUtil(int [,]board, int col) { // Basisfall: Wenn alle Königinnen platziert sind // dann true zurückgeben if (col>= N) return true; // Betrachten Sie diese Spalte und Versuchen Sie, // diese Königin nacheinander in allen Reihen zu platzieren for (int i = 0; i { // Prüfen Sie, ob die Königin auf // board[i,col] platziert werden kann if (isSafe(board, i, col)) { // Platziere diese Königin in Board[i, Col] Board[i, Col] = 1; // Wiederholen, um die restlichen Damen zu platzieren if (solveNQUtil(board, col + 1) == true) return true; Wenn das Platzieren der Königin in Board[i,col] // nicht zu einer Lösung führt, dann // entferne die Königin von Board[i,col] board[i, col] = 0; // BACKTRACK } } // Wenn die queen kann in keiner Zeile // dieser Spalte platziert werden, dann return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking. Sie verwendet hauptsächlich „solveNQUtil()“, um das Problem zu lösen. Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. boolsolveNQ() { int [,]board = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }}; if (solveNQUtil(board, 0) == false) { Console.Write('Lösung existiert nicht'); falsch zurückgeben; } printSolution(board); return true; } // Treibercode public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // Dieser Code wurde von Princi Singh beigesteuert> |
>
>
Javascript
> // JavaScript program to solve N Queen> // Problem using backtracking> const N = 4> function> printSolution(board)> {> >for>(let i = 0; i { for(let j = 0; j { if(board[i][j] == 1) document.write('Q ') else document.write('. ') } document.write('') } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens function isSafe(board, row, col) { // Check this row on left side for(let i = 0; i if(board[row][i] == 1) return false } // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) return false // Überprüfe die untere Diagonale auf der linken Seite auf (i = row, j = col; j>= 0 && i if (board[i] [j]) return false return true } functionsolveNQUtil(board, col){ // Basisfall: Wenn alle Damen platziert sind // dann return true if(col>= N) return true // Betrachten Sie diese Spalte und versuchen Sie, sie zu platzieren / / diese Königin in allen Reihen nacheinander for(let i=0;i if(isSafe(board, i, col)==true){ // Platziere diese Königin in board[i][col] board[i][ col] = 1 // wiederkehren, um den Rest der Damen zu platzieren if(solveNQUtil(board, col + 1) == true) return true // Wenn das Platzieren der Dame in Board[i][col // nicht zu a führt Lösung, dann // Königin aus Board[i][col] Board[i][col] = 0 } } // wenn die Königin in keiner Zeile // dieser Spalte platziert werden kann, col then return false return false } / / Diese Funktion löst das N-Queen-Problem mithilfe von // Backtracking. Sie verwendet hauptsächlich „solveNQUtil()“, um // das Problem zu lösen. Sie gibt „false“ zurück, wenn // „Queens“ nicht platziert werden können, andernfalls gibt sie „true“ und // die Platzierung von „Queens“ zurück 1s. // Beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. FunktionsolveNQ(){ let board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] if (solveNQUtil(board, 0) == false){ document.write('Lösung existiert nicht') return false } printSolution(board) return true } // TreibercodesolveNQ() // Dieser Code wird von Shinjanpatra beigesteuert> |
>
>Ausgabe
. . Q . Q . . . . . . Q . Q . .>
Zeitkomplexität: AN!)
Hilfsraum: AN2)
Weitere Optimierung in der Funktion is_safe():
Die Idee besteht nicht darin, jedes Element in der rechten und linken Diagonale zu überprüfen, sondern die Eigenschaft von Diagonalen zu nutzen:
- Die Summe von ich Und J ist konstant und eindeutig für jede rechte Diagonale, wobei ich ist die Reihe der Elemente und J ist der
Spalte von Elementen.- Der Unterschied zwischen ich Und J ist konstant und eindeutig für jede linke Diagonale, wobei ich Und J sind Zeile bzw. Spalte eines Elements.
Unten ist die Implementierung:
C++
// C++ program to solve N Queen Problem using backtracking> #include> using> namespace> std;> #define N 4> // ld is an array where its indices indicate row-col+N-1> // (N-1) is for shifting the difference to store negative> // indices> int> ld[30] = { 0 };> // rd is an array where its indices indicate row+col> // and used to check whether a queen can be placed on> // right diagonal or not> int> rd[30] = { 0 };> // Column array where its indices indicates column and> // used to check whether a queen can be placed in that> // row or not*/> int> cl[30] = { 0 };> // A utility function to print solution> void> printSolution(>int> board[N][N])> {> >for> (>int> i = 0; i for (int j = 0; j cout << ' ' << (board[i][j]==1?'Q':'.') << ' '; cout << endl; } } // A recursive utility function to solve N // Queen problem bool solveNQUtil(int board[N][N], int col) { // Base case: If all queens are placed // then return true if (col>= N) true zurückgeben; // Betrachten Sie diese Spalte und versuchen Sie, // diese Königin nacheinander in allen Zeilen zu platzieren for (int i = 0; i // Überprüfen Sie, ob die Königin auf // board[i][col] // platziert werden kann, um zu überprüfen, ob Eine Königin kann auf // Board[Zeile][Spalte] platziert werden. Wir müssen nur // ld[Zeile-Spalte+n-1] und rd[Zeile+Spalte] überprüfen, wobei // ld und rd für links und stehen right // diagonal bzw. if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Platziere diese Dame im Brett[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Wiederholen, um den Rest der Damen zu platzieren (solveNQUtil(board, col + 1)) return true; // Wenn das Platzieren der Königin auf dem Brett[i][col] // nicht zu einer Lösung führt, dann // entferne die Königin vom Brett[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Wenn die Königin nicht platziert werden kann row in // dieser Spalte col then return false return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking. Sie verwendet hauptsächlichsolveNQUtil(), um das Problem zu lösen. Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. boolsolveNQ() { 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) { cout<< 'Solution does not exist'; return false; } printSolution(board); return true; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> |
>
>
Java
// Java program to solve N Queen Problem using backtracking> import> java.util.*;> class> GFG {> >static> int> N =>4>;> >// ld is an array where its indices indicate row-col+N-1> >// (N-1) is for shifting the difference to store> >// negative indices> >static> int>[] ld =>new> int>[>30>];> >// rd is an array where its indices indicate row+col> >// and used to check whether a queen can be placed on> >// right diagonal or not> >static> int>[] rd =>new> int>[>30>];> >// Column array where its indices indicates column and> >// used to check whether a queen can be placed in that> >// row or not> >static> int>[] cl =>new> int>[>30>];> >// A utility function to print solution> >static> void> printSolution(>int> board[][])> >{> >for> (>int> i =>0>; i for (int j = 0; j System.out.printf(' %d ', board[i][j]); System.out.printf('
'); } } // A recursive utility function to solve N // Queen problem static boolean solveNQUtil(int board[][], int col) { // Base case: If all queens are placed // then return true if (col>= N) true zurückgeben; // Betrachten Sie diese Spalte und versuchen Sie, // diese Königin nacheinander in allen Zeilen zu platzieren for (int i = 0; i // Überprüfen Sie, ob die Königin auf // board[i][col] // platziert werden kann, um zu überprüfen, ob Eine Königin kann auf // Board[Zeile][Spalte] platziert werden. Wir müssen nur // ld[Zeile-Spalte+n-1] und rd[Zeile+Spalte] überprüfen, wobei // ld und rd für links und stehen right // diagonal bzw. if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Platziere diese Dame im Brett[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Wiederholen, um den Rest der Damen zu platzieren (solveNQUtil(board, col + 1)) return true; // Wenn das Platzieren der Königin auf dem Brett[i][col] // nicht zu einer Lösung führt, dann // entferne die Königin vom Brett[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Wenn die Königin nicht platziert werden kann row in // dieser Spalte col then return false return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking. Sie verwendet hauptsächlichsolveNQUtil(), um das Problem zu lösen. Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. statischer boolescher WertsolvNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0 } }; if (solveNQUtil(board, 0) == false) { System.out.printf('Lösung existiert nicht'); falsch zurückgeben; } printSolution(board); return true; } // Treibercode public static void main(String[] args) {solvNQ(); } } // Dieser Code wurde von Princi Singh beigesteuert> |
>
>
Python3
string jsonobject
# Python3 program to solve N Queen Problem using> # backtracking> N>=> 4> # ld is an array where its indices indicate row-col+N-1> # (N-1) is for shifting the difference to store negative> # indices> ld>=> [>0>]>*> 30> # rd is an array where its indices indicate row+col> # and used to check whether a queen can be placed on> # right diagonal or not> rd>=> [>0>]>*> 30> # Column array where its indices indicates column and> # used to check whether a queen can be placed in that> # row or not> cl>=> [>0>]>*> 30> # A utility function to print solution> def> printSolution(board):> >for> i>in> range>(N):> >for> j>in> range>(N):> >print>(board[i][j], end>=>' '>)> >print>()> # A recursive utility function to solve N> # Queen problem> def> solveNQUtil(board, col):> ># Base case: If all queens are placed> ># then return True> >if> (col>>=> N):> >return> True> ># Consider this column and try placing> ># this queen in all rows one by one> >for> i>in> range>(N):> ># Check if the queen can be placed on board[i][col]> ># To check if a queen can be placed on> ># board[row][col] We just need to check> ># ld[row-col+n-1] and rd[row+coln]> ># where ld and rd are for left and> ># right diagonal respectively> >if> ((ld[i>-> col>+> N>-> 1>] !>=> 1> and> >rd[i>+> col] !>=> 1>)>and> cl[i] !>=> 1>):> ># Place this queen in board[i][col]> >board[i][col]>=> 1> >ld[i>-> col>+> N>-> 1>]>=> rd[i>+> col]>=> cl[i]>=> 1> ># Recur to place rest of the queens> >if> (solveNQUtil(board, col>+> 1>)):> >return> True> ># If placing queen in board[i][col]> ># doesn't lead to a solution,> ># then remove queen from board[i][col]> >board[i][col]>=> 0> # BACKTRACK> >ld[i>-> col>+> N>-> 1>]>=> rd[i>+> col]>=> cl[i]>=> 0> ># If the queen cannot be placed in> ># any row in this column col then return False> >return> False> # This function solves the N Queen problem using> # Backtracking. It mainly uses solveNQUtil() to> # solve the problem. It returns False if queens> # cannot be placed, otherwise, return True and> # prints placement of queens in the form of 1s.> # Please note that there may be more than one> # solutions, this function prints one of the> # feasible solutions.> def> solveNQ():> >board>=> [[>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> False> >printSolution(board)> >return> True> # Driver Code> if> __name__>=>=> '__main__'>:> >solveNQ()> # This code is contributed by SHUBHAMSINGH10> |
>
>
C#
// C# program to solve N Queen Problem using backtracking> using> System;> class> GFG {> >static> int> N = 4;> >// ld is an array where its indices indicate row-col+N-1> >// (N-1) is for shifting the difference to store> >// negative indices> >static> int>[] ld =>new> int>[30];> >// rd is an array where its indices indicate row+col> >// and used to check whether a queen can be placed on> >// right diagonal or not> >static> int>[] rd =>new> int>[30];> >// Column array where its indices indicates column and> >// used to check whether a queen can be placed in that> >// row or not> >static> int>[] cl =>new> int>[30];> >// A utility function to print solution> >static> void> printSolution(>int>[, ] board)> >{> >for> (>int> i = 0; i for (int j = 0; j Console.Write(' {0} ', board[i, j]); Console.Write('
'); } } // A recursive utility function to solve N // Queen problem static bool solveNQUtil(int[, ] board, int col) { // Base case: If all queens are placed // then return true if (col>= N) true zurückgeben; // Betrachten Sie diese Spalte und versuchen Sie, // diese Königin nacheinander in allen Zeilen zu platzieren for (int i = 0; i // Überprüfen Sie, ob die Königin auf // board[i,col] // platziert werden kann, um zu überprüfen, ob a Königin kann auf // Board[row,col] platziert werden. Wir müssen nur // ld[row-col+n-1] und rd[row+coln] überprüfen, wobei // ld und rd für links und rechts stehen / / Diagonale bzw. if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Platziere diese Königin in Board[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Wiederholen, um den Rest der Damen zu platzieren, wenn (solveNQUtil(board , col + 1)) return true; // Wenn das Platzieren der Königin in Board[i,col] // nicht zu einer Lösung führt, dann // entferne die Königin von Board[i,col] Board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Wenn die Königin in keiner Zeile // dieser Spalte platziert werden kann, col then return false return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking. Sie verwendet hauptsächlichsolveNQUtil(), um das Problem zu lösen. Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. static bool SolveNQ() { int[, ] Board = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { Console.Write('Lösung existiert nicht'); falsch zurückgeben; } printSolution(board); return true; } // Treibercode public static void Main(String[] args) {solvNQ(); } } // Dieser Code wurde von Rajput-Ji beigesteuert> |
>
>
Javascript
> >// JavaScript code to implement the approach> let N = 4;> > // ld is an array where its indices indicate row-col+N-1> // (N-1) is for shifting the difference to store negative> // indices> let ld =>new> Array(30);> > // rd is an array where its indices indicate row+col> // and used to check whether a queen can be placed on> // right diagonal or not> let rd =>new> Array(30);> > // Column array where its indices indicates column and> // used to check whether a queen can be placed in that> // row or not> let cl =>new> Array(30);> > // A utility function to print solution> function> printSolution( board)> {> >for> (let i = 0; i { for (let j = 0; j document.write(board[i][j] + ' '); document.write(' '); } } // A recursive utility function to solve N // Queen problem function solveNQUtil(board, col) { // Base case: If all queens are placed // then return true if (col>= N) true zurückgeben; // Betrachten Sie diese Spalte und versuchen Sie, // diese Königin nacheinander in allen Zeilen zu platzieren for (let i = 0; i { // Überprüfen Sie, ob die Königin auf // board[i][col] // platziert werden kann. Zur Überprüfung ob eine Dame auf // Board[Zeile][Spalte] platziert werden kann. Wir müssen nur // ld[Zeile-Spalte+n-1] und rd[Zeile+Spalte] überprüfen, wobei // ld und rd für links stehen bzw. rechts // Diagonale if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Platziere diese Königin auf dem Brett [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Wiederholen, um den Rest der Damen zu platzieren if (solveNQUtil(board, col + 1)) return true; // Wenn das Platzieren der Königin in Board[i][col] // nicht zu einer Lösung führt, dann // entferne die Königin von Board[i][col ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Wenn die Königin nicht platziert werden kann jede Zeile in // dieser Spalte col then return false return false; } // Diese Funktion löst das N-Queen-Problem mit // Backtracking. Sie verwendet hauptsächlichsolveNQUtil(), um das Problem zu lösen. Es gibt „false“ zurück, wenn die Damen // nicht platziert werden können, andernfalls wird „true“ zurückgegeben und // die Platzierung der Damen in Form von Einsen ausgegeben. // Bitte beachten Sie, dass es mehr als eine // Lösung geben kann. Diese Funktion gibt eine der // möglichen Lösungen aus. functionsolveNQ() { let board = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == false) { document.write('Lösung existiert nicht'); falsch zurückgeben; } printSolution(board); return true; } // Treibercode SolveNQ(); // Dieser Code wurde von sanjoy_62 beigesteuert.> |
>
>Ausgabe
. . Q . Q . . . . . . Q . Q . .>
Zeitkomplexität: AN!)
Hilfsraum: AN)
In Verbindung stehende Artikel:
- Drucken aller Lösungen im N-Queen-Problem