Vi har diskuterat Riddarturné och Råtta i en labyrint problem tidigare som exempel på Backtracking-problem. Låt oss diskutera N Queen som ett annat exempelproblem som kan lösas med hjälp av backtracking.
Vad är N-Queen-problemet?
De N Drottning är problemet med att placera N schackdrottningar på en N×N schackbräde så att inga två drottningar attackerar varandra.
Till exempel är följande en lösning på problemet med 4 Queen.
Den förväntade produktionen är i form av en matris som har F ’s för blocken där damer placeras och de tomma utrymmena representeras av '.' . Följande är till exempel utmatrisen för ovanstående 4-Queen-lösning.
Rekommenderas: Vänligen lös det ÖVA först innan du går vidare till lösningen.. Q . .
. . . F
Q . . .
. . Q .
N Queen Problem med att använda Backtracking :
Tanken är att placera damer en efter en i olika kolumner, med början från kolumnen längst till vänster. När vi placerar en drottning i en kolumn, kontrollerar vi för sammandrabbningar med redan placerade damer. I den aktuella kolumnen, om vi hittar en rad för vilken det inte finns någon konflikt, markerar vi denna rad och kolumn som en del av lösningen. Om vi inte hittar en sådan rad på grund av sammandrabbningar, så backar vi och återvänder falsk .
Nedan är det rekursiva trädet för ovanstående tillvägagångssätt:
Rekursivt träd för N Queen-problem
Följ stegen nedan för att implementera idén:
- Börja i kolumnen längst till vänster
- Om alla damer placeras returneras sant
- Prova alla rader i den aktuella kolumnen. Gör följande för varje rad.
- Om drottningen kan placeras säkert i den här raden
- Markera sedan detta [rad kolumn] som en del av lösningen och rekursivt kontrollera om placering av dam här leder till en lösning.
- Om du placerar drottningen i [rad kolumn] leder till en lösning och återvänder sedan Sann .
- Om placering av dam inte leder till en lösning, avmarkera detta [rad kolumn] backa sedan och prova andra rader.
- Om alla rader har prövats och giltig lösning inte hittas, returnera falsk för att utlösa backtracking.
- Om drottningen kan placeras säkert i den här raden
För bättre visualisering av denna bakåtspårningsmetod, se 4 Queen problem .
Notera: Vi kan också lösa detta problem genom att placera damer i rader också.
Nedan är implementeringen av ovanstående tillvägagångssätt:
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]) returnerar falskt; // Kontrollera nedre diagonal på vänster sida för (i = rad, j = kol; j>= 0 && i if (board[i][j]) return false; return true; } // En rekursiv hjälpfunktion för att lösa N // Queen problem bool solveNQUtil(int board[N][N], int col) { // basfall: Om alla damer är placerade // returnera true if (col>= N) return true // Betrakta denna kolumn och försök att placera // denna dam i alla rader en efter en för (int i = 0; i // Kontrollera om damen kan placeras på // board[i][col] if (isSafe(board, i, col) ) { // Placera denna dam i brädet[i][col] board[i][col] = 1; // återkommer för att placera resten av damerna om (solveNQUtil(board, col + 1)) returnerar sant; Om det inte leder till någon lösning att placera dam i brädet[i][col] // ta bort damen från brädet[i][col] board[i][col] = 0 // BACKTRACK } } // Om damen inte kan placeras i någon rad i // denna kolumn kolumn returnerar false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil() för att // lösa problemet . Den returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placering av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. bool solveNQ() { int board[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--) if (board[i][j]) returnerar falskt; // Kontrollera nedre diagonal på vänster sida för (i = rad, j = kol; j>= 0 && i if (board[i][j]) return false; return true; } // En rekursiv hjälpfunktion för att lösa N // Queen problem bool solveNQUtil(int board[N][N], int col) { // Basfall: Om alla damer är placerade // returnera true if (col>= N) return true; och försök att placera // denna dam i alla rader en efter en för (int i = 0; i // Kontrollera om damen kan placeras på // board[i][col] if (isSafe(board, i, col) ) { // Placera denna dam i brädet[i][col] board[i][col] = 1; Om det inte leder till någon lösning att placera dam i brädet[i][col] // ta bort damen från brädet[i][col] board[i][col] = 0 // BACKTRACK } } // Om damen inte kan placeras i någon rad i // denna kolumn kolumn returnerar false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil() för att // lösa problemet . Den returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placering av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { printf('Lösningen finns inte'); returnera falskt; } printSolution(board); returnera sant; } // Drivrutinsprogram för att testa ovan funktion int main() { solveNQ(); returnera 0; } // Denna kod är bidragit av Aditya Kumar (adityakumar129)> |
>
>
Java
hur stor är min skärm
// 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) returnerar falskt; // Kontrollera nedre diagonalen på vänster sida för (i = rad, j = kol; j>= 0 && i if (board[i][j] == 1) return false; return true; } // En rekursiv verktygsfunktion att lösa N // Queen problem boolean solveNQUtil(int board[][], int col) { // Basfall: Om alla damer är placerade // returnera true if (col>= N) return true // Betrakta detta kolumn och försök placera // denna dam i alla rader en efter en för (int i = 0; i // Kontrollera om damen kan placeras på // board[i][col] if (isSafe(board, i, col) )) { // Placera denna dam i brädet[i][col] board[i][col] = 1; // Återkommer för att placera resten av damerna om (solveNQUtil(board, col + 1) == true) returnerar sant; // Om du placerar dam i brädet[i][col] // leder inte till en lösning så // ta bort drottningen från brädet[i][col] = 0; BACKTRACK } } // Om damen inte kan placeras i någon rad i // denna kolumn kolumn, returnera false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil (). // lösa problemet. Den returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placering av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { System.out.print('Lösningen finns inte'); returnera falskt; } printSolution(board); returnera sant; } // Drivrutinsprogram för att testa ovan funktion public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // Denna kod är bidragit av 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) returnerar falskt; // Kontrollera nedre diagonalen på vänster sida för (i = rad, j = kol; j>= 0 && i if (tavla[i, j] == 1) return false; return true; } // En rekursiv hjälpfunktion till solve N // Queen problem bool solveNQUtil(int [,]board, int col) { // Basfall: Om alla damer är placerade // returnera true if (col>= N) return true // Betrakta denna kolumn och försök att placera // denna dam i alla rader en efter en för (int i = 0; i { // Kontrollera om damen kan placeras på // board[i,col] if (isSafe(board, i, col)) { // Placera denna dam i brädet[i,col] board[i, col] = 1; // Återgå för att placera resten av damerna om (solveNQUtil(board, col + 1) == true) return true; Om att placera dam i brädet[i,col] // inte leder till en lösning så // ta bort damen från brädet[i,col] = 0 // BACKTRACK } } // Om queen kan inte placeras i någon rad i // denna kolumn kolumn, returnera sedan false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil () för att // lösa problemet. Den returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placering av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. bool solveNQ() { int [,]board = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }}; if (solveNQUtil(board, 0) == false) { Console.Write('Lösningen finns inte'); returnera falskt; } printSolution(board); returnera sant; } // Driver Code public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // Denna kod är bidragit av Princi Singh> |
>
>
Javascript
delad av sträng java
> // 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 // Kontrollera nedre diagonalen på vänster sida för (i = rad, j = kol; j>= 0 && i if (board[i] [j]) return false return true } function solveNQUtil(board, col){ // basfall: Om alla damer är placerade // returnera true if(col>= N) return true // Betrakta den här kolumnen och försök placera / / denna dam i alla rader en efter en för(låt i=0;i if(isSafe(board, i, col)==true){ // Placera denna dam i board[i][col] board[i][ col] = 1 // återkommer för att placera resten av damerna if(solveNQUtil(board, col + 1) == true) return true // Om placering av dam i tavlan[i][col // inte leder till en lösning, då // dam från brädet[i][col] board[i][col] = 0 } } // om drottningen inte kan placeras i någon rad i // denna kolumn kol returnera false return false } / / Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil() för att // lösa problemet. 1s. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. funktion solveNQ(){ let board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] om (solveNQUtil(board, 0) == false){ document.write('Lösningen existerar inte') return false } printSolution(board) return true } // Driver Code solveNQ() // Denna kod är bidragit från shinjanpatra> |
>
>Produktion
. . Q . Q . . . . . . Q . Q . .>
Tidskomplexitet: PÅ!)
Hjälputrymme: PÅ2)
Ytterligare optimering i is_safe()-funktionen:
Tanken är inte att kontrollera varje element i höger och vänster diagonal, använd istället egenskapen för diagonaler:
- Summan av i och j är konstant och unik för varje höger diagonal, där i är raden av element och j är
kolumn av element.- Skillnaden mellan i och j är konstant och unik för varje vänsterdiagonal, där i och j är rad och kolumn av element respektive.
Nedan är implementeringen:
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) returnera sant; // Betrakta den här kolumnen och försök att placera // den här damen i alla rader en efter en för (int i = 0; i // Kontrollera om damen kan placeras på // board[i][col] // För att kontrollera om en dam kan placeras på // board[rad][kol]. Vi behöver bara kontrollera // ld[rad-kol+n-1] och rd[rad+koln] där // ld och rd är för vänster och höger // diagonal respektive if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placera denna dam i brädet[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Återkommer för att placera resten av damerna om (solveNQUtil(board, col + 1)) return true // Om du placerar dam i brädet[i][col] // inte leder till en lösning, så // ta bort damen från brädet[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Om damen inte kan placeras i någon rad i // denna kolumn col. returnerar sedan false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil() för att // lösa problemet. Den returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placering av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. bool solveNQ() { int board[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)> |
>
>
Java
html listbox
// 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) returnera sant; // Betrakta den här kolumnen och försök att placera // den här damen i alla rader en efter en för (int i = 0; i // Kontrollera om damen kan placeras på // board[i][col] // För att kontrollera om en dam kan placeras på // board[rad][kol]. Vi behöver bara kontrollera // ld[rad-kol+n-1] och rd[rad+koln] där // ld och rd är för vänster och höger // diagonal respektive if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placera denna dam i brädet[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Återkommer för att placera resten av damerna om (solveNQUtil(board, col + 1)) return true // Om du placerar dam i brädet[i][col] // inte leder till en lösning, så // ta bort damen från brädet[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Om damen inte kan placeras i någon rad i // denna kolumn col. returnerar sedan false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil() för att // lösa problemet. Det returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placeringen av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. static boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0 } }; if (solveNQUtil(board, 0) == false) { System.out.printf('Lösningen finns inte'); returnera falskt; } printSolution(board); returnera sant; } // Driver Code public static void main(String[] args) { solveNQ(); } } // Denna kod är bidragit av 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) returnera sant; // Betrakta den här kolumnen och försök placera // den här damen i alla rader en efter en för (int i = 0; i // Kontrollera om damen kan placeras på // board[i,col] // För att kontrollera om en drottning kan placeras på // board[rad,kol]. Vi behöver bara kontrollera // ld[rad-kol+n-1] och rd[rad+koln] där // ld och rd är för vänster och höger / / diagonal respektive if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placera denna dam i brädet[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Återkommer för att placera resten av damerna if (solveNQUtil(board , col + 1)) return true; // Om du placerar dam i brädet[i,col] // inte leder till en lösning, så // ta bort queen från brädet[i,col] board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Om damen inte kan placeras i någon rad i // denna kolumn returnera sedan false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil() för att // lösa problemet. Den returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placering av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. static bool solveNQ() { int[, ] board = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { Console.Write('Lösningen finns inte'); returnera falskt; } printSolution(board); returnera sant; } // Driver Code public static void Main(String[] args) { solveNQ(); } } // Denna kod är bidragit av 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) returnera sant; // Betrakta den här kolumnen och försök placera // den här damen i alla rader en efter en för (låt i = 0; i { // Kontrollera om damen kan placeras på // board[i][col] // För att kontrollera om en dam kan placeras på // board[rad][kol]. Vi behöver bara kontrollera // ld[rad-kol+n-1] och rd[rad+koln] där // ld och rd är för vänster och höger // diagonal respektive om ((ld[i - kol + N - 1] != 1 && rd[i + kol] != 1) && cl[i] != 1) { // Placera denna dam i brädet [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Återkommer för att placera resten av damerna if (solveNQUtil(board, col + 1)) returnerar sant // Om du placerar dam i brädet[i][col] // inte leder till en lösning, så // ta bort damen från brädet[i][col; ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Om damen inte kan placeras in valfri rad i // denna kolumn returnerar sedan false return false } // Denna funktion löser N Queen-problemet med // Backtracking Den använder huvudsakligen solveNQUtil() för att // lösa problemet. Den returnerar falskt om damer // inte kan placeras, annars returneras sant och // skriver ut placering av damer i form av 1:or. // Observera att det kan finnas mer än en //-lösning, den här funktionen skriver ut en av de // möjliga lösningarna. funktion solveNQ() { let board = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == false) { document.write('Lösningen finns inte'); returnera falskt; } printSolution(board); returnera sant; } // Drivrutinskod solveNQ(); // Denna kod är bidragit från sanjoy_62.> |
>
>Produktion
. . Q . Q . . . . . . Q . Q . .>
Tidskomplexitet: PÅ!)
Hjälputrymme: PÅ)
Relaterade artiklar:
- Skriver ut alla lösningar i N-Queen Problem