Hem comentat La gira del cavaller i Rata en un laberint problema anterior com a exemples de problemes de retrocés. Parlem de N Queen com un altre problema d'exemple que es pot resoldre mitjançant el retrocés.

Què és el problema de N-Queen?

El N La reina és el problema de la col·locació N reines d'escacs en un N×N tauler d'escacs perquè no hi hagi dues reines que s'ataquin mútuament.

Per exemple, la següent és una solució per al problema de les 4 reines.

La sortida esperada té la forma d'una matriu que té ' Q 's per als blocs on es col·loquen les reines i els espais buits estan representats per ‘.’ . Per exemple, la següent és la matriu de sortida de la solució de 4 reines anterior.

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

N Queen Problema amb l'ús Fes marxa enrere :

La idea és col·locar les reines una per una en columnes diferents, començant per la columna més esquerra. Quan col·loquem una dama en una columna, comprovem si hi ha enfrontaments amb dames ja col·locades. A la columna actual, si trobem una fila per a la qual no hi ha xoc, marquem aquesta fila i columna com a part de la solució. Si no trobem una fila així a causa dels enfrontaments, retrocedim i tornem fals .

A continuació es mostra l'arbre recursiu de l'enfocament anterior:

Arbre recursiu per al problema N Queen

Seguiu els passos esmentats a continuació per implementar la idea:

• Comença a la columna de l'esquerra
• Si es col·loquen totes les dames, retorna cert
• Proveu totes les files de la columna actual. Feu el següent per a cada fila.
  • Si la reina es pot col·locar amb seguretat en aquesta fila
    • Aleshores marca això [fila, columna] com a part de la solució i comproveu recursivament si col·locar dama aquí condueix a una solució.
    • Si col·loqueu la reina [fila, columna] condueix a una solució i després torna veritat .
    • Si col·locar la reina no condueix a una solució, desmarqueu-ho [fila, columna] després feu marxa enrere i proveu altres files.
  • Si s'han provat totes les files i no es troba una solució vàlida, torneu fals per activar el retrocés.

Per a una millor visualització d'aquest enfocament de retrocés, consulteu 4 problema de la reina .

Nota: També podem resoldre aquest problema col·locant reines en files també.

A continuació es mostra la implementació de l'enfocament anterior:

C++

>

>

C

