Mes aptarėme Riterio turas ir Žiurkė labirinte problema anksčiau kaip „Backtracking“ problemų pavyzdžiai. Aptarkime „N Queen“ kaip kitą problemos pavyzdį, kurią galima išspręsti naudojant „backtracking“.

Kas yra N-Queen problema?

The N Karalienė yra vieta N šachmatų karalienės ant an N × N šachmatų lenta, kad dvi karalienės neužpultų viena kitos.

Pavyzdžiui, toliau pateikiamas 4 karalienės problemos sprendimas.

Tikėtina išvestis yra matricos forma, kuri turi „ K 's blokams, kuriuose dedamos karalienės, o tuščios vietos vaizduojamos '.' . Pavyzdžiui, toliau pateikta aukščiau pateikto 4-Queen sprendimo išvesties matrica.

. Q . .
. . . K
Q . . .
. . Q .

N Queen Problema naudojant Atsitraukimas :

Idėja yra sudėti karalienes po vieną į skirtingus stulpelius, pradedant nuo kairiojo stulpelio. Kai į stulpelį dedame karalienę, patikriname, ar nėra susidūrimų su jau padėtomis damomis. Jei esamame stulpelyje randame eilutę, kurioje nėra susidūrimo, pažymime šią eilutę ir stulpelį kaip sprendimo dalį. Jei dėl susirėmimų tokios eilės nerandame, tada atsitraukiame ir grįžtame klaidinga .

Žemiau pateikiamas aukščiau pateikto metodo rekursinis medis:

Rekursyvus medis N Queen problemai

Norėdami įgyvendinti idėją, atlikite toliau nurodytus veiksmus:

• Pradėkite kairiajame stulpelyje
• Jei padėtos visos karalienės, grąžinama tiesa
• Išbandykite visas dabartinio stulpelio eilutes. Atlikite šiuos veiksmus kiekvienai eilutei.
  • Jei karalienę galima saugiai pastatyti šioje eilėje
    • Tada pažymėkite tai [Eilute stulpelis] kaip sprendimo dalį ir rekursyviai patikrinkite, ar čia įdėjus karalienę gaunamas sprendimas.
    • Jei įdedate karalienę [Eilute stulpelis] veda prie sprendimo, tada grįžta tiesa .
    • Jei įdėjus karalienę nepavyksta rasti sprendimo, panaikinkite žymėjimą [Eilute stulpelis] tada grįžkite atgal ir išbandykite kitas eilutes.
  • Jei visos eilutės buvo išbandytos ir tinkamas sprendimas nerastas, grąžinkite klaidinga kad paskatintų atsitraukimą.

Norėdami geriau vizualizuoti šį atšaukimo metodą, žr 4 Karalienės problema .

Pastaba: Šią problemą taip pat galime išspręsti sudėdami dailes į eilutes.

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

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--) if (board[i][j] == 1) return false;  // Patikrinkite apatinę įstrižainę kairėje pusėje, ar nėra (i = eilutė, j = stulpelis; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Rekursyvinė naudingumo funkcija išspręsti N // Karalienės uždavinys loginis solveNQUtil(int board[][], int col) { // Bazinis dydis: Jei visos karalienės yra dedamos // tada grąžina true if (col>= N) return true // Apsvarstykite tai stulpelį ir pabandykite įdėti // šią karalienę visose eilutėse po vieną, kad būtų (int i = 0; i // Patikrinkite, ar karalienė gali būti dedama ant // lentos[i][col] if (isSafe(board, i, col )) { // Įdėkite šią valdovę į lentą[i][col] board[i][col] = 1 // Pakartokite, kad įdėtumėte likusias dailes if (solveNQUtil(lenta, col + 1) == true) return; tiesa // Jei įdėjus damą į lentą [i][col] // nepavyksta rasti sprendimo, tada // pašalinkite dama iš lentos[i][col] = 0; BACKTRACK } } // Jei karalienė negali būti dedama į jokią // šio stulpelio eilutę, grąžinkite false return false } // Ši funkcija išsprendžia N Queen problemą naudojant // Backtracking () to // išspręsti problemą. Grąžina false, jei karalienės // negali būti išdėstytos, priešingu atveju grąžina teisingą ir // atspausdina damų vietą 1 forma.  // Atkreipkite dėmesį, kad gali būti daugiau nei vienas // sprendimų, ši funkcija išspausdina vieną iš // įmanomų sprendimų.  loginis 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('Sprendimas neegzistuoja');  return false;  } printSolution(board);  grįžti tiesa;  } // Tvarkyklės programa, skirta patikrinti aukščiau pateiktą funkciją public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem();  Queen.solveNQ();  } } // Šį kodą sukūrė Abhishek Shankhadhar>
 
 
 
 
    
