N QUEEN PROBLEM - TECHCODEVIEW.COM

Diskutovali sme Rytierska prehliadka a Potkan v bludisku problém skôr ako príklady problémov Backtracking. Poďme diskutovať o N Queen ako o ďalšom príklade problému, ktorý možno vyriešiť pomocou spätného sledovania.

Čo je problém N-Queen?

The N Kráľovná je problém s umiestnením N šachové kráľovné na an N x N šachovnicu, aby na seba nezaútočili dve dámy.

Nasleduje napríklad riešenie problému 4 kráľovien.

Očakávaný výstup je vo forme matice, ktorá má „ Q 's pre bloky, kde sú umiestnené dámy a prázdne miesta sú reprezentované '.' . Nasleduje napríklad výstupná matica pre vyššie uvedené riešenie 4-Queen.

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

Odporúčané: Vyriešte to ďalej PRAXE najprv pred prechodom na riešenie.

N Queen Problém pri používaní Backtracking :

Cieľom je umiestniť dámy jednu po druhej do rôznych stĺpcov, počnúc od stĺpca úplne vľavo. Keď umiestnime dámu do stĺpca, skontrolujeme, či nedošlo k stretu s už umiestnenými dámami. Ak v aktuálnom stĺpci nájdeme riadok, pre ktorý neexistuje kolízia, označíme tento riadok a stĺpec ako súčasť riešenia. Ak takýto rad nenájdeme kvôli stretom, potom cúvneme a vrátime sa falošný .

Nižšie je uvedený rekurzívny strom vyššie uvedeného prístupu:

Rekurzívny strom pre problém N Queen

Pri implementácii myšlienky postupujte podľa krokov uvedených nižšie:

Začnite v stĺpci úplne vľavo
Ak sú umiestnené všetky dámy, vráťte true
Vyskúšajte všetky riadky v aktuálnom stĺpci. Pre každý riadok urobte nasledovné.
- Ak sa dá dáma bezpečne umiestniť do tohto radu
  - Potom označte toto [riadok stĺpec] ako súčasť riešenia a rekurzívne skontrolujte, či umiestnenie kráľovnej sem vedie k riešeniu.
  - Ak umiestnite kráľovnú [riadok stĺpec] vedie k riešeniu a potom sa vráti pravda .
  - Ak umiestnenie kráľovnej nevedie k riešeniu, zrušte označenie [riadok stĺpec] potom sa vráťte a skúste iné riadky.
- Ak boli vyskúšané všetky riadky a nenájde sa platné riešenie, vráťte sa späť falošný spustiť backtracking.

Pre lepšiu vizualizáciu tohto postupu spätného sledovania si pozrite 4 Problém s kráľovnou .

Poznámka: Tento problém môžeme vyriešiť aj umiestnením kráľovien do radov.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++

// C++ program to solve N Queen Problem using backtracking> #include> #define N 4> using> namespace> std;> // A utility function to print solution> void> printSolution(> int> board[N][N])> {> > for> (> int>