.tostring 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--) si (tauler[i][j] == 1) retorna fals;  // Comproveu la diagonal inferior del costat esquerre per (i = fila, j = col; j>= 0 && i si (tauler[i][j] == 1) retorna fals; retorna cert; } // Una funció d'utilitat recursiva resoldre N // Reina problema booleà solveNQUtil(int board[][], int col) { // Cas base: Si totes les reines es col·loquen // llavors retorna true si (col>= N) retorna cert // Considereu això columna i proveu de col·locar // aquesta dama a totes les files una per una per a (int i = 0; i // Comproveu si la dama es pot col·locar a // tauler[i][col] if (isSafe(board, i, col) )) { // Col·loqueu aquesta dama al tauler[i][col] tauler[i][col] = 1 // Repetiu per col·locar la resta de dames if (solveNQUtil(board, col + 1) == true) return; true // Si col·locar la reina al tauler[i][col] // no porta a una solució, // elimina la reina del tauler[i][col] = 0; BACKTRACK } } // Si la reina no es pot col·locar en cap fila d'aquesta columna, retorna false return false } // Aquesta funció resol el problema de N Queen utilitzant // Backtracking principalment // resol el problema. Retorna fals si // no es poden col·locar daines, en cas contrari, retorna true i // imprimeix la col·locació de les dames en forma d'1.  // Tingueu en compte que hi pot haver més d'una // solucions, aquesta funció imprimeix una de les // solucions factibles.  booleà 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 solució no existeix');  retornar fals;  } PrintSolution(board);  retornar veritat;  } // Programa de controladors per provar a sobre de la funció public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem();  Queen.solveNQ();  } } // Aquest codi és aportat per Abhishek Shankhadhar>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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--) si (tauler[i,j] == 1) retorna fals;  // Comproveu la diagonal inferior del costat esquerre per (i = fila, j = col; j>= 0 && i si (tauler[i, j] == 1) retorna fals; retorna vertader; } // Una funció d'utilitat recursiva a solve N // Queen problem bool solveNQUtil(int [,]board, int col) { // Cas base: Si totes les reines es col·loquen // llavors retorna true si (col>= N) retorna true // Considereu aquesta columna i prova de col·locar // aquesta dama a totes les files una per una per a (int i = 0; i { // Comprova si la dama es pot col·locar al // tauler[i,col] if (isSafe(board, i, col)) { // Col·loqueu aquesta dama al tauler[i, col] tauler[i, col] = 1 // Repetiu per col·locar la resta de dames si (solveNQUtil(board, col + 1) == true; Si col·locar la dama al tauler[i,col] // no condueix a una solució, aleshores // elimina la reina del tauler[i,col] = 0 // BACKTRACK } } // Si el queen no es pot col·locar en cap fila d'aquesta columna, després retorna false return false } // Aquesta funció soluciona el problema de N Queen utilitzant // Backtracking principalment per // resoldre el problema. Retorna fals si // no es poden col·locar daines, en cas contrari, retorna true i // imprimeix la col·locació de les dames en forma d'1.  // Tingueu en compte que hi pot haver més d'una // solucions, aquesta funció imprimeix una de les // solucions factibles.  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 solució no existeix');  retornar fals;  } PrintSolution(board);  retornar veritat;  } // Codi del controlador public static void Main(String []args) { GFG Queen = new GFG ();  Queen.solveNQ();  } } // Aquest codi és aportat per Princi Singh>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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--) si (tauler[i][j]) retorna fals // Comprova la diagonal inferior del costat esquerre per (i = fila, j = col·loqui; j>= 0 && i si (tauler[i]) [j]) retorna fals retorn vertader } funció solveNQUtil(board, col){ // cas base: si totes les reines es col·loquen // aleshores retorna true if (col>= N) retorna true // Considereu aquesta columna i proveu de col·locar // / aquesta dama a totes les files una per una per (let i=0;i if(isSafe(board, i, col)==true){ // Col·loqueu aquesta dama al tauler[i][col] tauler[i][i][col] col] = 1 // es repeteix per col·locar la resta de les dames if(solveNQUtil(board, col + 1) == true) return true // Si col·locar la dama al tauler[i][col // no condueix a un solució, aleshores // reina des del tauler[i][col] tauler[i][col] = 0 } } // si la reina no es pot col·locar en cap fila // aquesta columna col, llavors retorna fals retorn fals } / / Aquesta funció resol el problema de N Queen utilitzant // Backtracking Utilitza principalment solveNQUtil() per // resoldre el problema. 1s. // tingueu en compte que hi pot haver més d'una // solucions, aquesta funció imprimeix una de les // solucions factibles. funció solveNQ(){ deixa que tauler = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] si (solveNQUtil(board, 0) == false){ document.write('La solució no existeix') return false } printSolution(board) return true } // Codi del controlador solveNQ() // Aquest codi és aportat per shinjanpatra>>>
 
 
 
 
    
 
> 
    
 . . Q . Q . . . . . . Q . Q . .>
 
    Complexitat temporal:    O (N!)  
    Espai auxiliar:    O(N2)
 
    Optimització addicional a la funció is_safe():    
  
 
La idea no és comprovar tots els elements de la diagonal dreta i esquerra, sinó utilitzar la propietat de les diagonals:
 
 
La suma de    i    i    j    és constant i única per a cada diagonal dreta, on    i    és la fila d'elements i    j    és el  
columna d'elements.
 
La diferència entre    i    i    j    és constant i única per a cada diagonal esquerra, on    i    i    j    són fila i columna de l'element respectivament.
 
 
 
