We hebben besproken Riddertocht En Rat in een doolhof probleem eerder als voorbeelden van Backtracking-problemen. Laten we N Queen bespreken als een ander voorbeeldprobleem dat kan worden opgelost met behulp van backtracking.
Wat is het N-Queen-probleem?
De N Koningin is het probleem van plaatsing N schaakkoninginnen op een N×N schaakbord zodat geen twee koninginnen elkaar aanvallen.
Het volgende is bijvoorbeeld een oplossing voor het 4 Koningin-probleem.
De verwachte output heeft de vorm van een matrix met ‘ Q ‘s voor de blokken waar koninginnen worden geplaatst en de lege ruimtes worden weergegeven door '.' . Het volgende is bijvoorbeeld de uitvoermatrix voor de bovenstaande 4-Queen-oplossing.
Aanbevolen: los het op OEFENING eerst, voordat u verder gaat met de oplossing.. Q . .
. . . Q
Q . . .
. . Q .
N Queen Probleem bij gebruik Terugkeren :
Het idee is om koninginnen één voor één in verschillende kolommen te plaatsen, beginnend bij de meest linkse kolom. Wanneer we een dame in een kolom plaatsen, controleren we op botsingen met reeds geplaatste koninginnen. Als we in de huidige kolom een rij vinden waarvoor er geen conflict is, markeren we deze rij en kolom als onderdeel van de oplossing. Als we zo'n ruzie niet vinden vanwege botsingen, gaan we terug en keren we terug vals .
Hieronder vindt u de recursieve boom van de bovenstaande benadering:
Recursieve boom voor het N Queen-probleem
Volg de onderstaande stappen om het idee te implementeren:
- Begin in de meest linkse kolom
- Als alle koninginnen zijn geplaatst, is het resultaat waar
- Probeer alle rijen in de huidige kolom. Doe het volgende voor elke rij.
- Of de koningin veilig in deze rij geplaatst kan worden
- Markeer dit dan [rij kolom] als onderdeel van de oplossing en controleer recursief of het plaatsen van de koningin hier tot een oplossing leidt.
- Als u de koningin erin plaatst [rij kolom] leidt tot een oplossing en keert dan terug WAAR .
- Als het plaatsen van de koningin niet tot een oplossing leidt, schakel dit dan uit [rij kolom] ga dan terug en probeer andere rijen.
- Als alle rijen zijn geprobeerd en er geen geldige oplossing wordt gevonden, keert u terug vals om een terugslag in gang te zetten.
- Of de koningin veilig in deze rij geplaatst kan worden
Voor een betere visualisatie van deze backtracking-aanpak verwijzen wij u naar 4 Koningin-probleem .
Opmerking: We kunnen dit probleem ook oplossen door de koninginnen ook in rijen te plaatsen.
Hieronder vindt u de implementatie van de bovenstaande aanpak:
C++
hashset versus hashmap
// 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--) als (bord[i][j]) false retourneert; // Controleer de onderste diagonaal aan de linkerkant op (i = rij, j = col; j>= 0 && i if (bord[i][j]) return false; return true; } // Een recursieve nutsfunctie om N op te lossen // Koninginprobleem bool solveNQUtil(int board[N][N], int col) {// basisscenario: als alle koninginnen zijn geplaatst // retourneer dan true als (col>= N) true retourneert; en probeer // deze koningin één voor één in alle rijen te plaatsen voor (int i = 0; i // Controleer of de koningin geplaatst kan worden op // board[i][col] if (isSafe(board, i, col) ) {// Plaats deze koningin in bord[i][col] bord[i][col] = 1; // herhaal om de rest van de koninginnen te plaatsen als (solveNQUtil(bord, col + 1)) true retourneert; Als het plaatsen van de koningin op bord[i][col] // niet tot een oplossing leidt, verwijder dan // de koningin van bord[i][col] bord[i][col] = 0 // BACKTRACK } }; // Als de koningin niet in een rij in // deze kolom kan worden geplaatst, return false return false } // Deze functie lost het N Queen-probleem op met behulp van // Backtracking. Het gebruikt voornamelijk solveNQUtil() om // het probleem op te lossen . Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. bool solveNQ() { int bord[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(bord, 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--) als (bord[i][j]) false retourneert; // Controleer de onderste diagonaal aan de linkerkant op (i = rij, j = col; j>= 0 && i if (bord[i][j]) return false; return true; } // Een recursieve nutsfunctie om N op te lossen // Koninginprobleem bool solveNQUtil(int board[N][N], int col) {// Basisscenario: als alle koninginnen zijn geplaatst // retourneer dan true als (col>= N) true retourneert; en probeer // deze koningin één voor één in alle rijen te plaatsen voor (int i = 0; i // Controleer of de koningin geplaatst kan worden op // board[i][col] if (isSafe(board, i, col) ) {// Plaats deze koningin in bord[i][col] bord[i][col] = 1; // Herhaal om de rest van de koninginnen te plaatsen als (solveNQUtil(bord, col + 1)) true retourneert; Als het plaatsen van de koningin op bord[i][col] // niet tot een oplossing leidt, verwijder dan // de koningin van bord[i][col] bord[i][col] = 0 // BACKTRACK } }; // Als de koningin niet in een rij in // deze kolom kan worden geplaatst, return false return false } // Deze functie lost het N Queen-probleem op met behulp van // Backtracking. Het gebruikt voornamelijk solveNQUtil() om // het probleem op te lossen . Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. bool solveNQ() { int bord[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { printf('Oplossing bestaat niet'); retour vals; } printSolution(bord); retourneer waar; } // Stuurprogramma om bovenstaande functie te testen int main() { solveNQ(); retour 0; } // Deze code is bijgedragen door 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--) als (bord[i][j] == 1) false retourneert; // Controleer de onderste diagonaal aan de linkerkant op (i = rij, j = col; j>= 0 && i if (bord[i][j] == 1) return false; return true; } // Een recursieve nutsfunctie om N // Koninginprobleem op te lossen boolean solveNQUtil(int board[][], int col) {// Basisscenario: als alle koninginnen geplaatst zijn // retourneer dan waar als (col>= N) waar retourneert; kolom en probeer // deze koningin één voor één in alle rijen te plaatsen voor (int i = 0; i // Controleer of de koningin geplaatst kan worden op // board[i][col] if (isSafe(board, i, col )) {// Plaats deze koningin op bord[i][col] bord[i][col] = 1; // Herhaal om de rest van de koninginnen te plaatsen als (solveNQUtil(bord, col + 1) == waar) return true; // Als het plaatsen van de koningin op bord[i][col] // niet tot een oplossing leidt, // verwijder dan de koningin van bord[i][col] bord[i][col] = 0; BACKTRACK } } // Als de koningin in geen enkele rij in // deze kolom col kan worden geplaatst, retourneer dan false return false } // Deze functie lost het N Queen-probleem op met behulp van // Backtracking // het probleem oplossen. Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. boolean solveNQ() { int bord[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { System.out.print('Oplossing bestaat niet'); retour vals; } printSolution(bord); retourneer waar; } // Stuurprogramma om bovenstaande functie te testen public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Koningin.solveNQ(); } } // Deze code is bijgedragen door 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> |
q4 maanden
>
>
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--) als (bord[i,j] == 1) false retourneert; // Controleer de onderste diagonaal aan de linkerkant op (i = rij, j = col; j>= 0 && i if (bord[i, j] == 1) return false; return true; } // Een recursieve nutsfunctie om solve N // Queen probleem bool solveNQUtil(int [,]board, int col) {// Basisscenario: als alle koninginnen zijn geplaatst // return true if (col>= N) return true; probeer // deze koningin één voor één in alle rijen te plaatsen voor (int i = 0; i {// Controleer of de koningin geplaatst kan worden op // board[i,col] if (isSafe(board, i, col)) {// Plaats deze koningin in bord[i,col] bord[i, col] = 1; // Herhaal om de rest van de koninginnen te plaatsen als (solveNQUtil(bord, col + 1) == waar) retourneert waar // Als het plaatsen van de koningin op bord[i,col] // niet tot een oplossing leidt, // verwijder dan de koningin van bord[i,col] bord[i, col] = 0 // BACKTRACK } } // If the queen kan in geen enkele rij in // deze kolom worden geplaatst col, return false return false } // Deze functie lost het N Queen-probleem op met behulp van // Backtracking. Het gebruikt voornamelijk solveNQUtil () om // het probleem op te lossen. Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. bool solveNQ() { int [,]bord = {{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }}; if (solveNQUtil(board, 0) == false) { Console.Write('Oplossing bestaat niet'); retour vals; } printSolution(bord); retourneer waar; } // Stuurprogrammacode public static void Main(String []args) { GFG Queen = new GFG(); Koningin.solveNQ(); } } // Deze code is bijgedragen door 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 (bord[i][j]) return false // Controleer de onderste diagonaal aan de linkerkant voor (i = rij, j = col; j>= 0 && i if (bord[i] [j]) return false return true } function solveNQUtil(board, col){ // basisscenario: als alle vrouwen zijn geplaatst // retourneer dan true if(col>= N) return true // Beschouw deze kolom en probeer / te plaatsen / deze koningin in alle rijen één voor één for(let i=0;i if(isSafe(board, i, col)==true){ // Plaats deze koningin in bord[i][col] bord[i][ col] = 1 // herhaal om de rest van de vrouwen te plaatsen if(solveNQUtil(board, col + 1) == true) return true // Als het plaatsen van de koningin op bord[i][col // niet leidt tot een oplossing, dan // koningin van bord[i][col] bord[i][col] = 0 } } // als de koningin in geen enkele rij in // deze kolom col kan worden geplaatst, retourneer dan false return false } / / Deze functie lost het N Queen-probleem op met behulp van // Backtracking. Het gebruikt voornamelijk solveNQUtil() om // het probleem op te lossen. Het retourneert false als koninginnen // niet kunnen worden geplaatst, en retourneert true en // plaatsing van koninginnen in de vorm van 1s. // merk op dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. function 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('Oplossing bestaat niet') return false } printSolution(board) return true } // Stuurprogrammacode solveNQ() // Deze code is bijgedragen door shinjanpatra> |
>
>Uitvoer
. . Q . Q . . . . . . Q . Q . .>
Tijdcomplexiteit: OP!)
Hulpruimte: OP2)
Verdere optimalisatie in de is_safe()-functie:
Het idee is niet om elk element in de rechter- en linkerdiagonaal te controleren, maar in plaats daarvan de eigenschap van diagonalen te gebruiken:
- De som van i En J is constant en uniek voor elke rechterdiagonaal, waar i is de rij elementen en J is de
kolom met elementen.- Het verschil tussen i En J is constant en uniek voor elke linkerdiagonaal, waar i En J zijn respectievelijk rij en kolom van element.
Hieronder vindt u de implementatie:
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) retourneert waar; // Bekijk deze kolom en probeer // deze koningin één voor één in alle rijen te plaatsen voor (int i = 0; i // Controleer of de koningin geplaatst kan worden op // bord[i][col] // Om te controleren of een koningin kan op // bord[rij][col] worden geplaatst. We hoeven alleen maar // ld[rij-col+n-1] en rd[rij+coln] aan te vinken waarbij // ld en rd voor links en rechts // diagonaal respectievelijk if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) {// Plaats deze koningin op het bord[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Herhaal om de rest van de koninginnen te plaatsen als (solveNQUtil(board, col + 1)) return true; // Als het plaatsen van de koningin op bord[i][col] // niet tot een oplossing leidt, // verwijder dan de koningin van bord[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Als de koningin in geen enkele kan worden geplaatst rij in // deze kolom col retourneert false return false } // Deze functie lost het N Queen-probleem op met behulp van // Backtracking. Het gebruikt voornamelijk solveNQUtil() om // het probleem op te lossen. Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. bool solveNQ() { int bord[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(bord, 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
taakbeheer voor Linux
// 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) retourneert waar; // Bekijk deze kolom en probeer // deze koningin één voor één in alle rijen te plaatsen voor (int i = 0; i // Controleer of de koningin geplaatst kan worden op // bord[i][col] // Om te controleren of een koningin kan op // bord[rij][col] worden geplaatst. We hoeven alleen maar // ld[rij-col+n-1] en rd[rij+coln] aan te vinken waarbij // ld en rd voor links en rechts // diagonaal respectievelijk if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) {// Plaats deze koningin op het bord[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Herhaal om de rest van de koninginnen te plaatsen als (solveNQUtil(board, col + 1)) return true; // Als het plaatsen van de koningin op bord[i][col] // niet tot een oplossing leidt, // verwijder dan de koningin van bord[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Als de koningin in geen enkele kan worden geplaatst rij in // deze kolom col retourneert false return false } // Deze functie lost het N Queen-probleem op met behulp van // Backtracking. Het gebruikt voornamelijk solveNQUtil() om // het probleem op te lossen. Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. statische boolean solveNQ() { int bord[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0 } }; if (solveNQUtil(board, 0) == false) { System.out.printf('Oplossing bestaat niet'); retour vals; } printSolution(bord); retourneer waar; } // Stuurprogrammacode public static void main(String[] args) { solveNQ(); } } // Deze code is bijgedragen door 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) retourneert waar; // Bekijk deze kolom en probeer // deze koningin één voor één in alle rijen te plaatsen voor (int i = 0; i // Controleer of de koningin geplaatst kan worden op // bord[i,col] // Om te controleren of een koningin kan op // bord[rij,col] worden geplaatst. We hoeven alleen maar // ld[rij-col+n-1] en rd[rij+coln] aan te vinken waarbij // ld en rd voor links en rechts zijn / / diagonaal respectievelijk if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) {// Plaats deze dame op bord[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Herhaal om de rest van de koninginnen te plaatsen if (solveNQUtil(board , col + 1)) return true; // Als het plaatsen van de koningin op bord[i,col] // niet tot een oplossing leidt, // verwijder dan de koningin van bord[i,col] bord[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Als de koningin in geen enkele rij in // deze kolom col then return false return false } // Deze functie lost het N Queen-probleem op met // Backtracking. Het gebruikt voornamelijk solveNQUtil() om // het probleem op te lossen. Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. statische 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('Oplossing bestaat niet'); retour vals; } printSolution(bord); retourneer waar; } // Stuurprogrammacode public static void Main(String[] args) { solveNQ(); } } // Deze code is bijgedragen door 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) retourneert waar; // Bekijk deze kolom en probeer // deze koningin één voor één in alle rijen te plaatsen voor (laat i = 0; i {// Controleer of de koningin op // bord[i][col] // Om te controleren of een koningin geplaatst kan worden op // bord[rij][col]. We hoeven alleen maar // ld[rij-col+n-1] en rd[rij+coln] aan te vinken waarbij // ld en rd voor links staan en rechts // diagonaal respectievelijk if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) {// Plaats deze koningin in het bord [i][col] bord[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Herhaal om de rest van de koninginnen te plaatsen if (solveNQUtil(board, col + 1)) return true; // Als het plaatsen van de koningin op bord[i][col] // niet tot een oplossing leidt, // verwijder dan de koningin van bord[i][col] ] bord[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Als de koningin niet kan worden geplaatst elke rij in // deze kolom col retourneert false return false } // Deze functie lost het N Queen-probleem op met behulp van // Backtracking. Het gebruikt voornamelijk solveNQUtil() om // het probleem op te lossen. Het retourneert false als koninginnen // niet kunnen worden geplaatst, retourneert anders true en // drukt de plaatsing van koninginnen af in de vorm van 1-en. // Houd er rekening mee dat er meer dan één // oplossing kan zijn. Deze functie drukt een van de // haalbare oplossingen af. functie solveNQ() { laat bord = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == false) { document.write('Oplossing bestaat niet'); retour vals; } printSolution(bord); retourneer waar; } // Stuurprogrammacode solveNQ(); // Deze code is bijgedragen door sanjoy_62.> |
>
>Uitvoer
. . Q . Q . . . . . . Q . Q . .>
Tijdcomplexiteit: OP!)
Hulpruimte: OP)
Gerelateerde artikelen:
- Alle oplossingen afdrukken in N-Queen Probleem