Omówiliśmy Wycieczka rycerska I Szczur w labiryncie problem wcześniej jako przykłady problemów z cofaniem się. Omówmy N Queen jako kolejny przykładowy problem, który można rozwiązać za pomocą cofania.
Jaki jest problem N-Queen?
The N Królowa jest problemem umieszczenia N królowe szachowe na N×N szachownicy, tak aby żadne dwie królowe nie atakowały się nawzajem.
Na przykład poniżej znajduje się rozwiązanie problemu 4 królowych.
Oczekiwany wynik ma postać macierzy, która ma „ Q „s” dla bloków, w których umieszczane są królowe, a puste przestrzenie są reprezentowane przez „.” . Na przykład poniżej znajduje się macierz wyjściowa dla powyższego rozwiązania 4-Queen.
Zalecane: Proszę o rozwiązanie ĆWICZYĆ najpierw, zanim przejdziemy do rozwiązania.. Q . .
. . . Q
Q . . .
. . Q .
N Queen Problem z używaniem Cofanie się :
Pomysł jest taki, aby umieścić królowe jedna po drugiej w różnych kolumnach, zaczynając od kolumny znajdującej się najbardziej na lewo. Kiedy ustawiamy hetmana w kolumnie, sprawdzamy, czy nie koliduje z już umieszczonymi hetmanami. Jeśli w bieżącej kolumnie znajdziemy wiersz, dla którego nie ma kolizji, zaznaczamy ten wiersz i kolumnę jako część rozwiązania. Jeśli z powodu kolizji nie znajdziemy takiego rzędu, to cofamy się i wracamy FAŁSZ .
Poniżej znajduje się drzewo rekurencyjne powyższego podejścia:
Drzewo rekurencyjne dla problemu N Queen
Aby wdrożyć pomysł, wykonaj kroki wymienione poniżej:
- Zacznij od skrajnej lewej kolumny
- Jeśli wszystkie królowe są umieszczone, zwróć wartość true
- Wypróbuj wszystkie wiersze w bieżącej kolumnie. Wykonaj poniższe czynności dla każdego wiersza.
- Jeśli królową uda się bezpiecznie umieścić w tym rzędzie
- Następnie zaznacz to [wiersz, kolumna] jako część rozwiązania i rekurencyjnie sprawdź, czy umieszczenie tutaj hetmana prowadzi do rozwiązania.
- Jeśli umieścisz królową [wiersz, kolumna] prowadzi do rozwiązania, a następnie wraca PRAWDA .
- Jeśli umieszczenie hetmana nie doprowadzi do rozwiązania, odznacz to [wiersz, kolumna] następnie cofnij się i wypróbuj inne rzędy.
- Jeśli wypróbowano wszystkie wiersze i nie znaleziono prawidłowego rozwiązania, wróć FAŁSZ aby wywołać cofanie się.
- Jeśli królową uda się bezpiecznie umieścić w tym rzędzie
Aby uzyskać lepszą wizualizację tego podejścia polegającego na wycofywaniu się, zobacz 4 Problem z królową .
Notatka: Możemy również rozwiązać ten problem, umieszczając królowe również w rzędach.
drzewo avl
Poniżej implementacja powyższego podejścia:
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]) zwróć fałsz; // Sprawdź dolną przekątną po lewej stronie dla (i = wiersz, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Rekurencyjna funkcja użyteczności do rozwiązywania N // Problem z królową bool SolNQUtil(int board[N][N], int col) { // przypadek podstawowy: Jeśli wszystkie królowe są umieszczone //, zwróć wartość true if (col>= N) return true; // Rozważ tę kolumnę i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim dla (int i = 0; i // Sprawdź, czy hetman można umieścić na // board[i][col] if (isSafe(board, i, col) ) { // Umieść ten hetman na planszy[i][col] board[i][col] = 1; // powtórz, aby umieścić resztę hetmanów if (solveNQUtil(board, col + 1)) return true; Jeśli umieszczenie hetmana na planszy[i][col] // nie doprowadzi do rozwiązania, to // usuń hetmana z planszy[i][col] board[i][col] = 0 // BACKTRACK } }; // Jeśli królowej nie można umieścić w żadnym wierszu // tej kolumny, col then return false return false; } // Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Do // rozwiązania problemu używa głównie metody SolveNQUtil(). . Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje rozmieszczenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. bool rozwiążNQ() { int tablica[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { cout<< 'Solution does not exist'; return false; } printSolution(board); return true; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> |
>
>
C
// C program to solve N Queen Problem using backtracking> #define N 4> #include> #include> // A utility function to print solution> void> printSolution(>int> board[N][N])> {> >for> (>int> i = 0; i for (int j = 0; j if(board[i][j]) printf('Q '); else printf('. '); } printf('
'); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens bool isSafe(int board[N][N], int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row][i]) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) zwróć fałsz; // Sprawdź dolną przekątną po lewej stronie dla (i = wiersz, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Rekurencyjna funkcja użyteczności do rozwiązywania N // Problem z królową bool SolNQUtil(int board[N][N], int col) { // Przypadek podstawowy: jeśli wszystkie królowe są umieszczone //, zwróć wartość true if (col>= N) return true; // Rozważ tę kolumnę i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim dla (int i = 0; i // Sprawdź, czy hetman można umieścić na // board[i][col] if (isSafe(board, i, col) ) { // Umieść ten hetman na planszy[i][col] board[i][col] = 1; // Powtórz, aby umieścić resztę hetmanów if (solveNQUtil(board, col + 1)) return true; Jeśli umieszczenie hetmana na planszy[i][col] // nie doprowadzi do rozwiązania, to // usuń hetmana z planszy[i][col] board[i][col] = 0 // BACKTRACK } }; // Jeśli królowej nie można umieścić w żadnym wierszu // tej kolumny, col then return false return false; } // Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Do // rozwiązania problemu używa głównie metody SolveNQUtil(). . Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje rozmieszczenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. bool rozwiążNQ() { int tablica[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { printf('Rozwiązanie nie istnieje'); zwróć fałsz; } printSolution(tablica); zwróć wartość true; } // Program sterownika do testowania powyższej funkcji int main() {solveNQ(); zwróć 0; } // Autorem tego kodu jest Aditya Kumar (adityakumar129)> |
>
>
Jawa
// 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) return false; // Sprawdź dolną przekątną po lewej stronie dla (i = wiersz, j = col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Rekurencyjna funkcja użyteczności to rozwiązać N // Problem z królową boolean SolNQUtil(int board[][], int col) { // Przypadek podstawowy: jeśli wszystkie królowe są umieszczone //, zwróć wartość true if (col>= N) return true; // Rozważ to kolumnie i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim dla (int i = 0; i // Sprawdź, czy hetman można umieścić na // board[i][col] if (isSafe(board, i, col )) { // Umieść ten hetman na planszy[i][col] board[i][col] = 1; // Powtórz, aby umieścić resztę hetmanów if (solveNQUtil(board, col + 1) == true) return true; // Jeśli umieszczenie hetmana na planszy[i][col] // nie doprowadzi do rozwiązania, to // usuń hetmana z planszy[i][col] board[i][col] = 0; BACKTRACK } } // Jeśli królowej nie można umieścić w żadnym wierszu // tej kolumny, zwróć fałsz return false; } // Ta funkcja rozwiązuje problem N królowej za pomocą // Wykorzystuje głównie metodę SolNQUtil (). // Rozwiąż problem. Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje rozmieszczenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. wartość logiczna rozwiązaniaNQ() { int tablica[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { System.out.print('Rozwiązanie nie istnieje'); zwróć fałsz; } printSolution(tablica); zwróć wartość true; } // Program sterownika do testowania powyższej funkcji public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Królowa.rozwiążNQ(); } } // Autorem tego kodu jest 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> |
>
różnica między dwoma ciągami znaków w Pythonie
>
C#
środkowy przycisk CSS
// 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) return false; // Sprawdź dolną przekątną po lewej stronie dla (i = wiersz, j = col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Rekurencyjna funkcja użyteczności rozwiązać N // Problem z królową bool SolNQUtil(int [,]board, int col) { // Przypadek podstawowy: jeśli wszystkie królowe są umieszczone //, zwróć wartość true if (col>= N) return true; // Rozważ tę kolumnę i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim for (int i = 0; i { // Sprawdź, czy hetman można umieścić na // board[i,col] if (isSafe(board, i, col)) { // Umieść ten hetman na planszy[i,col] board[i, col] = 1; // Powtórz, aby umieścić resztę hetmanów if (solveNQUtil(board, col + 1) == true) return true; Jeśli umieszczenie hetmana na planszy[i,col] // nie doprowadzi do rozwiązania, // usuń hetman z planszy[i,col] board[i, col] = 0; // BACKTRACK } } // Jeśli królowej nie można umieścić w żadnym wierszu // tej kolumny col, następnie zwróć fałsz return false; } // Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Do // rozwiązania problemu używa głównie metody SolveNQUtil (). Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje rozmieszczenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. bool rozwiążNQ() { 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('Rozwiązanie nie istnieje'); zwróć fałsz; } printSolution(tablica); zwróć wartość true; } // Kod sterownika public static void Main(String []args) { Królowa GFG = nowy GFG(); Królowa.rozwiążNQ(); } } // Ten kod jest dziełem Princi Singha> |
>
>
JavaScript
> // JavaScript program to solve N Queen> // Problem using backtracking> const N = 4> function> printSolution(board)> {> >for>(let i = 0; i { for(let j = 0; j { if(board[i][j] == 1) document.write('Q ') else document.write('. ') } document.write('') } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are // already placed in columns from 0 to col -1. // So we need to check only left side for // attacking queens function isSafe(board, row, col) { // Check this row on left side for(let i = 0; i if(board[row][i] == 1) return false } // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j]) return false // Sprawdź dolną przekątną po lewej stronie dla (i = rząd, j = col; j>= 0 && i if (board[i] [j]) return false return true } funkcja SolNQUtil(board, col){ // przypadek podstawowy: Jeśli wszystkie królowe są umieszczone //, zwróć true if(col>= N) return true // Rozważ tę kolumnę i spróbuj umieścić / / ten hetman we wszystkich rzędach jeden po drugim for(let i=0;i if(isSafe(board, i, col)==true){ // Umieść ten hetman na planszy[i][col] board[i][ col] = 1 // powtórz, aby umieścić resztę hetmanów if(solveNQUtil(board, col + 1) == true) return true // Jeśli umieszczenie hetmana na planszy[i][col // nie prowadzi do rozwiązanie, to // hetman z planszy[i][col] board[i][col] = 0 } } // jeśli hetman nie może zostać umieszczony w żadnym wierszu w // tej kolumnie col then return false return false } / / Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Używa głównie metody SolNQUtil() do // rozwiązania problemu. Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // położenie królowych 1s. // pamiętaj, że może istnieć więcej niż jedno // rozwiązanie, ta funkcja wypisuje jedno z // możliwych rozwiązań. funkcja rozwiążNQ(){ niech tablica = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] jeśli (solveNQUtil(board, 0) == false){ document.write('Rozwiązanie nie istnieje') return false } printSolution(board) return true } // Kod sterownika SolveNQ() // Ten kod został opracowany przez shinjanpatra> |
>
>Wyjście
. . Q . Q . . . . . . Q . Q . .>
Złożoność czasowa: NA!)
Przestrzeń pomocnicza: NA2)
Dalsza optymalizacja w funkcji is_safe():
Pomysł nie polega na sprawdzaniu każdego elementu po prawej i lewej przekątnej, zamiast tego należy skorzystać z własności przekątnych:
- Suma I I J jest stała i unikalna dla każdej prawej przekątnej, gdzie I jest rządem elementów i J jest
kolumna elementów.- Różnica pomiędzy I I J jest stała i unikalna dla każdej lewej przekątnej, gdzie I I J są odpowiednio wierszem i kolumną elementu.
Poniżej implementacja:
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) zwraca prawdę; // Rozważ tę kolumnę i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim dla (int i = 0; i // Sprawdź, czy hetman można umieścić na // planszy[i][col] // Aby sprawdzić, czy hetmana można umieścić na // planszy[row][col]. Musimy tylko sprawdzić // ld[row-col+n-1] i rd[row+coln] gdzie // ld i rd oznaczają lewą i prawa // odpowiednio przekątna if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umieść ten hetman na planszy[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Powtórz, aby umieścić resztę królowych if (solveNQUtil(board, col + 1)) return true; // Jeśli umieszczenie hetmana na planszy[i][col] // nie doprowadzi do rozwiązania, to // usuń hetman z planszy[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Jeśli nie można umieścić hetmana w żadnym miejscu wiersz w // tej kolumnie col następnie zwróć fałsz return false; } // Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Do // rozwiązania problemu używa głównie funkcji SolNQUtil(). Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje rozmieszczenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. bool rozwiążNQ() { int tablica[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { cout<< 'Solution does not exist'; return false; } printSolution(board); return true; } // Driver program to test above function int main() { solveNQ(); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> |
>
>
Jawa
// 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) zwraca prawdę; // Rozważ tę kolumnę i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim dla (int i = 0; i // Sprawdź, czy hetman można umieścić na // planszy[i][col] // Aby sprawdzić, czy hetmana można umieścić na // planszy[row][col]. Musimy tylko sprawdzić // ld[row-col+n-1] i rd[row+coln] gdzie // ld i rd oznaczają lewą i prawa // odpowiednio przekątna if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umieść ten hetman na planszy[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Powtórz, aby umieścić resztę królowych if (solveNQUtil(board, col + 1)) return true; // Jeśli umieszczenie hetmana na planszy[i][col] // nie doprowadzi do rozwiązania, to // usuń hetman z planszy[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Jeśli nie można umieścić hetmana w żadnym miejscu wiersz w // tej kolumnie col następnie zwróć fałsz return false; } // Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Do // rozwiązania problemu używa głównie funkcji SolNQUtil(). Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje rozmieszczenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. statyczne rozwiązanie logiczne NQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0 } }; if (solveNQUtil(board, 0) == false) { System.out.printf('Rozwiązanie nie istnieje'); zwróć fałsz; } printSolution(tablica); zwróć wartość true; } // Kod sterownika public static void main(String[] args) {solveNQ(); } } // Ten kod jest dziełem Princi Singha> |
>
>
Python3
wyszukiwanie BFS
# 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) zwraca prawdę; // Rozważ tę kolumnę i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim dla (int i = 0; i // Sprawdź, czy hetman można umieścić na // board[i,col] // Aby sprawdzić, czy a królową można umieścić na // board[row,col]. Musimy tylko sprawdzić // ld[row-col+n-1] i rd[row+coln] gdzie // ld i rd oznaczają lewą i prawą stronę / / przekątna odpowiednio if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umieść ten hetman na planszy[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Powtórz, aby umieścić resztę hetmanów if (solveNQUtil(board , col + 1)) return true; // Jeśli umieszczenie hetmana na planszy[i,col] // nie doprowadzi do rozwiązania, to // usuń hetmana z planszy[i,col] board[i, col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Jeśli hetmana nie można umieścić w żadnym wierszu w // tej kolumnie col następnie zwróć fałsz return false; } // Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Do // rozwiązania problemu używa głównie metody SolNQUtil(). Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje rozmieszczenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. statyczny bool rozwiązujNQ() { int[, ] tablica = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { Console.Write('Rozwiązanie nie istnieje'); zwróć fałsz; } printSolution(tablica); zwróć wartość true; } // Kod sterownika public static void Main(String[] args) {solveNQ(); } } // Ten kod został napisany przez Rajput-Ji> |
>
>
strona internetowa taka jak coomeet
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) zwraca prawdę; // Rozważ tę kolumnę i spróbuj umieścić // ten hetman we wszystkich wierszach jeden po drugim dla (let i = 0; i { // Sprawdź, czy hetman można umieścić na // planszy[i][col] // Aby sprawdzić czy hetman może zostać umieszczony na // planszy[wiersz][col]. Musimy tylko sprawdzić // ld[row-col+n-1] i rd[row+coln] gdzie // ld i rd oznaczają lewą stronę i prawa // odpowiednio przekątna if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umieść ten hetman na planszy [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Powtórz, aby umieścić resztę hetmanów if (solveNQUtil(board, col + 1)) return true; // Jeśli umieszczenie hetmana na planszy[i][col] // nie doprowadzi do rozwiązania, to // usuń hetmana z planszy[i][col] ] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // Jeśli nie można umieścić hetmana dowolny wiersz w // tej kolumnie col następnie zwróć fałsz return false; } // Ta funkcja rozwiązuje problem N Queen za pomocą // Wycofywania się. Do // rozwiązania problemu używa głównie funkcji SolNQUtil(). Zwraca wartość false, jeśli // nie można umieścić królowych, w przeciwnym razie zwraca wartość true i // wypisuje położenie hetmanów w postaci jedynek. // Należy pamiętać, że może istnieć więcej niż jedno // rozwiązanie. Ta funkcja wypisuje jedno z // możliwych rozwiązań. funkcja rozwiążNQ() { niech tablica = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == false) { document.write('Rozwiązanie nie istnieje'); zwróć fałsz; } printSolution(tablica); zwróć wartość true; } // Kod sterownika SolNQ(); // Ten kod został napisany przez sanjoy_62.> |
>
>Wyjście
. . Q . Q . . . . . . Q . Q . .>
Złożoność czasowa: NA!)
Przestrzeń pomocnicza: NA)
Powiązane artykuły:
- Drukowanie wszystkich rozwiązań problemu N-Queen