A continuació es mostra la implementació:
 
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) retorna cert;  // Considereu aquesta columna i proveu de col·locar // aquesta dama a totes les files una per una per a (int i = 0; i // Comproveu si la dama es pot col·locar // al tauler[i][col] // Per comprovar si una dama es pot col·locar al // tauler[fila][col]. Només hem de comprovar // ld[fila-col+n-1] i rd[fila+coln] on // ld i rd són per a l'esquerra i dreta // diagonal respectivament si ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posa aquesta dama al tauler[ i][col] tauler[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recorre per col·locar la resta de les dames; (solveNQUtil(board, col + 1)) return true // Si col·locar la dama al tauler[i][col] // no porta a una solució, aleshores // elimina la dama del tauler[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Si la dama no es pot posar en cap fila a // aquesta columna coll retorna fals retorn fals } // Aquesta funció resol el problema de N Queen utilitzant // el seguiment principalment utilitza solveNQUtil() per // resoldre el problema. Retorna fals si // no es poden col·locar daines, en cas contrari, retorna true i // imprimeix la col·locació de les dames en forma d'1. // Tingueu en compte que hi pot haver més d'una // solucions, aquesta funció imprimeix una de les // solucions factibles. bool solveNQ() { int tauler[N][N] = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0 } };  if (solveNQUtil(tauler, 0) == fals) { 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
    
 
     
  
Lògica de 1r ordre
 
    
 
     
     
    
 
 
 
 
 
 // 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) retorna cert;  // Considereu aquesta columna i proveu de col·locar // aquesta dama a totes les files una per una per a (int i = 0; i // Comproveu si la dama es pot col·locar // al tauler[i][col] // Per comprovar si una dama es pot col·locar al // tauler[fila][col]. Només hem de comprovar // ld[fila-col+n-1] i rd[fila+coln] on // ld i rd són per a l'esquerra i dreta // diagonal respectivament si ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posa aquesta dama al tauler[ i][col] tauler[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recorre per col·locar la resta de les dames; (solveNQUtil(board, col + 1)) return true // Si col·locar la dama al tauler[i][col] // no porta a una solució, aleshores // elimina la dama del tauler[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Si la dama no es pot posar en cap fila a // aquesta columna col·la després retorna fals retorn fals } // Aquesta funció resol el problema de N Queen utilitzant // el seguiment principalment utilitza solveNQUtil() per // resoldre el problema. Retorna fals si // no es poden col·locar daines, en cas contrari, retorna true i // imprimeix la col·locació de les dames en forma d'1.  // Tingueu en compte que hi pot haver més d'una // solucions, aquesta funció imprimeix una de les // solucions factibles.  solveNQ booleà estàtic () { 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 solució no existeix');  retornar fals;  } PrintSolution(board);  retornar veritat;  } // Codi del controlador public static void main(String[] args) { solveNQ();   } } // Aquest codi és aportat per Princi Singh>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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) retorna cert;  // Considereu aquesta columna i proveu de col·locar // aquesta dama a totes les files una per una per (int i = 0; i // Comproveu si la dama es pot col·locar // al tauler[i,col] // Per comprovar si un la reina es pot col·locar al // tauler[fila, col]. Només hem de comprovar // ld[fila-col+n-1] i rd[fila+coln] on // ld i rd són per a l'esquerra i la dreta // / diagonal respectivament si ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posa aquesta dama al tauler[i, col] tauler[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recorre per col·locar la resta de les dames if (solveNQUtil; , col + 1)) retorna true // Si col·locar la dama al tauler[i,col] // no porta a una solució, aleshores // elimina la reina del tauler[i,col][i, col]; = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Si la dama no es pot col·locar en cap fila d'aquesta columna; then return false return false } // Aquesta funció resol el problema de N Queen utilitzant // Backtracking Utilitza principalment solveNQUtil() per // resoldre el problema. Retorna fals si // no es poden col·locar daines, en cas contrari, retorna true i // imprimeix la col·locació de les dames en forma d'1.  // Tingueu en compte que hi pot haver més d'una // solucions, aquesta funció imprimeix una de les // solucions factibles.  static bool solveNQ() { int[, ] tauler = { {0, 0, 0, 0 }, {0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0}};  if (solveNQUtil(board, 0) == false) { Console.Write('La solució no existeix');  retornar fals;  } PrintSolution(board);  retornar veritat;  } // Codi del controlador public static void Main(String[] args) { solveNQ();   } } // Aquest codi és aportat per Rajput-Ji>
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
actriu de cinema kajal
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > >// 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) retorna cert;    // Considereu aquesta columna i proveu de col·locar // aquesta dama a totes les files una per una per a (deixar i = 0; i { // Comproveu si la dama es pot col·locar // al tauler[i][col] // Per comprovar si es pot col·locar una dama al // tauler[fila][col].Només hem de comprovar // ld[fila-col+n-1] i rd[fila+coln] on // ld i rd són per a l'esquerra i dreta // diagonal respectivament si ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posa aquesta dama al tauler [i][col] tauler[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recorreu a la resta de les dames if (solveNQUtil(board, col + 1)) return true // Si col·locar la dama al tauler[i][col] // no condueix a una solució, aleshores // elimina la dama del tauler[i][col; ] tauler[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Si la dama no es pot col·locar qualsevol fila en // aquesta columna retorna fals retorn fals } // Aquesta funció resol el problema de N Queen utilitzant // el seguiment enrere, utilitza principalment solveNQUtil() per // resoldre el problema. Retorna false si // no es poden col·locar daines, en cas contrari, retorna true i // imprimeix la col·locació de les dames en forma d'1. // Tingueu en compte que hi pot haver més d'una // solucions, aquesta funció imprimeix una de les // solucions factibles. funció 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 solució no existeix');  retornar fals;  } printSolution(tauler);  retornar veritat; } // Codi del controlador solveNQ(); // Aquest codi és aportat per sanjoy_62.>>>
 
 
 
 
    
 
> 
    
  . . Q . Q . . . . . . Q . Q . .>
 
    Complexitat temporal:    O (N!)  
    Espai auxiliar:    O(N)
 
    Articles relacionats:    
 
 
 Impressió de totes les solucions a N-Queen Problem