Am discutat Turul cavalerului și Șobolan într-un labirint problema mai devreme ca exemple de probleme de backtracking. Să discutăm despre N Queen ca un alt exemplu de problemă care poate fi rezolvată folosind backtracking.

Ce este problema N-Queen?

The N Regina este problema plasării N regine de șah pe o N×N tabla de șah astfel încât să nu se atace două regine.

De exemplu, următoarea este o soluție pentru problema celor 4 Regine.

Rezultatul așteptat este sub forma unei matrice care are „ Q ‘s pentru blocurile în care sunt plasate matci și spațiile goale sunt reprezentate de '.' . De exemplu, următoarea este matricea de ieșire pentru soluția 4-Queen de mai sus.

. Q . .
. . . Q
Q . . .
. . Q .

N Queen Problemă cu utilizarea Întoarcerea înapoi :

Ideea este să așezi mătcile una câte una în coloane diferite, începând din coloana din stânga. Când plasăm o regină într-o coloană, verificăm dacă există confruntări cu damele deja plasate. În coloana curentă, dacă găsim un rând pentru care nu există ciocnire, marchem acest rând și coloană ca parte a soluției. Dacă nu găsim un astfel de rând din cauza ciocnirilor, atunci ne întoarcem înapoi fals .

Mai jos este arborele recursiv al abordării de mai sus:

Arborele recursiv pentru problema N Queen

10 la puterea lui 6

Urmați pașii menționați mai jos pentru a implementa ideea:

• Începeți în coloana din stânga
• Dacă toate reginele sunt plasate returnează adevărat
• Încercați toate rândurile din coloana curentă. Faceți următoarele pentru fiecare rând.
  • Dacă matca poate fi plasată în siguranță în acest rând
    • Apoi marcați asta [rând, coloană] ca parte a soluției și verificați recursiv dacă plasarea matcii aici duce la o soluție.
    • Dacă puneți regina înăuntru [rând, coloană] duce la o soluție apoi revine Adevărat .
    • Dacă plasarea reginei nu duce la o soluție, demarcați acest lucru [rând, coloană] apoi dați înapoi și încercați alte rânduri.
  • Dacă toate rândurile au fost încercate și soluția validă nu este găsită, reveniți fals pentru a declanșa întoarcerea.

Pentru o mai bună vizualizare a acestei abordări de backtracking, vă rugăm să consultați 4 problema reginei .

Notă: Putem rezolva această problemă și prin plasarea mătcilor pe rânduri.

Mai jos este implementarea abordării de mai sus:

C++

>

>

C

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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--) dacă (board[i][j] == 1) returnează fals;  // Verificați diagonala inferioară din partea stângă pentru (i = rând, j = col; j>= 0 && i dacă (board[i][j] == 1) returnează fals; returnează adevărat; } // O funcție recursivă de utilitate to solve N // Queen problem boolean solveNQUtil(int board[][], int col) { // Caz de bază: Dacă toate reginele sunt plasate // atunci returnează adevărat dacă (col>= N) returnează adevărat // Luați în considerare acest lucru; coloană și încercați să plasați // această damă pe toate rândurile unul câte unul pentru (int i = 0; i // Verificați dacă daca poate fi plasată pe // tabla[i][col] if (isSafe(board, i, col) )) { // Plasează această damă în placa[i][col] placa[i][col] = 1 // Recură pentru a plasa restul de dame if (solveNQUtil(board, col + 1) == true) return; true; // Dacă plasarea reginei în tablă[i][col] // nu duce la o soluție, atunci // elimină regina din tabla[i][col] = 0; BACKTRACK } } // Dacă regina nu poate fi plasată în nici un rând în // această coloană, returnează false returnare false } // Această funcție rezolvă problema N Queen folosind // În principal, folosește solveNQUtil (). // rezolva problema. Returnează false dacă // nu pot fi plasate regine, în caz contrar, returnează adevărat și // afișează plasarea reginelor sub formă de 1.  // Vă rugăm să rețineți că pot exista mai multe // soluții, această funcție imprimă una dintre // soluțiile fezabile.  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('Soluția nu există');  returnează fals;  } printSolution(board);  returnează adevărat;  } // Program driver pentru a testa funcția public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem();  Queen.solveNQ();  } } // Acest cod este contribuit de Abhishek Shankhadhar>
 
 
 
 
    
 
>
 
    
data curentă în java
 
