Noi abbiamo discusso Il giro del cavaliere E Ratto in un labirinto problema in precedenza come esempi di problemi di backtracking. Parliamo di N Queen come un altro problema di esempio che può essere risolto utilizzando il backtracking.
Qual è il problema N-Queen?
IL N La regina è il problema del piazzamento N regine degli scacchi su un N×N scacchiera in modo che due regine non si attacchino a vicenda.
Ad esempio, la seguente è una soluzione per il problema delle 4 regine.
L'output atteso è sotto forma di una matrice che ha ' Q è per i blocchi in cui sono posizionate le regine e gli spazi vuoti sono rappresentati da '.' . Ad esempio, la seguente è la matrice di output per la soluzione a 4 regine di cui sopra.
Consigliato: risolverlo PRATICA innanzitutto, prima di passare alla soluzione.. Q . .
. . . Q
Q . . .
. . Q .
N Queen Problema nell'utilizzo Fare marcia indietro :
L'idea è di posizionare le regine una per una in colonne diverse, a partire dalla colonna più a sinistra. Quando posizioniamo una regina in una colonna, controlliamo la presenza di scontri con le regine già posizionate. Nella colonna corrente, se troviamo una riga per la quale non sono presenti conflitti, contrassegniamo questa riga e colonna come parte della soluzione. Se non troviamo tale riga a causa di scontri, torniamo indietro e torniamo falso .
Di seguito è riportato l'albero ricorsivo dell'approccio precedente:
Albero ricorsivo per il problema N Queen
Seguire i passaggi indicati di seguito per implementare l'idea:
- Inizia nella colonna più a sinistra
- Se vengono piazzate tutte le regine, restituisce vero
- Prova tutte le righe nella colonna corrente. Procedi come segue per ogni riga.
- Se la regina può essere posizionata in sicurezza in questa riga
- Allora segnalo [riga colonna] come parte della soluzione e controlla ricorsivamente se posizionare la regina qui porta a una soluzione.
- Se si inserisce la Regina [riga colonna] porta ad una soluzione e poi ritorna VERO .
- Se posizionare la regina non porta a una soluzione, deselezionalo [riga colonna] quindi torna indietro e prova altre righe.
- Se sono state provate tutte le righe e non è stata trovata una soluzione valida, restituire falso per innescare il backtracking.
- Se la regina può essere posizionata in sicurezza in questa riga
Per una migliore visualizzazione di questo approccio di backtracking, fare riferimento 4 Problema della regina .
Nota: Possiamo anche risolvere questo problema posizionando anche le regine in file.
Di seguito è riportata l’implementazione dell’approccio di cui sopra:
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--) se (board[i][j]) restituisce falso; // Controlla la diagonale inferiore sul lato sinistro per (i = riga, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Una funzione di utilità ricorsiva per risolvere N // Problema della regina boolsolveNQUtil(int board[N][N], int col) { // caso base: se tutte le regine sono posizionate // allora restituisce true if (col>= N) return true // Considera questa colonna e prova a posizionare // questa regina in tutte le righe una per una for (int i = 0; i // Controlla se la regina può essere posizionata su // board[i][col] if (isSafe(board, i, col) ) { // Posiziona questa regina in board[i][col] board[i][col] = 1; // ripeti per posizionare il resto delle regine if (solveNQUtil(board, col + 1)) return true; Se posizionare la regina in board[i][col] // non porta a una soluzione, allora // rimuovi la regina da board[i][col] board[i][col] = 0 // BACKTRACK } }; // Se la regina non può essere posizionata in nessuna riga in // questa colonna col allora return false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() per // risolvere il problema . Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. bool risolvereNQ() { int scheda[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)> |
>
>
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--) se (board[i][j]) restituisce falso; // Controlla la diagonale inferiore sul lato sinistro per (i = riga, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Una funzione di utilità ricorsiva per risolvere N // Problema della regina boolsolveNQUtil(int board[N][N], int col) { // Caso base: se tutte le regine sono posizionate // allora restituisce true if (col>= N) return true // Considera questa colonna e prova a posizionare // questa regina in tutte le righe una per una for (int i = 0; i // Controlla se la regina può essere posizionata su // board[i][col] if (isSafe(board, i, col) ) { // Posiziona questa regina in board[i][col] board[i][col] = 1; // Ripeti per posizionare il resto delle regine if (solveNQUtil(board, col + 1)) return true; Se posizionare la regina in board[i][col] // non porta a una soluzione, allora // rimuovi la regina da board[i][col] board[i][col] = 0 // BACKTRACK } }; // Se la regina non può essere posizionata in nessuna riga in // questa colonna col allora return false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() per // risolvere il problema . Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. bool risolvereNQ() { int scheda[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { printf('La soluzione non esiste'); restituire falso; } stampaSoluzione(scheda); restituisce vero; } // Programma driver per testare la funzione precedente int main() {solveNQ(); restituire 0; } // Questo codice è un contributo di Aditya Kumar (adityakumar129)> |
>
k il vicino più vicino
>
Giava
// 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) restituisce falso; // Controlla la diagonale inferiore sul lato sinistro per (i = riga, j = col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Una funzione di utilità ricorsiva per risolvere N // Problema della regina boolean solveNQUtil(int board[][], int col) { // Caso base: se tutte le regine sono posizionate // allora restituisce true if (col>= N) return true; colonna e prova a posizionare // questa regina in tutte le righe una per una for (int i = 0; i // Controlla se la regina può essere posizionata su // board[i][col] if (isSafe(board, i, col )) { // Posiziona questa regina in board[i][col] board[i][col] = 1; // Ripeti per posizionare il resto delle regine if (solveNQUtil(board, col + 1) == true) return true; // Se posizionare la regina in board[i][col] // non porta a una soluzione, allora // rimuovi la regina da board[i][col] board[i][col] = 0; BACKTRACK } } // Se la regina non può essere posizionata in nessuna riga in // questa colonna col, restituisce false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() to // risolvere il problema. Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. booleano risolvereNQ() { 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 soluzione non esiste'); restituire falso; } stampaSoluzione(scheda); restituisce vero; } // Programma driver per testare la funzione sopra public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Regina.solveNQ(); } } // Questo codice è un contributo di 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 (tavola[i,j] == 1) restituisce falso; // Controlla la diagonale inferiore sul lato sinistro per (i = riga, j = col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Una funzione di utilità ricorsiva per risolvere N // Problema della regina bool risolvereNQUtil(int [,]board, int col) { // Caso base: se tutte le regine sono posizionate // allora restituisce true if (col>= N) return true // Considera questa colonna e prova a posizionare // questa regina in tutte le righe una per una for (int i = 0; i { // Controlla se la regina può essere posizionata su // board[i,col] if (isSafe(board, i, col)) { // Posiziona questa regina in board[i,col] board[i, col] = 1; // Ripeti per posizionare il resto delle regine if (solveNQUtil(board, col + 1) == true) return true; Se posizionare la regina in board[i,col] // non porta a una soluzione allora // rimuovi la regina da board[i,col] board[i, col] = 0; // BACKTRACK } } // Se il queen non può essere posizionata in nessuna riga in // questa colonna col, then return false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() per // risolvere il problema. Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. bool risolvereNQ() { 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 soluzione non esiste'); restituire falso; } stampaSoluzione(scheda); restituisce vero; } // Codice driver public static void Main(String []args) { GFG Queen = new GFG(); Regina.solveNQ(); } } // Questo codice è un contributo di 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 // Controlla la diagonale inferiore sul lato sinistro per (i = riga, j = col; j>= 0 && i if (board[i] [j]) return false return true } function risolveNQUtil(board, col){ // caso base: Se tutte le regine sono posizionate // allora restituisce true if(col>= N) return true // Considera questa colonna e prova a posizionare / / questa regina in tutte le righe una per una for(let i=0;i if(isSafe(board, i, col)==true){ // Posiziona questa regina in board[i][col] board[i][ col] = 1 // ricorre per posizionare il resto delle regine if(solveNQUtil(board, col + 1) == true) return true // Se posizionare la regina in board[i][col // non porta a a soluzione, allora // regina da board[i][col] board[i][col] = 0 } } // se la regina non può essere posizionata in nessuna riga in // questa colonna col then return false return false } / / Questa funzione risolve il problema N Queen utilizzando // Backtracking. Utilizza principalmente findNQUtil() per // risolvere il problema. Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // il posizionamento delle regine sotto forma di 1 secondo // nota che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. funzione risolveNQ(){ lascia 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 soluzione non esiste') return false } printSolution(board) return true } // Codice driversolveNQ() // Questo codice è fornito da shinjanpatra> |
>
>Produzione
. . Q . Q . . . . . . Q . Q . .>
Complessità temporale: SU!)
Spazio ausiliario: SU2)
Ulteriore ottimizzazione nella funzione is_safe():
L'idea non è quella di controllare ogni elemento nella diagonale destra e sinistra, ma utilizzare invece la proprietà delle diagonali:
- La somma di io E J è costante e unico per ogni diagonale destra, dove io è la riga di elementi e J è il
colonna di elementi.- La differenza tra io E J è costante e unico per ogni diagonale sinistra, dove io E J sono rispettivamente la riga e la colonna dell'elemento.
Di seguito l'implementazione:
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) restituisce vero; // Considera questa colonna e prova a posizionare // questa regina in tutte le righe una per una per (int i = 0; i // Controlla se la regina può essere posizionata su // board[i][col] // Per verificare se una regina può essere posizionata su // board[row][col]. Dobbiamo solo controllare // ld[row-col+n-1] e rd[row+coln] dove // ld e rd stanno per left e right // diagonale rispettivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posiziona questa regina nel tabellone[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Ricorre per posizionare il resto delle regine se (solveNQUtil(board, col + 1)) return true // Se posizionare la regina nel board[i][col] // non porta a una soluzione, allora // rimuovi la regina dal board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Se la regina non può essere posizionata in nessuna riga in // questa colonna col then return false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() per // risolvere il problema. Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. bool risolvereNQ() { int scheda[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)> |
>
>
Giava
// 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) restituisce vero; // Considera questa colonna e prova a posizionare // questa regina in tutte le righe una per una per (int i = 0; i // Controlla se la regina può essere posizionata su // board[i][col] // Per verificare se una regina può essere posizionata su // board[row][col]. Dobbiamo solo controllare // ld[row-col+n-1] e rd[row+coln] dove // ld e rd stanno per left e right // diagonale rispettivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posiziona questa regina nel tabellone[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Ricorre per posizionare il resto delle regine se (solveNQUtil(board, col + 1)) return true // Se posizionare la regina nel board[i][col] // non porta a una soluzione, allora // rimuovi la regina dal board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Se la regina non può essere posizionata in nessuna riga in // questa colonna col then return false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() per // risolvere il problema. Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. booleano statico risolveNQ() { 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 soluzione non esiste'); restituire falso; } stampaSoluzione(scheda); restituisce vero; } // Codice driver public static void main(String[] args) {solveNQ(); } } // Questo codice è un contributo di 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>>=> 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) restituisce vero; // Considera questa colonna e prova a posizionare // questa regina in tutte le righe una per una per (int i = 0; i // Controlla se la regina può essere posizionata su // board[i,col] // Per verificare se a la regina può essere posizionata su // board[row,col]. Dobbiamo solo controllare // ld[row-col+n-1] e rd[row+coln] dove // ld e rd stanno per sinistra e destra / / diagonale rispettivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posiziona questa regina nel tabellone[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Ripeti per posizionare il resto delle regine if (solveNQUtil(board , col + 1)) return true; // Se posizionare la regina in board[i,col] // non porta a una soluzione, allora // rimuovi la regina da board[i,col] board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Se la regina non può essere posizionata in nessuna riga in // questa colonna col then return false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() per // risolvere il problema. Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. static boolsolveNQ() { 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 soluzione non esiste'); restituire falso; } stampaSoluzione(scheda); restituisce vero; } // Codice driver public static void Main(String[] args) {solveNQ(); } } // Questo codice è fornito da 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) restituisce vero; // Considera questa colonna e prova a posizionare // questa regina in tutte le righe una per una per (let i = 0; i { // Controlla se la regina può essere posizionata su // board[i][col] // Per controllare se una regina può essere posizionata su // board[row][col]. Dobbiamo solo controllare // ld[row-col+n-1] e rd[row+coln] dove // ld e rd stanno per sinistra e destra // diagonale rispettivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Posiziona questa regina sul tabellone [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Ricorre per posizionare il resto delle regine if (solveNQUtil(board, col + 1)) return true; // Se posizionare la regina in board[i][col] // non porta a una soluzione, allora // rimuovi la regina da board[i][col ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Se la regina non può essere posizionata qualsiasi riga in // questa colonna col then return false return false; } // Questa funzione risolve il problema N Queen utilizzando // Backtracking Utilizza principalmentesolveNQUtil() per // risolvere il problema. Restituisce false se le regine // non possono essere posizionate, altrimenti restituisce true e // stampa il posizionamento delle regine sotto forma di 1. // Tieni presente che potrebbero esserci più // soluzioni, questa funzione stampa una delle // soluzioni fattibili. function risolvereNQ() { lascia 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 soluzione non esiste'); restituire falso; } stampaSoluzione(scheda); restituisce vero; } // Codice driversolveNQ(); // Questo codice è fornito da sanjoy_62.> |
>
>Produzione
. . Q . Q . . . . . . Q . Q . .>
Complessità temporale: SU!)
Spazio ausiliario: SU)
Articoli Correlati:
- Stampa di tutte le soluzioni in N-Queen Problem