Vi har diskuteret Riddertur og Rotte i en labyrint problem tidligere som eksempler på Backtracking-problemer. Lad os diskutere N Queen som et andet eksempelproblem, der kan løses ved hjælp af backtracking.
Hvad er N-Queen-problemet?
Det N Dronning er problemet med at placere N skak dronninger på en N×N skakbræt, så ikke to dronninger angriber hinanden.
For eksempel er følgende en løsning på 4 Queen-problemet.
Det forventede output er i form af en matrix, der har ' Q ’s for de blokke, hvor dronninger er placeret, og de tomme rum er repræsenteret af '.' . For eksempel er det følgende outputmatrix for ovenstående 4-Queen-løsning.
Anbefalet: Løs det venligst på ØVE SIG først, inden vi går videre til løsningen.. Q . .
. . . Q
Q . . .
. . Q .
N Queen Problem med at bruge Backtracking :
Ideen er at placere dronninger en efter en i forskellige kolonner, startende fra kolonnen længst til venstre. Når vi placerer en dronning i en kolonne, tjekker vi for sammenstød med allerede placerede dronninger. Hvis vi i den aktuelle kolonne finder en række, hvor der ikke er nogen sammenstød, markerer vi denne række og kolonne som en del af løsningen. Hvis vi ikke finder sådan en række på grund af sammenstød, så går vi tilbage og vender tilbage falsk .
Nedenfor er det rekursive træ for ovenstående tilgang:
Rekursivt træ til N Queen problem
Følg nedenstående trin for at implementere ideen:
- Start i kolonnen længst til venstre
- Hvis alle dronninger er placeret, returneres sand
- Prøv alle rækker i den aktuelle kolonne. Gør følgende for hver række.
- Hvis dronningen kan placeres sikkert i denne række
- Marker derefter dette [række, kolonne] som en del af løsningen og rekursivt tjek om placering af dronning her fører til en løsning.
- Hvis du placerer dronningen ind [række, kolonne] fører til en løsning og derefter vende tilbage rigtigt .
- Hvis placering af dronning ikke fører til en løsning, skal du fjerne markeringen af dette [række, kolonne] så gå tilbage og prøv andre rækker.
- Hvis alle rækker er blevet prøvet, og gyldig løsning ikke findes, returneres falsk at udløse backtracking.
- Hvis dronningen kan placeres sikkert i denne række
For bedre visualisering af denne backtracking-tilgang, se venligst 4 Queen problem .
Bemærk: Vi kan også løse dette problem ved også at placere dronninger i rækker.
Nedenfor er implementeringen af ovenstående tilgang:
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]) returner falsk; // Tjek nederste diagonal på venstre side for (i = række, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // En rekursiv hjælpefunktion til at løse N // Queen problem bool solveNQUtil(int board[N][N], int col) { // base case: Hvis alle dronninger er placeret // returner true if (col>= N) return true // Betragt denne kolonne og prøv at placere // denne dronning i alle rækker én efter én for (int i = 0; i // Tjek om dronningen kan placeres på // board[i][col] if (isSafe(board, i, col) ) { // Placer denne dronning i brættet[i][col] board[i][col] = 1; Hvis placering af dronning i board[i][col] // ikke fører til en løsning, så // fjern dronning fra board[i][col] board[i][col] = 0 // BACKTRACK } } // Hvis dronningen ikke kan placeres i en række i // denne kolonne col, returner false return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger primært solveNQUtil() til at // løse problemet . Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. 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) == falsk) { 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]) returner falsk; // Tjek nederste diagonal på venstre side for (i = række, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // En rekursiv hjælpefunktion til at løse N // Queen problem bool solveNQUtil(int board[N][N], int col) { // Grundfald: Hvis alle dronninger er placeret // returner true if (col>= N) return true; og prøv at placere // denne dronning i alle rækker én efter én for (int i = 0; i // Tjek om dronningen kan placeres på // board[i][col] if (isSafe(board, i, col) ) { // Placer denne dronning i board[i][col] board[i][col] = 1 // Gentag for at placere resten af dronningerne hvis (solveNQUtil(board, col + 1)) returnerer true; Hvis placering af dronning i board[i][col] // ikke fører til en løsning, så // fjern dronning fra board[i][col] board[i][col] = 0 // BACKTRACK } } // Hvis dronningen ikke kan placeres i en række i // denne kolonne col, returner false return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger primært solveNQUtil() til at // løse problemet . Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. 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) == falsk) { printf('Løsningen findes ikke'); returnere falsk; } printSolution(board); returnere sandt; } // Driverprogram til at teste ovenstående funktion int main() { solveNQ(); retur 0; } // Denne kode er bidraget af Aditya Kumar (adityakumar129)> |
>
>
Java
// Java program to solve N Queen Problem using backtracking> public> class> NQueenProblem {> >final> int> N =>4>;> >// A utility function to print solution> >void> printSolution(>int> board[][])> >{> >for> (>int> i =>0>; i for (int j = 0; j if (board[i][j] == 1) System.out.print('Q '); else System.out.print('. '); } System.out.println(); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens boolean isSafe(int board[][], int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row][i] == 1) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j] == 1) returner falsk; // Tjek nederste diagonal på venstre side for (i = række, j = col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // En rekursiv hjælpefunktion at løse N // Queen problem boolean solveNQUtil(int board[][], int col) { // Grundfald: Hvis alle dronninger er placeret // returner true if (col>= N) return true // Overvej dette kolonne og prøv at placere // denne dronning i alle rækker én efter én for (int i = 0; i // Tjek om dronningen kan placeres på // board[i][col] if (isSafe(board, i, col) )) { // Placer denne dronning i board[i][col] board[i][col] = 1; // Gentag for at placere resten af dronningerne hvis (solveNQUtil(board, col + 1) == true) returnerer true; // Hvis placering af dronning i board[i][col] // ikke fører til en løsning, så // fjern dronning fra board[i][col] board[i][col] = 0; BACKTRACK } } // Hvis dronningen ikke kan placeres i nogen række i // denne kolonne col, returner false return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking // løs problemet. Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == falsk) { System.out.print('Løsningen findes ikke'); returnere falsk; } printSolution(board); returnere sandt; } // Driverprogram til at teste ovenstående funktion public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // Denne kode er bidraget af 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) returner falsk; // Tjek nederste diagonal på venstre side for (i = række, j = col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // En rekursiv hjælpefunktion til solve N // Queen problem bool solveNQUtil(int [,]board, int col) { // Grundfald: Hvis alle dronninger er placeret // returner true if (col>= N) return true // Betragt denne kolonne og prøv at placere // denne dronning i alle rækker én efter én for (int i = 0; i { // Tjek om dronningen kan placeres på // board[i,col] if (isSafe(board, i, col)) { // Placer denne dronning i board[i,col] board[i, col] = 1 // Gentag for at placere resten af dronningerne hvis (solveNQUtil(board, col + 1) == true) return true; Hvis placering af dronning i board[i,col] // ikke fører til en løsning, så // fjern dronning fra board[i,col] board[i, col] = 0 // BACKTRACK } } // Hvis dronning kan ikke placeres i nogen række i // denne kolonne col, returner derefter false return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger primært solveNQUtil () til at // løse problemet. Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. bool solveNQ() { int [,]board = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }}; if (solveNQUtil(board, 0) == falsk) { Console.Write('Løsningen findes ikke'); returnere falsk; } printSolution(board); returnere sandt; } // Driver Code public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // Denne kode er bidraget af 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 (tavle[i][j]) returner falsk // Tjek nederste diagonal på venstre side for (i = række, j = kol; j>= 0 && i if (bræt[i] [j]) return false return true } function solveNQUtil(board, col){ // basiscase: Hvis alle dronninger er placeret // returner derefter true if(col>= N) return true // Overvej denne kolonne og prøv at placere / / denne dronning i alle rækker én efter én for(lad i=0;i if(erSafe(board, i, col)==true){ // Placer denne dronning i board[i][col] board[i][ col] = 1 // går igen for at placere resten af dronningerne if(solveNQUtil(board, col + 1) == true) return true // Hvis placering af dronning i brættet[i][col // ikke fører til en løsning, så // dronning fra board[i][col] board[i][col] = 0 } } // hvis dronningen ikke kan placeres i nogen række i // denne kolonne col så returner falsk return false } / / Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger hovedsageligt solveNQUtil() til at // løse problemet. 1s. // bemærk at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. funktion solveNQ(){ lad bord = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] hvis (solveNQUtil(board, 0) == false){ document.write('Løsningen findes ikke') return false } printSolution(board) return true } // Driverkode solveNQ() // Denne kode er bidraget af shinjanpatra> |
>
>Produktion
. . Q . Q . . . . . . Q . Q . .>
Tidskompleksitet: PÅ!)
Hjælpeplads: PÅ2)
Yderligere optimering i is_safe() funktion:
Ideen er ikke at kontrollere hvert element i højre og venstre diagonal, i stedet bruge egenskaben for diagonaler:
- Summen af jeg og j er konstant og unik for hver højre diagonal, hvor jeg er rækken af elementer og j er
kolonne af elementer.- Forskellen på jeg og j er konstant og unik for hver venstre diagonal, hvor jeg og j er henholdsvis række og kolonne af element.
Nedenfor er 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) returner sand; // Overvej denne kolonne og prøv at placere // denne dronning i alle rækker én efter én for (int i = 0; i // Tjek om dronningen kan placeres på // board[i][col] // For at kontrollere evt. en dronning kan placeres på // board[row][col]. Vi skal bare tjekke // ld[row-col+n-1] og rd[row+coln] hvor // ld og rd er for venstre og højre // diagonal henholdsvis if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placer denne dronning i brættet[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; (solveNQUtil(board, col + 1)) return true // Hvis placering af dronning i board[i][col] // ikke fører til en løsning, så // fjern dronning fra board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan placeres i nogen række i // denne kolonne col, returner derefter falsk return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger primært solveNQUtil() til at // løse problemet. Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. 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) == falsk) { cout<< 'Solution does not exist'; return false; } printSolution(board); return true; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> |
>
>
Java
// Java program to solve N Queen Problem using backtracking> import> java.util.*;> class> GFG {> >static> int> N =>4>;> >// ld is an array where its indices indicate row-col+N-1> >// (N-1) is for shifting the difference to store> >// negative indices> >static> int>[] ld =>new> int>[>30>];> >// rd is an array where its indices indicate row+col> >// and used to check whether a queen can be placed on> >// right diagonal or not> >static> int>[] rd =>new> int>[>30>];> >// Column array where its indices indicates column and> >// used to check whether a queen can be placed in that> >// row or not> >static> int>[] cl =>new> int>[>30>];> >// A utility function to print solution> >static> void> printSolution(>int> board[][])> >{> >for> (>int> i =>0>; i for (int j = 0; j System.out.printf(' %d ', board[i][j]); System.out.printf('
'); } } // A recursive utility function to solve N // Queen problem static boolean solveNQUtil(int board[][], int col) { // Base case: If all queens are placed // then return true if (col>= N) returner sand; // Overvej denne kolonne og prøv at placere // denne dronning i alle rækker én efter én for (int i = 0; i // Tjek om dronningen kan placeres på // board[i][col] // For at kontrollere evt. en dronning kan placeres på // board[row][col]. Vi skal bare tjekke // ld[row-col+n-1] og rd[row+coln] hvor // ld og rd er for venstre og højre // diagonal henholdsvis if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placer denne dronning i brættet[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; (solveNQUtil(board, col + 1)) return true // Hvis placering af dronning i board[i][col] // ikke fører til en løsning, så // fjern dronning fra board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan placeres i nogen række i // denne kolonne col, returner derefter falsk return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger primært solveNQUtil() til at // løse problemet. Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. 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) == falsk) { System.out.printf('Løsningen findes ikke'); returnere falsk; } printSolution(board); returnere sandt; } // Driverkode public static void main(String[] args) { solveNQ(); } } // Denne kode er bidraget af 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) returner sand; // Overvej denne kolonne og prøv at placere // denne dronning i alle rækker én efter én for (int i = 0; i // Tjek om dronningen kan placeres på // board[i,col] // For at kontrollere om en dronning kan placeres på // board[row,col]. Vi skal bare tjekke // ld[row-col+n-1] og rd[row+coln] hvor // ld og rd er for venstre og højre / / hhv col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Gentag for at placere resten af dronningerne if (solveNQUtil(board , col + 1)) return true; // Hvis placering af dronning i board[i,col] // ikke fører til en løsning, så // fjern dronning fra board[i,col] board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan placeres i nogen række i // denne kolonne col returner derefter false return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger primært solveNQUtil() til at // løse problemet. Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. statisk bool solveNQ() { int[, ] board = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == falsk) { Console.Write('Løsningen findes ikke'); returnere falsk; } printSolution(board); returnere sandt; } // Driver Code public static void Main(String[] args) { solveNQ(); } } // Denne kode er bidraget af Rajput-Ji> |
splitte en streng i c++
>
>
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) returner sand; // Overvej denne kolonne og prøv at placere // denne dronning i alle rækker én efter én for (lad i = 0; i { // Tjek om dronningen kan placeres på // bord[i][col] // For at kontrollere hvis en dronning kan placeres på // board[row][col]. Vi skal bare tjekke // ld[row-col+n-1] og rd[row+coln] hvor // ld og rd er for venstre og højre // diagonal henholdsvis if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Placer denne dronning i brættet [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Gentag for at placere resten af damerne if (solveNQUtil(board, col + 1)) returner true // Hvis placering af dronning i board[i][col] // ikke fører til en løsning, så // fjern dronning fra board[i][col; ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan placeres en hvilken som helst række i // denne kolonne returnerer derefter falsk return false } // Denne funktion løser N Queen-problemet ved at bruge // Backtracking Den bruger hovedsageligt solveNQUtil() til at // løse problemet. Det returnerer falsk, hvis dronninger // ikke kan placeres, ellers returneres sandt og // udskriver placering af dronninger i form af 1'ere. // Bemærk venligst at der kan være mere end én // løsninger, denne funktion udskriver en af de // mulige løsninger. funktion solveNQ() { lad bord = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == falsk) { document.write('Løsningen findes ikke'); returnere falsk; } printSolution(board); returnere sandt; } // Driverkode solveNQ(); // Denne kode er bidraget af sanjoy_62.> |
>
>Produktion
. . Q . Q . . . . . . Q . Q . .>
Tidskompleksitet: PÅ!)
Hjælpeplads: PÅ)
Relaterede artikler:
- Udskrivning af alle løsninger i N-Queen Problem