substring_index SQL
 
>
 
    
 
>
 
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python3 program to solve N Queen> # Problem using backtracking> global> N> N>=> 4> def> printSolution(board):> >for> i>in> range>(N):> >for> j>in> range>(N):> >if> board[i][j]>=>=> 1>:> >print>(>'Q'>,end>=>' '>)> >else>:> >print>(>'.'>,end>=>' '>)> >print>()> # A utility function to check if a queen can> # be placed on board[row][col]. Note that this> # function is called when 'col' queens are> # already placed in columns from 0 to col -1.> # So we need to check only left side for> # attacking queens> def> isSafe(board, row, col):> ># Check this row on left side> >for> i>in> range>(col):> >if> board[row][i]>=>=> 1>:> >return> False> ># Check upper diagonal on left side> >for> i, j>in> zip>(>range>(row,>->1>,>->1>),> >range>(col,>->1>,>->1>)):> >if> board[i][j]>=>=> 1>:> >return> False> ># Check lower diagonal on left side> >for> i, j>in> zip>(>range>(row, N,>1>),> >range>(col,>->1>,>->1>)):> >if> board[i][j]>=>=> 1>:> >return> False> >return> True> def> solveNQUtil(board, col):> ># Base case: If all queens are placed> ># then return true> >if> col>>>N:> >return> True> ># Consider this column and try placing> ># this queen in all rows one by one> >for> i>in> range>(N):> >if> isSafe(board, i, col):> ># Place this queen in board[i][col]> >board[i][col]>=> 1> ># Recur to place rest of the queens> >if> solveNQUtil(board, col>+> 1>)>=>=> True>:> >return> True> ># If placing queen in board[i][col> ># doesn't lead to a solution, then> ># queen from board[i][col]> >board[i][col]>=> 0> ># If the queen can not be placed in any row in> ># this column col then return false> >return> False> # This function solves the N Queen problem using> # Backtracking. It mainly uses solveNQUtil() to> # solve the problem. It returns false if queens> # cannot be placed, otherwise return true and> # placement of queens in the form of 1s.> # note that there may be more than one> # solutions, this function prints one of the> # feasible solutions.> def> solveNQ():> >board>=> [[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>]]> >if> solveNQUtil(board,>0>)>=>=> False>:> >print>(>'Solution does not exist'>)> >return> False> >printSolution(board)> >return> True> # Driver Code> if> __name__>=>=> '__main__'>:> >solveNQ()> # This code is contributed by Divyanshu Mehta> 
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# program to solve N Queen Problem> // using backtracking> using> System;> > class> GFG> {> >readonly> int> N = 4;> >// A utility function to print solution> >void> printSolution(>int> [,]board)> >{> >for> (>int> i = 0; i   {  for (int j = 0; j   {  if (board[i, j] == 1)  Console.Write('Q ');  else  Console.Write('. ');  }  Console.WriteLine();  }  }  // A utility function to check if a queen can  // be placed on board[row,col]. Note that this  // function is called when 'col' queens are already  // placeed in columns from 0 to col -1. So we need  // to check only left side for attacking queens  bool isSafe(int [,]board, int row, int col)  {  int i, j;  // Check this row on left side  for (i = 0; i   if (board[row,i] == 1)  return false;  // Check upper diagonal on left side  for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (lenta[i,j] == 1) return false;  // Patikrinkite apatinę įstrižainę kairėje pusėje, ar nėra (i = eilutė, j = stulpelis; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Rekursinė naudingumo funkcija išspręsti N // Queen problem bool solveNQUtil(int [,]board, int col) { // Bazinis dydis: Jei visos karalienės yra dedamos // tada grąžinkite true if (col>= N) return true // Apsvarstykite šį stulpelį ir pabandykite įdėti // šią karalienę visose eilutėse po vieną, kad būtų (int i = 0; i { // Patikrinkite, ar karalienė gali būti dedama ant // lentos[i,col] if (isSafe(board, i, col)) { // Įdėkite šią valdovę į lentą[i,col] lenta[i, col] = 1 // Pakartokite likusias dailes if (solveNQUtil(lenta, col + 1) == true) return true //; Jei įdėjus queen į lentą[i,col] // nepasiekiamas sprendimas, tada // pašalinkite damą iš lentos[i,col] lenta[i,col] = 0 // BACKTRACK } } // Jei queen negali būti dedama į jokią // šio stulpelio eilutę, tada grąžina false return false } // Ši funkcija išsprendžia N Queen problemą naudojant // Backtracking. Grąžina false, jei karalienės // negali būti išdėstytos, priešingu atveju grąžina teisingą ir // atspausdina damų vietą 1 forma.  // Atkreipkite dėmesį, kad gali būti daugiau nei vienas // sprendimų, ši funkcija išspausdina vieną iš // įmanomų sprendimų.  bool solveNQ() { int [,] lenta = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }};  if (solveNQUtil(lenta, 0) == false) { Console.Write('Sprendimas neegzistuoja');  return false;  } printSolution(board);  grįžti tiesa;  } // Tvarkyklės kodas public static void Main(String []args) { GFG Queen = new GFG();  Queen.solveNQ();  } } // Šį kodą sukūrė 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--) if (lenta[i][j]) return false // Patikrinkite apatinę įstrižainę kairėje pusėje (i = eilutė, j = stulpelis; j>= 0 && i if (lenta[i] [j]) return false return true } funkcija solveNQUtil(lenta, stulpelis){ // pagrindinės raidės: jei visos valdovės yra dedamos // tada grąžinkite true if(col>= N) return true // Apsvarstykite šį stulpelį ir pabandykite įdėti // / ši karalienė visose eilutėse po vieną for(let i=0;i if(isSafe(board, i, col)==true){ // Įdėkite šią karalienę į lentą[i][col] board[i][ col] = 1 // pasikartokite, kad būtų įdėtos likusios dama sprendimas, tada // karalienė iš lentos[i][col] lenta[i][col] = 0 } } // jei valdovė negali būti dedama į jokią eilutę // šio stulpelio stulpelyje, tada grąžinama false return false } / / Ši funkcija išsprendžia N Queen problemą, naudodama // Backtracking. Ji dažniausiai naudoja solveNQUtil(), kad // išspręstų problemą. Ji grąžina false, jei negalima įdėti karalienės, priešingu atveju grąžina true ir // damų išdėstymas. 1s. // atkreipkite dėmesį, kad gali būti daugiau nei vienas // sprendimų, ši funkcija išspausdina vieną iš // įmanomų sprendimų. funkcija solveNQ(){ tegul lenta = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] jei (solveNQUtil(board, 0) == false){ document.write('Sprendimas neegzistuoja') return false } printSolution(board) return true } // Tvarkyklės kodas solveNQ() // Šį kodą pateikė shinjanpatra>>
 
 
 
 
    
 
> 
konvertuoti int į eilutę c++
    
 . . Q . Q . . . . . . Q . Q . .>
 
    Laiko sudėtingumas:    O (N!)  
    Pagalbinė erdvė:    O (N2)
 
    Tolesnis funkcijos is_safe() optimizavimas:    
  
 