i = 0; i   for (int j = 0; j   if(board[i][j])  cout  < < 'Q ';  else cout < <'. ';  printf('
');  } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens bool isSafe(int board[N][N], int row, int col) {  int i, j;  // Check this row on left side  for (i = 0; i   if (board[row][i])  return false;  // Check upper diagonal on left side  for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) return false;  // Skontrolujte spodnú uhlopriečku na ľavej strane, či neobsahuje (i = riadok, j = stĺpec; j>= 0 && i if (board[i][j]) return false; return true; } // Rekurzívna pomocná funkcia na riešenie N // Problém s kráľovnou bool solveNQUtil(int board[N][N], int col) { // základný prípad: Ak sú umiestnené všetky dámy // potom vráti true if (col>= N) return true // Uvažujme tento stĺpec a skúste umiestniť // túto dámu do všetkých radov jeden po druhom pre (int i = 0; i // Skontrolujte, či je možné dámu umiestniť na // board[i][col] if (isSafe(board, i, col) ) { // Umiestnite túto dámu na board[i][col] board[i][col] = 1 // zopakujte umiestnenie zvyšných dám if (solveNQUtil(board, col + 1)) return true; Ak umiestnenie dámy na board[i][col] // nevedie k riešeniu, potom // odstráňte dámu z boardu[i][col] board[i][col] = 0 // BACKTRACK } } // Ak nie je možné umiestniť kráľovnú do žiadneho riadku v // tomto stĺpci, potom vráťte hodnotu false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking Na // vyriešenie problému používa hlavne solveNQUtil(). . Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s. // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} };  if (solveNQUtil(doska, 0) == nepravda) { cout < < 'Solution does not exist';  return false;  }  printSolution(board);  return true; } // Driver program to test above function int main() {  solveNQ();  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

C

// C program to solve N Queen Problem using backtracking> #define N 4> #include> #include> // A utility function to print solution> void> printSolution(> int> board[N][N])> {> > for> (> int>

i = 0; i   for (int j = 0; j   if(board[i][j])  printf('Q ');  else  printf('. ');  }  printf('
');  } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens bool isSafe(int board[N][N], int row, int col) {  int i, j;  // Check this row on left side  for (i = 0; i   if (board[row][i])  return false;  // Check upper diagonal on left side  for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) return false;  // Skontrolujte spodnú uhlopriečku na ľavej strane, či neobsahuje (i = riadok, j = stĺpec; j>= 0 && i if (board[i][j]) return false; return true; } // Rekurzívna pomocná funkcia na riešenie N // Problém s kráľovnou bool solveNQUtil(int board[N][N], int col) { // Základný prípad: Ak sú všetky dámy umiestnené // potom vráti true if (col>= N) return true // Zvážte tento stĺpec a skúste umiestniť // túto dámu do všetkých radov jeden po druhom pre (int i = 0; i // Skontrolujte, či je možné dámu umiestniť na // board[i][col] if (isSafe(board, i, col) ) { // Umiestnite túto dámu na board[i][col] board[i][col] = 1 // Opakujte, ak chcete umiestniť zvyšné dámy, ak (solveNQUtil(board, col + 1)) return true; Ak umiestnenie dámy na board[i][col] // nevedie k riešeniu, potom // odstráňte dámu z boardu[i][col] board[i][col] = 0 // BACKTRACK } } // Ak sa kráľovná nedá umiestniť do žiadneho riadku v // tomto stĺpci, potom vráti false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking . Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s. // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} };  if (solveNQUtil(doska, 0) == false) { printf('Riešenie neexistuje');  vrátiť nepravdu;  } printSolution(board);  vrátiť true; } // Program ovládača na testovanie vyššie uvedenej funkcie int main() { solveNQ();  návrat 0; } // Tento kód prispel Aditya Kumar (adityakumar129)>

Java

// Java program to solve N Queen Problem using backtracking> public> class> NQueenProblem {> > final> int> N => 4> ;> > // A utility function to print solution> > void> printSolution(> int> board[][])> > {> > for> (> int> i => 0>

; i   for (int j = 0; j   if (board[i][j] == 1)  System.out.print('Q ');  else  System.out.print('. ');  }  System.out.println();  }  }  // A utility function to check if a queen can  // be placed on board[row][col]. Note that this  // function is called when 'col' queens are already  // placeed in columns from 0 to col -1. So we need  // to check only left side for attacking queens  boolean isSafe(int board[][], int row, int col)  {  int i, j;  // Check this row on left side  for (i = 0; i   if (board[row][i] == 1)  return false;  // Check upper diagonal on left side  for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j] == 1) return false;  // Skontrolujte dolnú uhlopriečku na ľavej strane, či neobsahuje (i = riadok, j = stĺpec; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Rekurzívna užitočná funkcia na vyriešenie N // Problém s kráľovnou boolean solveNQUtil(int board[][], int col) { // Základný prípad: Ak sú všetky dámy umiestnené // potom vráti true if (col>= N) return true // Zvážte toto stĺpec a skúste umiestniť // túto dámu do všetkých riadkov jeden po druhom pre (int i = 0; i // Skontrolujte, či je možné dámu umiestniť na // board[i][col] if (isSafe(board, i, col )) { // Umiestnite túto dámu na board[i][col] board[i][col] = 1 // Opakujte a umiestnite zvyšné dámy, ak (solveNQUtil(board, col + 1) == true) return; true // Ak umiestnenie dámy na board[i][col] // nevedie k riešeniu, potom // odstráňte dámu z boardu[i][col] board[i][col] = 0; BACKTRACK } } // Ak sa kráľovná nedá umiestniť do žiadneho riadku // tohto stĺpca, potom vráti false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking // vyrieš ten problém. Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s.  // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení.  boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };  if (solveNQUtil(doska, 0) == false) { System.out.print('Riešenie neexistuje');  vrátiť nepravdu;  } printSolution(doska);  vrátiť true;  } // Program ovládača na testovanie vyššie uvedenej funkcie public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem();  Queen.solveNQ();  } } // Tento kód prispel Abhishek Shankhadhar>

Python3

# Python3 program to solve N Queen> # Problem using backtracking> global> N> N> => 4> def> printSolution(board):> > for> i> in> range> (N):> > for> j> in> range> (N):> > if> board[i][j]> => => 1> :> > print> (> 'Q'> ,end> => ' '> )> > else> :> > print> (> '.'> ,end> => ' '> )> > print> ()> # A utility function to check if a queen can> # be placed on board[row][col]. Note that this> # function is called when 'col' queens are> # already placed in columns from 0 to col -1.> # So we need to check only left side for> # attacking queens> def> isSafe(board, row, col):> > # Check this row on left side> > for> i> in> range> (col):> > if> board[row][i]> => => 1> :> > return> False> > # Check upper diagonal on left side> > for> i, j> in> zip> (> range> (row,> -> 1> ,> -> 1> ),> > range> (col,> -> 1> ,> -> 1> )):> > if> board[i][j]> => => 1> :> > return> False> > # Check lower diagonal on left side> > for> i, j> in> zip> (> range> (row, N,> 1> ),> > range> (col,> -> 1> ,> -> 1> )):> > if> board[i][j]> => => 1> :> > return> False> > return> True> def> solveNQUtil(board, col):> > # Base case: If all queens are placed> > # then return true> > if> col>> => N:> > return> True> > # Consider this column and try placing> > # this queen in all rows one by one> > for> i> in> range> (N):> > if> isSafe(board, i, col):> > # Place this queen in board[i][col]> > board[i][col]> => 1> > # Recur to place rest of the queens> > if> solveNQUtil(board, col> +> 1> )> => => True> :> > return> True> > # If placing queen in board[i][col> > # doesn't lead to a solution, then> > # queen from board[i][col]> > board[i][col]> => 0> > # If the queen can not be placed in any row in> > # this column col then return false> > return> False> # This function solves the N Queen problem using> # Backtracking. It mainly uses solveNQUtil() to> # solve the problem. It returns false if queens> # cannot be placed, otherwise return true and> # placement of queens in the form of 1s.> # note that there may be more than one> # solutions, this function prints one of the> # feasible solutions.> def> solveNQ():> > board> => [[> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ]]> > if> solveNQUtil(board,> 0> )> => => False> :> > print> (> 'Solution does not exist'> )> > return> False> > printSolution(board)> > return> True> # Driver Code> if> __name__> => => '__main__'> :> > solveNQ()> # This code is contributed by Divyanshu Mehta>

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 (board[i,j] == 1) return false;  // Skontrolujte dolnú uhlopriečku na ľavej strane, či neobsahuje (i = riadok, j = stĺpec; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Rekurzívna pomocná funkcia na vyriešiť N // Problém s kráľovnou bool solveNQUtil(int [,]board, int col) { // Základný prípad: Ak sú všetky dámy umiestnené // potom vráti true if (col>= N) return true // Uvažujme tento stĺpec a skúste umiestniť // túto dámu do všetkých radov jeden po druhom pre (int i = 0; i { // Skontrolujte, či je možné dámu umiestniť na // board[i,col] if (isSafe(board, i, col)) { // Umiestnite túto dámu na board[i,col] board[i, col] = 1 // Opakujte, ak chcete umiestniť zvyšné dámy if (solveNQUtil(board, col + 1) == true) return true; Ak umiestnenie dámy na board[i,col] // nevedie k riešeniu, potom // odstráňte dámu z boardu[i,col] board[i, col] = 0 // BACKTRACK } } // Ak; queen nemožno umiestniť do žiadneho riadku v // tomto stĺpci col, potom return false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking Na // vyriešenie problému používa hlavne solveNQUtil (). Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s.  // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení.  bool solveNQ() { int [,]board = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }};  if (solveNQUtil(doska, 0) == false) { Console.Write('Riešenie neexistuje');  vrátiť nepravdu;  } printSolution(board);  vrátiť true;  } // Kód ovládača public static void Main(String []args) { GFG Queen = new GFG();  Queen.solveNQ();  } } // Tento kód prispel Prince 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 // Skontrolujte spodnú uhlopriečku na ľavej strane pre (i = riadok, j = stĺpec; j>= 0 && i if (board[i]) [j]) return false return true } function solveNQUtil(board, col){ // základný prípad: Ak sú umiestnené všetky kráľovné // potom vráti true if(col>= N) return true // Zvážte tento stĺpec a skúste umiestniť / / túto dámu vo všetkých radoch po jednom pre (nech i=0;i if(isSafe(board, i, col)==true){ // Umiestnite túto dámu na dosku[i][col] dosku[i][ stĺpec] = 1 // opakujte, aby ste umiestnili zvyšok dám if(solveNQUtil(board, col + 1) == true) return true // Ak umiestnenie dámy na board[i][col // nevedie k riešenie, potom // queen from board[i][col] board[i][col] = 0 } } // ak dámu nemožno umiestniť do žiadneho riadku v // tomto stĺpci col, potom vráti false return false } / / Táto funkcia rieši problém N Queen pomocou // Backtracking Používa hlavne solveNQUtil() na // vyriešenie problému. Vráti false, ak nie je možné umiestniť kráľovnú, inak vráti true a // umiestnenie kráľovien vo forme. 1 s. // všimnite si, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení. funkcia solveNQ(){ nech board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] ak (solveNQUtil(doska, 0) == false){ document.write('Riešenie neexistuje') return false } printSolution(board) return true } // Kód ovládača solveNQ() // Tento kód prispel shinjanpatra>

Výkon

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

Časová zložitosť: O(N!)
Pomocný priestor: O(N ² )

Ďalšia optimalizácia vo funkcii is_safe():

Cieľom nie je kontrolovať každý prvok v pravej a ľavej uhlopriečke, ale použiť vlastnosť uhlopriečok:

Súčet i a j je konštantná a jedinečná pre každú pravú uhlopriečku, kde i je rad prvkov a j je
stĺpec prvkov.

Rozdiel medzi i a j je konštantná a jedinečná pre každú ľavú uhlopriečku, kde i a j sú riadok a stĺpec prvku.

Nižšie je uvedená implementácia:

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) návrat true;  // Zvážte tento stĺpec a skúste umiestniť // túto dámu do všetkých riadkov jeden po druhom pre (int i = 0; i // Skontrolujte, či je možné dámu umiestniť na // board[i][col] // Skontrolujte, či dámu možno umiestniť na // board[riadok][stĺpec]. Potrebujeme len skontrolovať // ld[riadok-stĺpec+n-1] a rd[riadok+stĺpec], kde // ld a rd sú ľavé a vpravo // diagonála if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umiestnite túto dámu na dosku[ i][col] tabuľka[i][col] = 1 ld[i - stĺpec + N - 1] = rd[i + stĺpec] = cl[i] = 1 // Opakujte umiestnenie zvyšných dám; (solveNQUtil(board, col + 1)) return true // Ak umiestnenie dámy na hracej ploche[i][col] // nevedie k riešeniu, potom // odstráňte dámu z dosky[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Ak sa nedá dáma umiestniť do žiadneho; riadok v // tento stĺpec col then return false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking Na // vyriešenie problému používa hlavne solveNQUtil(). Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s. // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} };  if (solveNQUtil(doska, 0) == nepravda) { 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) návrat true;  // Zvážte tento stĺpec a skúste umiestniť // túto dámu do všetkých riadkov jeden po druhom pre (int i = 0; i // Skontrolujte, či je možné dámu umiestniť na // board[i][col] // Skontrolujte, či dámu možno umiestniť na // board[riadok][stĺpec]. Potrebujeme len skontrolovať // ld[riadok-stĺpec+n-1] a rd[riadok+stĺpec], kde // ld a rd sú ľavé a vpravo // diagonála if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umiestnite túto dámu na dosku[ i][col] tabuľka[i][col] = 1 ld[i - stĺpec + N - 1] = rd[i + stĺpec] = cl[i] = 1 // Opakujte umiestnenie zvyšných dám; (solveNQUtil(board, col + 1)) return true // Ak umiestnenie dámy na hracej ploche[i][col] // nevedie k riešeniu, potom // odstráňte dámu z dosky[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Ak sa nedá dáma umiestniť do žiadneho; riadok v // tento stĺpec col then return false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking Na // vyriešenie problému používa hlavne solveNQUtil(). Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s.  // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení.  static boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0} };  if (solveNQUtil(doska, 0) == false) { System.out.printf('Riešenie neexistuje');  vrátiť nepravdu;  } printSolution(board);  vrátiť true;  } // Kód ovládača public static void main(String[] args) { solveNQ();   } } // Tento kód prispel Prince 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>> => 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) návrat true;  // Zvážte tento stĺpec a skúste umiestniť // túto dámu do všetkých riadkov jeden po druhom pre (int i = 0; i // Skontrolujte, či je možné dámu umiestniť na // board[i,col] // Ak chcete skontrolovať, či a dámu je možné umiestniť na // board[riadok, stĺpec]. Potrebujeme len skontrolovať // ld[riadok-stĺpec+n-1] a rd[riadok+stĺpec], kde // ld a rd sú vľavo a vpravo / / diagonálne if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umiestnite túto dámu na dosku[i, col] tabuľka[i, stĺpec] = 1; ld[i - stĺpec + N - 1] = rd[i + stĺpec] = cl[i] = 1 // Opakujte umiestnenie zvyšných dám, ak (solveNQUtil(board , col + 1)) return true // Ak umiestnenie dámy na board[i,col] // nevedie k riešeniu, potom // odstráňte dámu z boardu[i,col] board[i, col]; = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Ak sa nedá dáma umiestniť do žiadneho riadku v // tomto stĺpci; potom return false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking Na // vyriešenie problému používa hlavne solveNQUtil(). Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s.  // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení.  static bool solveNQ() { int[, ] board = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} };  if (solveNQUtil(doska, 0) == false) { Console.Write('Riešenie neexistuje');  vrátiť nepravdu;  } printSolution(board);  vrátiť true;  } // Kód ovládača public static void Main(String[] args) { solveNQ();   } } // Tento kód prispel 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) návrat true;    // Zvážte tento stĺpec a skúste umiestniť // túto dámu do všetkých riadkov jeden po druhom pre (nech i = 0; i { // Skontrolujte, či je možné dámu umiestniť na // board[i][col] // Kontrola ak je možné umiestniť dámu na // board[riadok][stĺpec]. Potrebujeme len skontrolovať // ld[riadok-stĺpec+n-1] a rd[riadok+stĺpec], kde // ld a rd sú vľavo a vpravo // diagonálne if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umiestnite túto dámu na hraciu plochu [i][col] tabuľka[i][col] = 1 ld[i - stĺpec + N - 1] = rd[i + stĺpec] = cl[i] = 1 // Opakujte umiestnenie zvyšných dám; if (solveNQUtil(board, col + 1)) return true // Ak umiestnenie dámy na board[i][col] // nevedie k riešeniu, potom // odstráňte dámu z boardu[i][col]; ] board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Ak nie je možné umiestniť dámu; ľubovoľný riadok v // tomto stĺpci col potom vráti false return false } // Táto funkcia rieši problém N Queen pomocou // Backtracking Na // vyriešenie problému používa hlavne solveNQUtil(). Vracia hodnotu false, ak // nemožno umiestniť dámy, v opačnom prípade vráti hodnotu true a // vypíše umiestnenie dám v tvare 1s. // Upozorňujeme, že môže existovať viac ako jedno // riešení, táto funkcia vypíše jedno z // možných riešení. funkcia solveNQ() { nech board = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]];    if (solveNQUtil(doska, 0) == false) { document.write('Riešenie neexistuje');  vrátiť nepravdu;  } printSolution(board);  vrátiť true; } // Kód ovládača solveNQ(); // Tento kód pridal sanjoy_62.>

Výkon