Vi har diskutert Riddertur og Rotte i en labyrint problem tidligere som eksempler på tilbakesporingsproblemer. La oss diskutere N Queen som et annet eksempelproblem som kan løses ved å bruke tilbakesporing.
Hva er N-Queen-problemet?
De N Queen er problemet med plassering N sjakkdronninger på en N×N sjakkbrett slik at ikke to dronninger angriper hverandre.
Følgende er for eksempel en løsning på 4 Queen-problemet.
Den forventede utgangen er i form av en matrise som har Q 's for blokkene der dronninger er plassert og de tomme plassene er representert av '.' . Følgende er for eksempel utdatamatrisen for 4-Queen-løsningen ovenfor.
Anbefalt: Vennligst løs det ØVE PÅ først, før du går videre til løsningen.. Q . .
. . . Q
Q . . .
. . Q .
N Queen Problem med å bruke Tilbakesporing :
Ideen er å plassere dronninger én etter én i forskjellige kolonner, fra kolonnen lengst til venstre. Når vi plasserer en dronning i en kolonne, sjekker vi for sammenstøt med allerede plasserte dronninger. I gjeldende kolonne, hvis vi finner en rad som det ikke er noen sammenstøt for, merker vi denne raden og kolonnen som en del av løsningen. Hvis vi ikke finner en slik rekke på grunn av sammenstøt, så går vi tilbake og går tilbake falsk .
Nedenfor er det rekursive treet for tilnærmingen ovenfor:
Rekursivt tre for N Queen problem
Følg trinnene nevnt nedenfor for å implementere ideen:
- Start i kolonnen lengst til venstre
- Hvis alle dronninger er plassert, returneres sant
- Prøv alle radene i gjeldende kolonne. Gjør følgende for hver rad.
- Hvis dronningen kan plasseres trygt i denne raden
- Merk deretter dette [rad kolonne] som en del av løsningen og rekursivt sjekk om plassering av dronning her fører til en løsning.
- Hvis du plasserer dronningen inn [rad kolonne] fører til en løsning for så å komme tilbake ekte .
- Hvis plassering av dronning ikke fører til en løsning, fjern merket for dette [rad kolonne] så gå tilbake og prøv andre rader.
- Hvis alle rader er prøvd og gyldig løsning ikke er funnet, returner falsk for å utløse tilbakesporing.
- Hvis dronningen kan plasseres trygt i denne raden
For bedre visualisering av denne tilbakesporingsmetoden, vennligst se 4 Queen problem .
Merk: Vi kan også løse dette problemet ved å plassere damer i rader også.
Nedenfor er implementeringen av tilnærmingen ovenfor:
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 usant; // Sjekk nedre diagonal på venstre side for (i = rad, j = col; j>= 0 && i if (board[i][j]) return usant; return true; } // En rekursiv verktøyfunksjon for å løse N // Queen problem bool solveNQUtil(int board[N][N], int col) { // base case: Hvis alle dronninger er plassert // returner true if (col>= N) return true // Betrakt denne kolonnen og prøv å plassere // denne dronningen i alle rader én etter én for (int i = 0; i // Sjekk om dronningen kan plasseres på // board[i][col] if (isSafe(board, i, col) ) { // Plasser denne dronningen i brettet[i][col] board[i][col] = 1; Hvis plassering av dronning i brettet[i][col] // ikke fører til en løsning, så // fjern dronning fra brettet[i][col] board[i][col] = 0 // BACKTRACK } } // Hvis dronningen ikke kan plasseres i noen rad i // denne kolonnen, returner false return false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil() for å // løse problemet . Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(bord, 0) == usann) { 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 (tavle[i][j]) returner falsk; // Sjekk nedre diagonal på venstre side for (i = rad, j = col; j>= 0 && i if (board[i][j]) return usant; return true; } // En rekursiv verktøyfunksjon for å løse N // Queen problem bool solveNQUtil(int board[N][N], int col) { // Grunnfall: Hvis alle dronninger er plassert // returner true if (col>= N) return true; og prøv å plassere // denne dronningen i alle rader én etter én for (int i = 0; i // Sjekk om dronningen kan plasseres på // board[i][col] if (isSafe(board, i, col) ) { // Plasser denne dronningen i brettet[i][col] board[i][col] = 1; Hvis plassering av dronning i brettet[i][col] // ikke fører til en løsning, så // fjern dronning fra brettet[i][col] board[i][col] = 0 // BACKTRACK } } // Hvis dronningen ikke kan plasseres i noen rad i // denne kolonnen, returner false return false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil() for å // løse problemet . Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. 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) == usann) { printf('Løsningen finnes ikke'); returner falsk; } printSolution(board); return true; } // Driverprogram for å teste ovenfor funksjon int main() { solveNQ(); returner 0; } // Denne koden er bidratt av 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 (tavle[i][j] == 1) returner falsk; // Sjekk nedre diagonal på venstre side for (i = rad, j = col; j>= 0 && i if (board[i][j] == 1) return usant; return true; } // En rekursiv verktøyfunksjon å løse N // Queen problem boolean solveNQUtil(int board[][], int col) { // Grunnfall: Hvis alle dronninger er plassert // returner true if (col>= N) return true // Tenk på dette kolonne og prøv å plassere // denne dronningen i alle radene én etter én for (int i = 0; i // Sjekk om dronningen kan plasseres på // board[i][col] if (isSafe(board, i, col) )) { // Plasser denne dronningen i brettet[i][col] board[i][col] = 1; // Gå tilbake for å plassere resten av dronningene hvis (solveNQUtil(board, col + 1) == true) returnerer sant; // Hvis plassering av dronning i brettet[i][col] // ikke fører til en løsning, så // fjern dronning fra brettet[i][col] = 0; BACKTRACK } } // Hvis dronningen ikke kan plasseres i noen rad i // denne kolonnen, returnerer false false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil () til // løs problemet. Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == usann) { System.out.print('Løsningen finnes ikke'); returner falsk; } printSolution(board); return true; } // Driverprogram for å teste ovenfor funksjon public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // Denne koden er bidratt 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 (tavle[i,j] == 1) returner falsk; // Sjekk nedre diagonal på venstre side for (i = rad, j = col; j>= 0 && i if (tavle[i, j] == 1) return usant; return true; } // En rekursiv verktøyfunksjon til løse N // Queen problem bool solveNQUtil(int [,]board, int col) { // Grunntall: Hvis alle dronninger er plassert // returner true if (col>= N) return true // Betrakt denne kolonnen og; prøv å plassere // denne dronningen i alle rader én etter én for (int i = 0; i { // Sjekk om dronningen kan plasseres på // board[i,col] if (isSafe(board, i, col)) { // Plasser denne dronningen i brettet[i,col] board[i, col] = 1; Hvis plassering av dronning i brett[i,col] // ikke fører til en løsning så // fjern dronning fra brett[i,col] brett[i, col] = 0 // BACKTRACK } } // Hvis queen kan ikke plasseres i noen rad i // denne kolonnen col, returner deretter false return false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil () for å // løse problemet. Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. bool solveNQ() { int [,]board = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }}; if (solveNQUtil(bord, 0) == usann) { Console.Write('Løsningen finnes ikke'); returner falsk; } printSolution(board); return true; } // Driver Code public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // Denne koden er bidratt av 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 // Sjekk nedre diagonal på venstre side for (i = rad, j = kol; j>= 0 && i if (tavle[i] [j]) return false return true } function solveNQUtil(board, col){ // base case: Hvis alle dronninger er plassert // returner true if(col>= N) return true // Tenk på denne kolonnen og prøv å plassere / / denne dronningen i alle rader én etter én for(la i=0;i if(isSafe(board, i, col)==true){ // Plasser denne dronningen i board[i][col] board[i][ col] = 1 // gjentas for å plassere resten av dronningene if(solveNQUtil(board, col + 1) == true) return true // Hvis plassering av dronning i brettet[i][col // ikke fører til en løsning, så // dronning fra brett[i][col] board[i][col] = 0 } } // hvis dronningen ikke kan plasseres i noen rad i // denne kolonnen col, returner false return false } / / Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil() for å // løse problemet Den returnerer false hvis dronninger // ikke kan plasseres, ellers returnerer true og // plassering av dronninger. 1s. // merk at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. funksjon solveNQ(){ la bord = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] hvis (solveNQUtil(board, 0) == usann){ document.write('Løsningen eksisterer ikke') return usann } printSolution(board) return true } // Driverkode solveNQ() // Denne koden er bidratt av shinjanpatra> |
>
>Produksjon
. . Q . Q . . . . . . Q . Q . .>
Tidskompleksitet: PÅ!)
Hjelpeplass: PÅ2)
Ytterligere optimalisering i is_safe()-funksjonen:
Tanken er ikke å sjekke hvert element i høyre og venstre diagonal, i stedet bruke egenskapen til diagonaler:
- Summen av Jeg og j er konstant og unik for hver høyre diagonal, hvor Jeg er raden av elementer og j er den
kolonne med elementer.- Forskjellen mellom Jeg og j er konstant og unik for hver venstre diagonal, hvor Jeg og j er henholdsvis rad og kolonne med 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) return true; // Tenk på denne kolonnen og prøv å plassere // denne dronningen i alle rader én etter én for (int i = 0; i // Sjekk om dronningen kan plasseres på // board[i][col] // For å sjekke om en dronning kan plasseres på // bord[rad][kol]. Vi trenger bare å sjekke // ld[rad-kolonne+n-1] og rd[rad+kolonne] der // ld og rd er for venstre og høyre // diagonal henholdsvis if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plasser denne dronningen i brettet[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Gjenta plassering av dronninger hvis (solveNQUtil(board, col + 1)) return true; // Hvis plassering av dronning i brettet[i][col] // ikke fører til en løsning, så // fjern dronning fra brettet[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan plasseres i noen rad i // denne kolonnen returner deretter false return false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil() for å // løse problemet. Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(bord, 0) == usann) { 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) return true; // Tenk på denne kolonnen og prøv å plassere // denne dronningen i alle rader én etter én for (int i = 0; i // Sjekk om dronningen kan plasseres på // board[i][col] // For å sjekke om en dronning kan plasseres på // bord[rad][kol]. Vi trenger bare å sjekke // ld[rad-kolonne+n-1] og rd[rad+kolonne] der // ld og rd er for venstre og høyre // diagonal henholdsvis if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plasser denne dronningen i brettet[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Gjenta plassering av dronninger hvis (solveNQUtil(board, col + 1)) return true; // Hvis plassering av dronning i brettet[i][col] // ikke fører til en løsning, så // fjern dronning fra brettet[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan plasseres i noen rad i // denne kolonnen returner deretter false return false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil() for å // løse problemet. Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. 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) == usann) { System.out.printf('Løsningen finnes ikke'); returner falsk; } printSolution(board); return true; } // Driver Code public static void main(String[] args) { solveNQ(); } } // Denne koden er bidratt 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) return true; // Tenk på denne kolonnen og prøv å plassere // denne dronningen i alle radene én etter én for (int i = 0; i // Sjekk om dronningen kan plasseres på // board[i,col] // For å sjekke om en dronning kan plasseres på // bord[rad,kol]. Vi trenger bare å sjekke // ld[rad-kolonne+n-1] og rd[rad+kolonne] der // ld og rd er for venstre og høyre / / diagonal henholdsvis if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plasser denne dronningen i brettet[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Gå tilbake for å plassere resten av dronningene if (solveNQUtil(board , col + 1)) return true; // Hvis plassering av dronning i brett[i,col] // ikke fører til en løsning, så // fjern dronning fra brett[i,col] board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan plasseres i noen rad i // denne kolonnen returner deretter false return false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil() for å // løse problemet. Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. static bool solveNQ() { int[, ] bord = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(bord, 0) == usann) { Console.Write('Løsningen finnes ikke'); returner falsk; } printSolution(board); return true; } // Driver Code public static void Main(String[] args) { solveNQ(); } } // Denne koden er bidratt av Rajput-Ji> |
java arraylist sortering
>
>
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) return true; // Vurder denne kolonnen og prøv å plassere // denne dronningen i alle rader én etter én for (la i = 0; i { // Sjekk om dronningen kan plasseres på // board[i][col] // For å sjekke hvis en dronning kan plasseres på // bord[rad][kol]. Vi trenger bare å sjekke // ld[rad-kolonne+n-1] og rd[rad+kolonne] der // ld og rd er for venstre og høyre // diagonal henholdsvis if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Plasser denne dronningen i brettet [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; if (solveNQUtil(board, col + 1)) return true // Hvis plassering av dama i brettet[i][col] // ikke fører til en løsning, så // fjern damen fra brettet[i][col] ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Hvis dronningen ikke kan plasseres hvilken som helst rad i // denne kolonnen returnerer deretter false return false } // Denne funksjonen løser N Queen-problemet ved å bruke // Backtracking Den bruker hovedsakelig solveNQUtil() for å // løse problemet. Den returnerer usann hvis dronninger // ikke kan plasseres, ellers returnerer den sann og // skriver ut plassering av dronninger i form av 1-ere. // Vær oppmerksom på at det kan være mer enn én //-løsning, denne funksjonen skriver ut en av de // mulige løsningene. funksjon solveNQ() { la bord = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == usann) { document.write('Løsningen finnes ikke'); returner falsk; } printSolution(board); return true; } // Driverkode solveNQ(); // Denne koden er bidratt av sanjoy_62.> |
>
>Produksjon
. . Q . Q . . . . . . Q . Q . .>
Tidskompleksitet: PÅ!)
Hjelpeplass: PÅ)
Relaterte artikler:
- Skriver ut alle løsninger i N-Queen Problem