Idėja nėra tikrinti kiekvieno elemento dešinėje ir kairėje įstrižainėje, o naudoti įstrižainių savybę:
 
 
Suma    i    ir    j    yra pastovi ir unikali kiekvienai dešiniajai įstrižai, kur    i    yra elementų eilutė ir    j    yra  
elementų stulpelis.
 
Skirtumas tarp    i    ir    j    yra pastovus ir unikalus kiekvienai kairiajai įstrižai, kur    i    ir    j    yra atitinkamai elemento eilutė ir stulpelis.
 
 
 
Žemiau pateikiamas įgyvendinimas:
 
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) grąžinti teisingą;  // Apsvarstykite šį stulpelį ir pabandykite įdėti // šią karalienę visose eilutėse po vieną, kad būtų (int i = 0; i // Patikrinkite, ar karalienė gali būti dedama ant // lentos[i][col] // Norėdami patikrinti, ar karalienė gali būti dedama ant // lentos[eilutė][stulpelis]. Mums tereikia patikrinti // ld[row-coln+n-1] ir rd[row+coln], kur // ld ir rd reiškia kairę ir dešinė // atitinkamai įstrižainė if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Įdėkite šią karalienę į lentą[ i][col] lenta[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Pakartokite, kad būtų likusios karalienės; (solveNQUtil(lenta, stulpelis + 1)) return true // Jei įdėjus valdovę į lentą[i][col] // nepavyksta rasti sprendimo, tada // pašalinkite dama iš lentos[i][col]; lenta[i][col] = 0 // BACKTRACK ld[i - col eilutę // šio stulpelio stulpelis, tada grąžina false return false } // Ši funkcija išsprendžia N Queen problemą naudojant // Backtracking Ji dažniausiai naudoja solveNQUtil(), kad išspręstų problemą. Grąžina false, jei karalienės // negali būti išdėstytos, priešingu atveju grąžina teisingą ir // atspausdina damų vietą 1 forma. // Atkreipkite dėmesį, kad gali būti daugiau nei vienas // sprendimų, ši funkcija išspausdina vieną iš // įmanomų sprendimų. bool solveNQ() { int lenta[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };  if (spręstiNQUtil(lenta, 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
    
 
     
  
mylivecriclet
 
    
 
     
     
    
 
 
 
 
 
 // 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) grąžinti teisingą;  // Apsvarstykite šį stulpelį ir pabandykite įdėti // šią karalienę visose eilutėse po vieną, kad būtų (int i = 0; i // Patikrinkite, ar karalienė gali būti dedama ant // lentos[i][col] // Norėdami patikrinti, ar karalienė gali būti dedama ant // lentos[eilutė][stulpelis]. Mums tereikia patikrinti // ld[row-coln+n-1] ir rd[row+coln], kur // ld ir rd reiškia kairę ir dešinė // atitinkamai įstrižainė if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Įdėkite šią karalienę į lentą[ i][col] lenta[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Pakartokite, kad būtų likusios karalienės; (solveNQUtil(lenta, stulpelis + 1)) return true // Jei įdėjus valdovę į lentą[i][col] // nepavyksta rasti sprendimo, tada // pašalinkite dama iš lentos[i][col]; lenta[i][col] = 0 // BACKTRACK ld[i - col eilutę // šio stulpelio stulpelis, tada grąžina false return false } // Ši funkcija išsprendžia N Queen problemą naudojant // Backtracking Ji dažniausiai naudoja solveNQUtil(), kad išspręstų problemą. Grąžina false, jei karalienės // negali būti išdėstytos, priešingu atveju grąžina teisingą ir // atspausdina damų vietą 1 forma.  // Atkreipkite dėmesį, kad gali būti daugiau nei vienas // sprendimų, ši funkcija išspausdina vieną iš // įmanomų sprendimų.  statinis loginis solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0 } };  if (solveNQUtil(lenta, 0) == false) { System.out.printf('Sprendimas neegzistuoja');  return false;  } printSolution(board);  grįžti tiesa;  } // Tvarkyklės kodas public static void main(String[] args) { solveNQ();   } } // Šį kodą sukūrė 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) grąžinti teisingą;  // Apsvarstykite šį stulpelį ir pabandykite įdėti // šią karalienę visose eilutėse po vieną, kad būtų (int i = 0; i // Patikrinkite, ar karalienė gali būti dedama ant // lentos[i,col] // Norėdami patikrinti, ar karalienė gali būti dedama ant // lentos[eilutė,stulpelis]. Mums tereikia patikrinti // ld[eilutė-stulpelis+n-1] ir rd[eilutė+stulpelis], kur // ld ir rd yra kairėje ir dešinėje / / įstrižainė atitinkamai if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Įdėkite šią karalienę į lentą[i, col] lenta[i, col] = 1; ld[i - col , col + 1)) return true // Jei įdėjus damą į lentą[i,col] // nepavyksta rasti sprendimo, tada // pašalinkite dama iš lentos[i,col] board[i,col]; = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Jei karalienė negali būti dedama į jokią eilutę // šiame stulpelyje tada return false return false } // Ši funkcija išsprendžia N Queen problemą, naudodama // Backtracking. Ji dažniausiai naudoja solveNQUtil() problemai išspręsti. Grąžina false, jei karalienės // negali būti išdėstytos, priešingu atveju grąžina teisingą ir // atspausdina damų vietą 1 forma.  // Atkreipkite dėmesį, kad gali būti daugiau nei vienas // sprendimų, ši funkcija išspausdina vieną iš // įmanomų sprendimų.  statinis bool solveNQ() { int[, ] lenta = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };  if (solveNQUtil(lenta, 0) == false) { Console.Write('Sprendimas neegzistuoja');  return false;  } printSolution(board);  grįžti tiesa;  } // Tvarkyklės kodas public static void Main(String[] args) { solveNQ();   } } // Šį kodą sukūrė 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) grąžinti teisingą;    // Apsvarstykite šį stulpelį ir pabandykite įdėti // šią karalienę visose eilutėse po vieną (tegul i = 0; i { // Patikrinkite, ar karalienė gali būti dedama ant // lentos[i][col] // Norėdami patikrinti jei karalienė gali būti dedama ant // lentos[eilutė][stulpelis]. Mums tereikia patikrinti // ld[row-coln+n-1] ir rd[row+coln], kur // ld ir rd reiškia kairę ir dešinė // atitinkamai įstrižainė, jei ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Padėkite šią karalienę į lentą [i][col] lenta[i][col] = 1; ld[i - col if (solveNQUtil(lenta, stulpelis + 1)) return true // Jei įdėjus valdovę į lentą[i][col] // nepavyksta rasti sprendimo, tada // pašalinkite dama iš lentos[i][col; ] lenta[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0} } // Jei negalima įdėti karalienės; bet kuri eilutė // šio stulpelio stulpelyje, tada grąžina false return false } // Ši funkcija išsprendžia N Queen problemą naudojant // Backtracking. Grąžina false, jei karalienės // negali būti išdėstytos, priešingu atveju grąžina teisingą ir // atspausdina damų vietą 1 forma. // Atkreipkite dėmesį, kad gali būti daugiau nei vienas // sprendimų, ši funkcija išspausdina vieną iš // įmanomų sprendimų. function solveNQ() { tegul lenta = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]];    if (solveNQUtil(lenta, 0) == false) { document.write('Sprendimas neegzistuoja');  return false;  } printSolution(board);  grįžti tiesa; } // Tvarkyklės kodas solveNQ(); // Šį kodą sukūrė sanjoy_62.>>
 
 
 
 
    
 
> 
    
  . . Q . Q . . . . . . Q . Q . .>
 
    Laiko sudėtingumas:    O (N!)  
    Pagalbinė erdvė:    O(N)
 
    Susiję straipsniai:    
 
 
 Spausdinami visi N-Queen problemos sprendimai