Nous avons discuté La tournée des chevaliers et Rat dans un labyrinthe problème plus tôt comme exemples de problèmes de retour en arrière. Discutons de N Queen comme un autre exemple de problème qui peut être résolu en utilisant le retour en arrière.
Quel est le problème N-Queen ?
Le N La reine est le problème du placement N les reines d'échecs sur un N×N échiquier afin que deux reines ne s'attaquent pas.
Par exemple, ce qui suit est une solution au problème des 4 reines.
Le résultat attendu se présente sous la forme d’une matrice qui a « Q C'est pour les blocs où sont placées les reines et les espaces vides sont représentés par '.' . Par exemple, ce qui suit est la matrice de sortie pour la solution 4-Queen ci-dessus.
Recommandé : veuillez le résoudre sur PRATIQUE d'abord, avant de passer à la solution.. Q. .
. . . Q
Q. . .
. . Q.
N Queen Problème d'utilisation Retour en arrière :
L’idée est de placer les reines une à une dans différentes colonnes, en commençant par la colonne la plus à gauche. Lorsque nous plaçons une reine dans une colonne, nous vérifions les conflits avec les reines déjà placées. Dans la colonne actuelle, si nous trouvons une ligne pour laquelle il n’y a pas de conflit, nous marquons cette ligne et cette colonne comme faisant partie de la solution. Si nous ne trouvons pas une telle dispute en raison d'affrontements, alors nous faisons marche arrière et revenons FAUX .
Vous trouverez ci-dessous l'arbre récursif de l'approche ci-dessus :
Arbre récursif pour le problème N Queen
Suivez les étapes mentionnées ci-dessous pour mettre en œuvre l'idée :
- Commencez dans la colonne la plus à gauche
- Si toutes les reines sont placées, retourne vrai
- Essayez toutes les lignes de la colonne actuelle. Faites ce qui suit pour chaque ligne.
- Si la reine peut être placée en toute sécurité dans cette rangée
- Alors marque ceci [ligne, colonne] dans le cadre de la solution et vérifiez récursivement si placer la reine ici conduit à une solution.
- Si vous placez la reine dans [ligne, colonne] mène à une solution puis revient vrai .
- Si placer la reine ne mène pas à une solution, décochez ceci [ligne, colonne] puis revenez en arrière et essayez d’autres lignes.
- Si toutes les lignes ont été essayées et qu'une solution valide n'est pas trouvée, retournez FAUX pour déclencher un retour en arrière.
- Si la reine peut être placée en toute sécurité dans cette rangée
Pour une meilleure visualisation de cette approche de retour en arrière, veuillez vous référer Problème des 4 reines .
Note: Nous pouvons également résoudre ce problème en plaçant les reines en rangées.
caractéristiques d'une série panda
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
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; // Vérifiez la diagonale inférieure sur le côté gauche pour (i = row, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Une fonction utilitaire récursive pour résoudre N // Problème de reine bool solveNQUtil(int board[N][N], int col) { // cas de base : si toutes les reines sont placées // alors renvoie true if (col>= N) return true ; // Considérez cette colonne ; et essayez de placer // cette reine dans toutes les lignes une par une pour (int i = 0; i // Vérifiez si la reine peut être placée sur // board[i][col] if (isSafe(board, i, col) ) { // Placer cette reine dans board[i][col] board[i][col] = 1; // se reproduit pour placer le reste des reines if (solveNQUtil(board, col + 1)) return true; Si placer la reine dans board[i][col] // ne mène pas à une solution, alors // supprime la reine de board[i][col] board[i][col] = 0; // BACKTRACK } } // Si la reine ne peut être placée dans aucune ligne de // cette colonne col alors return false return false; } // Cette fonction résout le problème de N Queen en utilisant // le backtracking. . Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. bool solveNQ() { 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; // Vérifiez la diagonale inférieure sur le côté gauche pour (i = row, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Une fonction utilitaire récursive pour résoudre N // Problème de reine bool solveNQUtil(int board[N][N], int col) { // Cas de base : si toutes les reines sont placées // alors renvoie true if (col>= N) return true ; // Considérez cette colonne ; et essayez de placer // cette reine dans toutes les lignes une par une pour (int i = 0; i // Vérifiez si la reine peut être placée sur // board[i][col] if (isSafe(board, i, col) ) { // Placez cette reine dans board[i][col] board[i][col] = 1; // Répétez pour placer le reste des reines if (solveNQUtil(board, col + 1)) return true; Si placer la reine dans board[i][col] // ne mène pas à une solution, alors // supprime la reine de board[i][col] board[i][col] = 0; // BACKTRACK } } // Si la reine ne peut être placée dans aucune ligne de // cette colonne col alors return false return false; } // Cette fonction résout le problème de N Queen en utilisant // le backtracking. . Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. bool solveNQ() { 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('La solution n'existe pas'); retourner faux ; } printSolution(tableau); renvoie vrai ; } // Programme pilote pour tester la fonction ci-dessus int main() { solveNQ(); renvoie 0 ; } // Ce code est contribué par Aditya Kumar (adityakumar129)> |
>
>
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; // Vérifiez la diagonale inférieure sur le côté gauche pour (i = row, j = col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Une fonction utilitaire récursive pour résoudre le problème de N // Reine boolean solveNQUtil(int board[][], int col) { // Cas de base : si toutes les reines sont placées // alors renvoie true if (col>= N) return true ; // Considérez ceci ; colonne et essayez de placer // cette reine dans toutes les lignes une par une pour (int i = 0; i // Vérifiez si la reine peut être placée sur // board[i][col] if (isSafe(board, i, col )) { // Placez cette reine dans board[i][col] board[i][col] = 1; // Répétez pour placer le reste des reines if (solveNQUtil(board, col + 1) == true) return true; // Si placer la reine dans board[i][col] // ne mène pas à une solution alors // supprime la reine de board[i][col] board[i][col] = 0; BACKTRACK } } // Si la reine ne peut être placée dans aucune ligne de // cette colonne col, alors return false return false; } // Cette fonction résout le problème de N Queen en utilisant // Backtracking. // résoudre le problème. Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. boolean solveNQ() { 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('La solution n'existe pas'); retourner faux ; } printSolution(tableau); renvoie vrai ; } // Programme pilote pour tester la fonction ci-dessus public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Reine.solveNQ(); } } // Ce code est fourni par Abhishek Shankhadhar> |
>
>
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> |
>
différence entre deux chaînes python
>
C#
chaîne en date
// 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 ; // Vérifiez la diagonale inférieure sur le côté gauche pour (i = row, j = col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Une fonction utilitaire récursive pour résoudre N // Problème de reine bool solveNQUtil(int [,]board, int col) { // Cas de base : si toutes les reines sont placées // alors renvoie true if (col>= N) return true // Considérez cette colonne et essayez de placer // cette reine dans toutes les lignes une par une pour (int i = 0; i { // Vérifiez si la reine peut être placée sur // board[i,col] if (isSafe(board, i, col)) { // Placez cette reine dans board[i,col] board[i, col] = 1; // Répétez pour placer le reste des reines if (solveNQUtil(board, col + 1) == true) return true; Si placer la reine dans le tableau[i,col] // ne mène pas à une solution alors // supprime la reine du tableau[i,col] board[i, col] = 0; // BACKTRACK } } // Si le queen ne peut être placé dans aucune ligne de // cette colonne col, puis return false return false; } // Cette fonction résout le problème de N Queen en utilisant // le backtracking. Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. 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('La solution n'existe pas'); retourner faux ; } printSolution(tableau); renvoie vrai ; } // Code du pilote public static void Main(String []args) { GFG Queen = new GFG(); Reine.solveNQ(); } } // Ce code est fourni par Princi Singh> |
>
>
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 // Vérifiez la diagonale inférieure sur le côté gauche pour (i = row, j = col; j>= 0 && i if (board[i] [j]) return false return true } function solveNQUtil(board, col){ // cas de base : si toutes les reines sont placées // alors renvoie true if(col>= N) return true // Considérez cette colonne et essayez de placer / / cette reine dans toutes les lignes une par une for(let i=0;i if(isSafe(board, i, col)==true){ // Placez cette reine dans board[i][col] board[i][ col] = 1 // revient pour placer le reste des reines if(solveNQUtil(board, col + 1) == true) return true // Si placer la reine dans board[i][col // ne conduit pas à un solution, alors // la reine de board[i][col] board[i][col] = 0 } } // si la reine ne peut être placée dans aucune ligne de // cette colonne col alors return false return false } / / Cette fonction résout le problème N Queen en utilisant // Backtracking. Elle utilise principalement solveNQUtil() pour // résoudre le problème. Elle renvoie false si les reines // ne peuvent pas être placées, sinon renvoie true et // le placement des reines sous la forme de. 1s. // notez qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. function solveNQ(){ let board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] si (solveNQUtil(board, 0) == false){ document.write('La solution n'existe pas') return false } printSolution(board) return true } // Code du pilote solveNQ() // Ce code est fourni par shinjanpatra> |
>
>Sortir
. . Q . Q . . . . . . Q . Q . .>
Complexité temporelle : SUR!)
Espace auxiliaire : SUR2)
Optimisation supplémentaire dans la fonction is_safe() :
L'idée n'est pas de vérifier chaque élément des diagonales droite et gauche, mais d'utiliser la propriété des diagonales :
- La somme de je et j est constant et unique pour chaque diagonale droite, où je est la rangée d'éléments et j est le
colonne d'éléments.- La différence entre je et j est constant et unique pour chaque diagonale gauche, où je et j sont respectivement la ligne et la colonne de l'élément.
Ci-dessous la mise en œuvre :
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) renvoie vrai ; // Considérez cette colonne et essayez de placer // cette reine dans toutes les lignes une par une pour (int i = 0; i // Vérifiez si la reine peut être placée sur // board[i][col] // Pour vérifier si une reine peut être placée sur // board[row][col]. Il suffit de vérifier // ld[row-col+n-1] et rd[row+coln] où // ld et rd sont pour la gauche et droite // diagonale respectivement if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placez cette reine dans le plateau[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Récupère pour placer le reste des reines si (solveNQUtil(board, col + 1)) return true; // Si placer la reine dans board[i][col] // ne mène pas à une solution, alors // supprime la reine du board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Si la reine ne peut être placée dans aucun row in // this column col then return false return false; } // Cette fonction résout le problème de N Queen en utilisant // Backtracking. Elle utilise principalement solveNQUtil() pour // résoudre le problème. Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. bool solveNQ() { 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) renvoie vrai ; // Considérez cette colonne et essayez de placer // cette reine dans toutes les lignes une par une pour (int i = 0; i // Vérifiez si la reine peut être placée sur // board[i][col] // Pour vérifier si une reine peut être placée sur // board[row][col]. Il suffit de vérifier // ld[row-col+n-1] et rd[row+coln] où // ld et rd sont pour la gauche et droite // diagonale respectivement if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placez cette reine dans le plateau[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Récupère pour placer le reste des reines si (solveNQUtil(board, col + 1)) return true; // Si placer la reine dans board[i][col] // ne mène pas à une solution, alors // supprime la reine du board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Si la reine ne peut être placée dans aucun row in // this column col then return false return false; } // Cette fonction résout le problème de N Queen en utilisant // Backtracking. Elle utilise principalement solveNQUtil() pour // résoudre le problème. Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. booléen statique solveNQ() { 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('La solution n'existe pas'); retourner faux ; } printSolution(tableau); renvoie vrai ; } // Code du pilote public static void main(String[] args) { solveNQ(); } } // Ce code est fourni par Princi Singh> |
>
>
Python3
logique propositionnelle
# 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) renvoie vrai ; // Considérez cette colonne et essayez de placer // cette reine dans toutes les lignes une par une pour (int i = 0; i // Vérifiez si la reine peut être placée sur // board[i,col] // Pour vérifier si un la reine peut être placée sur // board[row,col]. Il suffit de vérifier // ld[row-col+n-1] et rd[row+coln] où // ld et rd sont pour la gauche et la droite / / diagonale respectivement if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placez cette reine dans le board[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Répétez pour placer le reste des reines if (solveNQUtil(board , col + 1)) return true; // Si placer la reine dans le tableau[i,col] // ne mène pas à une solution, alors // supprime la reine du tableau[i,col] board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Si la reine ne peut être placée dans aucune ligne de // cette colonne col then return false return false; } // Cette fonction résout le problème de N Queen en utilisant // Backtracking. Elle utilise principalement solveNQUtil() pour résoudre le problème. Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. 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('La solution n'existe pas'); retourner faux ; } printSolution(tableau); renvoie vrai ; } // Code du pilote public static void Main(String[] args) { solveNQ(); } } // Ce code est contribué par Rajput-Ji> |
>
>
lire un fichier Excel en Java
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) renvoie vrai ; // Considérez cette colonne et essayez de placer // cette reine dans toutes les lignes une par une pour (let i = 0; i { // Vérifiez si la reine peut être placée sur // board[i][col] // Pour vérifier si une reine peut être placée sur // board[row][col]. Il suffit de vérifier // ld[row-col+n-1] et rd[row+coln] où // ld et rd sont à gauche et droite // diagonale respectivement if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placez cette reine sur le plateau [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Récupère pour placer le reste des reines if (solveNQUtil(board, col + 1)) return true; // Si placer la reine dans board[i][col] // ne mène pas à une solution, alors // supprime la reine du board[i][col] ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Si la reine ne peut pas être placée dans n'importe quelle ligne de // cette colonne col then return false return false; } // Cette fonction résout le problème de N Queen en utilisant // le backtracking. Il renvoie false si les reines // ne peuvent pas être placées, sinon, renvoie vrai et // imprime le placement des reines sous la forme de 1. // Veuillez noter qu'il peut y avoir plus d'une // solutions, cette fonction imprime l'une des // solutions réalisables. function solveNQ() { 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('La solution n'existe pas'); retourner faux ; } printSolution(tableau); renvoie vrai ; } // Code du pilote solveNQ(); // Ce code est contribué par sanjoy_62.> |
>
>Sortir
. . Q . Q . . . . . . Q . Q . .>
Complexité temporelle : SUR!)
Espace auxiliaire : SUR)
Articles Liés:
- Impression de toutes les solutions dans le problème N-Queen