>
 
 
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#
    
 
     
  
 
    
: în java
 
     
     
    
 
 
 
 
 
 // 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--) dacă (board[i,j] == 1) returnează fals;  // Verificați diagonala inferioară din partea stângă pentru (i = rând, j = col; j>= 0 && i dacă (board[i, j] == 1) returnează fals; returnează adevărat; } // O funcție utilitar recursivă la solve N // Queen problem bool solveNQUtil(int [,]board, int col) { // Caz de bază: Dacă toate reginele sunt plasate // atunci returnează adevărat dacă (col>= N) returnează adevărat // Luați în considerare această coloană; încercați să plasați // această damă pe toate rândurile unul câte unul pentru (int i = 0; i { // Verificați dacă dama poate fi plasată pe // tabla[i,col] if (isSafe(board, i, col)) { // Plasează această damă în placa[i,col] placa[i, col] = 1 // Recură pentru a plasa restul de dame dacă (solveNQUtil(board, col + 1) == true) returnează adevărat; Dacă plasarea reginei în tablă[i,col] // nu duce la o soluție, atunci // elimină regina din tabla[i,col] = 0 // BACKTRACK } } // Dacă; regina nu poate fi plasată în nici un rând în // această coloană, apoi returnează false returnare false } // Această funcție rezolvă problema N Queen folosind // Backtracking. Folosește în principal solveNQUtil () pentru a // rezolva problema. Returnează false dacă // nu pot fi plasate regine, în caz contrar, returnează adevărat și // afișează plasarea reginelor sub formă de 1.  // Vă rugăm să rețineți că pot exista mai multe // soluții, această funcție imprimă una dintre // soluțiile fezabile.  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('Soluția nu există');  returnează fals;  } printSolution(board);  returnează adevărat;  } // Cod driver public static void Main(String []args) { GFG Queen = new GFG();  Queen.solveNQ();  } } // Acest cod este contribuit de 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 // Verificați diagonala inferioară pe partea stângă pentru (i = rând, j = col; j>= 0 && i dacă (board[i]) [j]) returnează fals returnează adevărat } funcția solveNQUtil(board, col){ // caz de bază: Dacă toate reginele sunt plasate // atunci returnează true if(col>= N) return true // Luați în considerare această coloană și încercați să plasați / / această damă în toate rândurile unul câte unul pentru(let i=0;i if(isSafe(board, i, col)==true){ // Plasează această damă în bord[i][col] board[i][ col] = 1 // se repetă pentru a plasa restul reginelor if(solveNQUtil(board, col + 1) == true) return true // Dacă plasarea reginei la bord[i][col // nu duce la un soluție, atunci // regina din board[i][col] board[i][col] = 0 } } // dacă regina nu poate fi plasată în niciun rând în // această coloană col, atunci returnează false return false } / / Această funcție rezolvă problema N Queen folosind // Backtracking Folosește în principal solveNQUtil() pentru a // rezolva problema. 1s. // rețineți că pot exista mai multe // soluții, această funcție imprimă una dintre // soluțiile fezabile. funcția solveNQ(){ lasă bord = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] dacă (solveNQUtil(board, 0) == false){ document.write('Soluția nu există') return false } printSolution(board) return true } // Cod driver solveNQ() // Acest cod este contribuit de shinjanpatra>>>
 
 
 
 
    
 
> 
    
 . . Q . Q . . . . . . Q . Q . .>
 
    Complexitatea timpului:    PE!)  
    Spațiu auxiliar:    PE2)
 
    Optimizare suplimentară în funcția is_safe():    
  
 
Ideea este să nu verificați fiecare element din diagonala dreaptă și stângă, ci folosiți proprietatea diagonalelor:
 
 
Suma    i    și    j    este constantă și unică pentru fiecare diagonală dreaptă, unde    i    este rândul de elemente și    j    este  
coloană de elemente.
 
Diferența dintre    i    și    j    este constantă și unică pentru fiecare diagonală stângă, unde    i    și    j    sunt rândul și, respectiv, coloana elementului.
 
 
 
Mai jos este implementarea:
 
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) returnează adevărat;  // Luați în considerare această coloană și încercați să plasați // această damă pe toate rândurile unul câte unul pentru (int i = 0; i // Verificați dacă dama poate fi plasată // pe tabla[i][col] // Pentru a verifica dacă o regină poate fi plasată pe // bord[rând][col].Trebuie doar să verificăm // ld[row-col+n-1] și rd[row+coln] unde // ld și rd sunt pentru stânga și dreapta // respectiv diagonala if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plaseaza aceasta dama la bord[ i][col] board[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recură pentru a plasa rest de matci; (solveNQUtil(board, col + 1)) return true // Dacă plasarea reginei în board[i][col] // nu duce la o soluție, atunci // elimină regina din board[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Dacă regina nu poate fi pusă în niciuna; row in // această coloană, apoi returnează false return false } // Această funcție rezolvă problema N Queen folosind // Backtracking Folosește în principal solveNQUtil() pentru a // rezolva problema. Returnează false dacă // nu pot fi plasate regine, în caz contrar, returnează adevărat și // afișează plasarea reginelor sub formă de 1. // Vă rugăm să rețineți că pot exista mai multe // soluții, această funcție imprimă una dintre // soluțiile fezabile. bool solveNQ() { int bord[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) returnează adevărat;  // Luați în considerare această coloană și încercați să plasați // această damă pe toate rândurile unul câte unul pentru (int i = 0; i // Verificați dacă dama poate fi plasată // pe tabla[i][col] // Pentru a verifica dacă o regină poate fi plasată pe // bord[rând][col].Trebuie doar să verificăm // ld[row-col+n-1] și rd[row+coln] unde // ld și rd sunt pentru stânga și dreapta // respectiv diagonala if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plaseaza aceasta dama la bord[ i][col] board[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recură pentru a plasa rest de matci; (solveNQUtil(board, col + 1)) return true // Dacă plasarea reginei în board[i][col] // nu duce la o soluție, atunci // elimină regina din board[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Dacă regina nu poate fi pusă în niciuna; row in // această coloană, apoi returnează false return false } // Această funcție rezolvă problema N Queen folosind // Backtracking Folosește în principal solveNQUtil() pentru a // rezolva problema. Returnează false dacă // nu pot fi plasate regine, în caz contrar, returnează adevărat și // afișează plasarea reginelor sub formă de 1.  // Vă rugăm să rețineți că pot exista mai multe // soluții, această funcție imprimă una dintre // soluțiile fezabile.  static 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.printf('Soluția nu există');  returnează fals;  } printSolution(board);  returnează adevărat;  } // Cod driver public static void main(String[] args) { solveNQ();   } } // Acest cod este contribuit de Princi Singh>
 
 
 
 
    
 
>
 
    
 
