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

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>  
  
  
  
  
 
     
 
   
 
     
 
   
 
  
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>>>>     >  # 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--) 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>>>  
  
  
  
  
 
     
 
  
>   
 
     
 
      Complexitatea timpului:     PE!)   
    Spațiu auxiliar:     PE   2   )  
  
    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 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # 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>>>>     >  # 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) 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.>>>  
  
  
  
  
 
     
 
  
>   
 
     
 
      Complexitatea timpului:     PE!)   
    Spațiu auxiliar:     PE)  
  
    Articole similare:     
  
  
  Tipărirea tuturor soluțiilor în N-Queen Problem