Hemos discutido gira del caballero y Rata en un laberinto problema anterior como ejemplos de problemas de retroceso. Analicemos N Queen como otro problema de ejemplo que se puede resolver mediante el retroceso.
¿Qué es el problema de N-Queen?
El norte La reina es el problema de colocar. norte reinas de ajedrez en un N×N tablero de ajedrez para que no haya dos reinas que se ataquen entre sí.
Por ejemplo, la siguiente es una solución para el problema de las 4 reinas.
El resultado esperado tiene la forma de una matriz que tiene ' q es para los bloques donde se colocan las reinas y los espacios vacíos están representados por ‘.’ . Por ejemplo, la siguiente es la matriz de salida para la solución de 4 reinas anterior.
Recomendado: Resuélvelo en PRÁCTICA primero, antes de pasar a la solución.. P. .
. . . q
P. . .
. . P.
N Reina Problema al usar Retroceder :
La idea es colocar las reinas una a una en diferentes columnas, comenzando por la columna más a la izquierda. Cuando colocamos una reina en una columna, comprobamos si hay conflictos con reinas ya colocadas. En la columna actual, si encontramos una fila para la cual no hay conflicto, marcamos esta fila y columna como parte de la solución. Si no encontramos esa fila debido a enfrentamientos, retrocedemos y regresamos. FALSO .
A continuación se muestra el árbol recursivo del enfoque anterior:
Árbol recursivo para el problema de N Queen
Siga los pasos que se mencionan a continuación para implementar la idea:
- Comience en la columna más a la izquierda
- Si se colocan todas las reinas, devuelve verdadero.
- Pruebe todas las filas de la columna actual. Haga lo siguiente para cada fila.
- Si la reina se puede colocar de forma segura en esta fila
- Entonces marca esto [fila columna] como parte de la solución y verifique recursivamente si colocar la reina aquí conduce a una solución.
- Si colocas la reina en [fila columna] conduce a una solución y luego regresa verdadero .
- Si colocar la reina no conduce a una solución, desmarque esto [fila columna] luego retroceda y pruebe con otras filas.
- Si se han probado todas las filas y no se encuentra una solución válida, regrese FALSO para activar el retroceso.
- Si la reina se puede colocar de forma segura en esta fila
Para una mejor visualización de este enfoque de retroceso, consulte Problema de 4 reinas .
Nota: También podemos resolver este problema colocando reinas en filas.
A continuación se muestra la implementación del enfoque anterior:
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--) si (tablero[i][j]) devuelve falso; // Verifique la diagonal inferior en el lado izquierdo para (i = fila, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Una función de utilidad recursiva para resolver N // Problema de reina bool solveNQUtil(int board[N][N], int col) { // caso base: si se colocan todas las reinas // entonces devuelve verdadero si (col>= N) devuelve verdadero // Considere esta columna; e intente colocar // esta reina en todas las filas una por una for (int i = 0; i // Compruebe si la reina se puede colocar en // el tablero[i][col] if (isSafe(board, i, col) ) { // Coloca esta reina en el tablero[i][col] board[i][col] = 1; // recurre para colocar el resto de las reinas si (solveNQUtil(board, col + 1)) return true; Si colocar la reina en el tablero[i][col] // no conduce a una solución, entonces // elimina la reina del tablero[i][col] board[i][col] = 0 // BACKTRACK } } // Si la reina no se puede colocar en ninguna fila // de esta columna, entonces return false return false } // Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil() para // resolver el problema. . Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. bool solveNQ() { int tablero[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(tablero, 0) == falso) { 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--) si (tablero[i][j]) devuelve falso; // Verifique la diagonal inferior en el lado izquierdo para (i = fila, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Una función de utilidad recursiva para resolver N // Problema de reina bool solveNQUtil(int board[N][N], int col) { // Caso base: si se colocan todas las reinas // entonces devuelve verdadero si (col>= N) devuelve verdadero // Considere esta columna; e intente colocar // esta reina en todas las filas una por una for (int i = 0; i // Compruebe si la reina se puede colocar en // el tablero[i][col] if (isSafe(board, i, col) ) { // Coloca esta reina en el tablero[i][col] board[i][col] = 1; // Recurre para colocar el resto de las reinas si (solveNQUtil(board, col + 1)) return true; Si colocar la reina en el tablero[i][col] // no conduce a una solución, entonces // elimina la reina del tablero[i][col] board[i][col] = 0 // BACKTRACK } } // Si la reina no se puede colocar en ninguna fila // de esta columna, entonces return false return false } // Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil() para // resolver el problema. . Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. bool solveNQ() { int tablero[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 solución no existe'); falso retorno; } imprimirSolución(tablero); devolver verdadero; } // Programa controlador para probar la función anterior int main() { solveNQ(); devolver 0; } // Este código es una contribución de Aditya Kumar (adityakumar129)> |
cadenas concat java
>
>
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 (tablero[i][j] == 1) devuelve falso; // Verifique la diagonal inferior en el lado izquierdo para (i = fila, j = col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Una función de utilidad recursiva para resolver N // Problema de reina booleano solveNQUtil(int board[][], int col) { // Caso base: si todas las reinas están colocadas // entonces devuelve verdadero si (col>= N) devuelve verdadero // Considere esto; columna e intente colocar // esta reina en todas las filas una por una for (int i = 0; i // Compruebe si la reina se puede colocar en // el tablero[i][col] if (isSafe(board, i, col )) { // Coloca esta reina en el tablero[i][col] board[i][col] = 1; // Recurre para colocar el resto de las reinas if (solveNQUtil(board, col + 1) == true) return true; // Si colocar la reina en el tablero[i][col] // no conduce a una solución, entonces // elimina la reina del tablero[i][col] board[i][col] = 0; BACKTRACK } } // Si la reina no se puede colocar en ninguna fila // de esta columna, entonces devuelve false return false } // Esta función resuelve el problema de N Queen usando // Backtracking. // resolver el problema. Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. booleano solveNQ() { int tablero[][] = { { 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ón no existe'); falso retorno; } imprimirSolución(tablero); devolver verdadero; } // Programa controlador para probar la función anterior public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Reina.solveNQ(); } } // Este código es una contribución de Abhishek Shankhadhar> |
>
>
Python3
# Python3 program to solve N Queen> # Problem using backtracking> global> N> N>=> 4> def> printSolution(board):> >for> i>in> range>(N):> >for> j>in> range>(N):> >if> board[i][j]>=>=> 1>:> >print>(>'Q'>,end>=>' '>)> >else>:> >print>(>'.'>,end>=>' '>)> >print>()> # A utility function to check if a queen can> # be placed on board[row][col]. Note that this> # function is called when 'col' queens are> # already placed in columns from 0 to col -1.> # So we need to check only left side for> # attacking queens> def> isSafe(board, row, col):> ># Check this row on left side> >for> i>in> range>(col):> >if> board[row][i]>=>=> 1>:> >return> False> ># Check upper diagonal on left side> >for> i, j>in> zip>(>range>(row,>->1>,>->1>),> >range>(col,>->1>,>->1>)):> >if> board[i][j]>=>=> 1>:> >return> False> ># Check lower diagonal on left side> >for> i, j>in> zip>(>range>(row, N,>1>),> >range>(col,>->1>,>->1>)):> >if> board[i][j]>=>=> 1>:> >return> False> >return> True> def> solveNQUtil(board, col):> ># Base case: If all queens are placed> ># then return true> >if> col>>=> 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> |
igualdad de cadenas en java
>
>
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 (tablero[i,j] == 1) devuelve falso; // Verifique la diagonal inferior en el lado izquierdo para (i = fila, j = col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Una función de utilidad recursiva para resolver N // Problema de reina bool solveNQUtil(int [,]board, int col) { // Caso base: si se colocan todas las reinas // entonces devuelve verdadero si (col>= N) devuelve verdadero // Considere esta columna y intente colocar // esta reina en todas las filas una por una for (int i = 0; i { // Compruebe si la reina se puede colocar en // el tablero[i,col] if (isSafe(board, i, col)) { // Coloca esta reina en el tablero[i,col] board[i, col] = 1; // Recurre para colocar el resto de las reinas if (solveNQUtil(board, col + 1) == true) return true; Si colocar la reina en el tablero[i,col] // no conduce a una solución, entonces // elimina la reina del tablero[i,col] board[i, col] = 0 // BACKTRACK } } // Si el; la reina no se puede colocar en ninguna fila en // esta columna col, luego devuelve falso devuelve falso } // Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil () para // resolver el problema. Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. bool solveNQ() { int [,]tablero = {{ 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ón no existe'); falso retorno; } imprimirSolución(tablero); devolver verdadero; } // Código del controlador public static void Main(String []args) { GFG Queen = new GFG(); Reina.solveNQ(); } } // Este código es una contribución de Princi Singh> |
>
>
JavaScript
> // JavaScript program to solve N Queen> // Problem using backtracking> const N = 4> function> printSolution(board)> {> >for>(let i = 0; i { for(let j = 0; j { if(board[i][j] == 1) document.write('Q ') else document.write('. ') } document.write('') } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens function isSafe(board, row, col) { // Check this row on left side for(let i = 0; i if(board[row][i] == 1) return false } // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) return false // Verifique la diagonal inferior en el lado izquierdo para (i = fila, j = col; j>= 0 && i if (board[i] [j]) return false return true } function solveNQUtil(board, col){ // caso base: si se colocan todas las reinas // entonces devuelve verdadero if(col>= N) return true // Considere esta columna e intente colocar / / esta reina en todas las filas una por una for(let i=0;i if(isSafe(board, i, col)==true){ // Coloca esta reina en el tablero[i][col] tablero[i][ col] = 1 // recurre para colocar el resto de las reinas if(solveNQUtil(board, col + 1) == true) return true // Si colocar la reina en el tablero[i][col // no conduce a una solución, entonces // reina del tablero[i][col] tablero[i][col] = 0 } } // si la reina no se puede colocar en ninguna fila en // esta columna col entonces devuelve falso devuelve falso } / / Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil() para // resolver el problema. Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero y // la colocación de las reinas en forma de. 1 chelín. // tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. función resolverNQ(){ let board = [ [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ón no existe') return false } printSolution(board) return true } // Código del controlador solveNQ() // Este código es una contribución de shinjanpatra> |
>
>Producción
. . Q . Q . . . . . . Q . Q . .>
Complejidad del tiempo: ¡EN!)
Espacio Auxiliar: EN2)
Optimización adicional en la función is_safe():
La idea no es verificar todos los elementos en la diagonal derecha e izquierda, sino utilizar la propiedad de las diagonales:
- La suma de i y j es constante y única para cada diagonal recta, donde i es la fila de elementos y j es el
columna de elementos.- La diferencia entre i y j es constante y única para cada diagonal izquierda, donde i y j son fila y columna del elemento respectivamente.
A continuación se muestra la implementación:
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) devuelve verdadero; // Considere esta columna e intente colocar // esta reina en todas las filas una por una for (int i = 0; i // Compruebe si la reina se puede colocar // en el tablero[i][col] // Para comprobar si se puede colocar una reina en // el tablero[fila][col]. Sólo necesitamos verificar // ld[fila-col+n-1] y rd[fila+coln] donde // ld y rd son para izquierda y derecha // diagonal respectivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Coloca esta reina en el tablero[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recurre para colocar el resto de las reinas si; (solveNQUtil(board, col + 1)) return true; // Si colocar la reina en el tablero[i][col] // no conduce a una solución, entonces // elimina la reina del tablero[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; fila en // esta columna col luego devuelve falso retorno falso } // Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil() para // resolver el problema. Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. bool solveNQ() { int tablero[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(tablero, 0) == falso) { 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 largo a int
// 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) devuelve verdadero; // Considere esta columna e intente colocar // esta reina en todas las filas una por una for (int i = 0; i // Compruebe si la reina se puede colocar // en el tablero[i][col] // Para comprobar si se puede colocar una reina en // el tablero[fila][col]. Sólo necesitamos verificar // ld[fila-col+n-1] y rd[fila+coln] donde // ld y rd son para izquierda y derecha // diagonal respectivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Coloca esta reina en el tablero[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recurre para colocar el resto de las reinas si; (solveNQUtil(board, col + 1)) return true; // Si colocar la reina en el tablero[i][col] // no conduce a una solución, entonces // elimina la reina del tablero[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; fila en // esta columna col luego devuelve falso retorno falso } // Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil() para // resolver el problema. Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. estático booleano solveNQ() { int tablero[][] = { { 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ón no existe'); falso retorno; } imprimirSolución(tablero); devolver verdadero; } // Código del controlador public static void main(String[] args) { solveNQ(); } } // Este código es una contribución de Princi Singh> |
>
>
Python3
# Python3 program to solve N Queen Problem using> # backtracking> N>=> 4> # ld is an array where its indices indicate row-col+N-1> # (N-1) is for shifting the difference to store negative> # indices> ld>=> [>0>]>*> 30> # rd is an array where its indices indicate row+col> # and used to check whether a queen can be placed on> # right diagonal or not> rd>=> [>0>]>*> 30> # Column array where its indices indicates column and> # used to check whether a queen can be placed in that> # row or not> cl>=> [>0>]>*> 30> # A utility function to print solution> def> printSolution(board):> >for> i>in> range>(N):> >for> j>in> range>(N):> >print>(board[i][j], end>=>' '>)> >print>()> # A recursive utility function to solve N> # Queen problem> def> solveNQUtil(board, col):> ># Base case: If all queens are placed> ># then return True> >if> (col>>=> 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) devuelve verdadero; // Considere esta columna e intente colocar // esta reina en todas las filas una por una for (int i = 0; i // Compruebe si la reina se puede colocar // en el tablero[i,col] // Para comprobar si La reina se puede colocar en // el tablero[fila,col]. Sólo necesitamos verificar // ld[fila-col+n-1] y rd[fila+coln] donde // ld y rd son para izquierda y derecha / / diagonal respectivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Coloca esta reina en el tablero[i, col] tablero[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recurre para colocar el resto de las reinas if (solveNQUtil(board) , col + 1)) return true; // Si colocar la reina en el tablero[i,col] // no conduce a una solución, entonces // elimina la reina del tablero[i,col] tablero[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Si la reina no se puede colocar en ninguna fila de // esta columna luego return false return false } // Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil() para // resolver el problema. Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. static bool solveNQ() { int[, ] tablero = { { 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ón no existe'); falso retorno; } imprimirSolución(tablero); devolver verdadero; } // Código del controlador public static void Main(String[] args) { solveNQ(); } } // Este código es aportado por Rajput-Ji> |
>
>
JavaScript
búsqueda de novios
> >// 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) devuelve verdadero; // Considere esta columna e intente colocar // esta reina en todas las filas una por una for (let i = 0; i { // Compruebe si la reina se puede colocar // en el tablero[i][col] // Para comprobar si se puede colocar una reina en // tablero[fila][col]. Solo necesitamos verificar // ld[fila-col+n-1] y rd[fila+coln] donde // ld y rd son para la izquierda y derecha // diagonal respectivamente if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Coloca esta reina en el tablero [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Recurre para colocar el resto de las reinas. if (solveNQUtil(board, col + 1)) return true; // Si colocar la reina en el tablero[i][col] // no conduce a una solución, entonces // elimina la reina del tablero[i][col] ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; cualquier fila en // esta columna col luego devuelve falso retorno falso } // Esta función resuelve el problema de N Queen usando // Retroceso. Utiliza principalmente solveNQUtil() para // resolver el problema. Devuelve falso si las reinas // no se pueden colocar; de lo contrario, devuelve verdadero e // imprime la ubicación de las reinas en forma de unos. // Tenga en cuenta que puede haber más de una // solución, esta función imprime una de las // soluciones factibles. función resolverNQ() { 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ón no existe'); falso retorno; } imprimirSolución(tablero); devolver verdadero; } // Código del controlador solveNQ(); // Este código es aportado por sanjoy_62.> |
>
>Producción
. . Q . Q . . . . . . Q . Q . .>
Complejidad del tiempo: ¡EN!)
Espacio Auxiliar: EN)
Artículos relacionados:
- Imprimir todas las soluciones en N-Queen Problem