>
 
 
Python3
    
 
     
  
 
    
 
     
     
    
 
mamta kulkarni
 
 
 
 
 # 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#
    
 
     
  
 
    
 
     
     
    
8 la 1 multiplexor
 
 
 
 
 
 // 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) returnează adevărat;  // Luați în considerare această coloană și încercați să plasați // această damă pe toate rândurile unul câte unul pentru (int i = 0; i // Verificați dacă dama poate fi plasată // pe tabla[i,col] // Pentru a verifica dacă un dama poate fi plasată pe // bord[row,col].Trebuie doar să verificăm // ld[row-col+n-1] și rd[row+coln] unde // ld și rd sunt pentru stânga și dreapta / / diagonala respectiv if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plaseaza aceasta dama in tabla[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recură pentru a plasa restul matcilor if (solveNQUtil(board; , col + 1)) return true // Dacă plasarea reginei în tablă[i,col] // nu duce la o soluție, atunci // eliminați dama de la bord[i,col] board[i, col]; = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Dacă regina nu poate fi plasată în nici un rând în // această coloană; then return false return false } // Această funcție rezolvă problema N Queen folosind // Backtracking Folosește în principal solveNQUtil() pentru a // rezolva problema. Returnează false dacă // nu pot fi plasate regine, în caz contrar, returnează adevărat și // afișează plasarea reginelor sub formă de 1.  // Vă rugăm să rețineți că pot exista mai multe // soluții, această funcție imprimă una dintre // soluțiile fezabile.  static bool solveNQ() { int[, ] bord = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };  if (solveNQUtil(board, 0) == false) { Console.Write('Soluția nu există');  returnează fals;  } printSolution(board);  returnează adevărat;  } // Cod driver public static void Main(String[] args) { solveNQ();   } } // Acest cod este contribuit de Rajput-Ji>
 
 
 
 
    
 
>
 
    
 
>
 
 
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) returnează adevărat;    // Luați în considerare această coloană și încercați să plasați // această damă pe toate rândurile unul câte unul pentru (let i = 0; i { // Verificați dacă dama poate fi plasată pe // tabla[i][col] // Pentru a verifica dacă o regină poate fi plasată pe // bord[rând][col].Trebuie doar să verificăm // ld[row-col+n-1] și rd[row+coln] unde // ld și rd sunt pentru stânga si dreapta // respectiv diagonala daca ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plaseaza aceasta dama in tabla [i][col] board[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; if (solveNQUtil(board, col + 1)) return true // Dacă plasarea reginei în board[i][col] // nu duce la o soluție, atunci // elimină regina din board[i][col; ] board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Dacă matca nu poate fi plasată; orice rând din // această coloană returnează false return false } // Această funcție rezolvă problema N Queen folosind // Backtracking. Folosește în principal solveNQUtil() pentru a // rezolva problema. Returnează false dacă // nu pot fi plasate regine, în caz contrar, returnează adevărat și // afișează plasarea reginelor sub formă de 1. // Vă rugăm să rețineți că pot exista mai multe // soluții, această funcție imprimă una dintre // soluțiile fezabile. 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('Soluția nu există');  returnează fals;  } printSolution(board);  returnează adevărat; } // Cod driver solveNQ(); // Acest cod este contribuit de sanjoy_62.>>>
 
 
 
 
    
 
> 
    
  . . Q . Q . . . . . . Q . Q . .>
 
    Complexitatea timpului:    PE!)  
    Spațiu auxiliar:    PE)
 
    Articole similare:    
 
 
 Tipărirea tuturor soluțiilor în N-Queen Problem