Mēs esam apsprieduši Bruņinieku tūre un Žurka labirintā problēma iepriekš kā atkāpšanās problēmu piemēri. Apspriedīsim N Queen kā vēl vienu problēmas piemēru, ko var atrisināt, izmantojot atkāpšanos.
Kas ir N-Queen problēma?
The N Karaliene ir izvietošanas problēma N šaha karalienes uz an N × N šaha galdiņu, lai divas karalienes neuzbruktu viena otrai.
Piemēram, tālāk ir sniegts 4 karalienes problēmas risinājums.
Paredzamā izvade ir matricas formā, kurai ir ' J 's blokiem, kur novietotas dāmas un tukšās vietas ir attēlotas ar '.' . Piemēram, šī ir izvades matrica iepriekšminētajam 4-Queen risinājumam.
Ieteicams: lūdzu, atrisiniet to PRAKSE pirmkārt, pirms pāriet pie risinājuma.. J . .
. . . J
J . . .
. . J .
N Queen Problēma ar lietošanu Atkāpšanās :
Ideja ir izvietot karalienes pa vienai dažādās kolonnās, sākot no galējās kreisās kolonnas. Kad mēs ievietojam dāmu kolonnā, mēs pārbaudām, vai nav sadursmes ar jau novietotām dāmām. Pašreizējā kolonnā, ja atrodam rindu, kurai nav sadursmes, mēs atzīmējam šo rindu un kolonnu kā daļu no risinājuma. Ja tādu rindu nesadursmju dēļ neatrodam, tad atkāpjamies un atgriežamies viltus .
Tālāk ir parādīts iepriekš minētās pieejas rekursīvais koks:
Rekursīvs koks N Queen problēmai
Lai īstenotu ideju, veiciet tālāk norādītās darbības.
- Sāciet ar galējo kreiso kolonnu
- Ja visas dāmas ir novietotas, atgriež true
- Izmēģiniet visas pašreizējās kolonnas rindas. Katrai rindai rīkojieties šādi.
- Ja karalieni var droši novietot šajā rindā
- Pēc tam atzīmējiet šo [rinda, kolonna] kā daļu no risinājuma un rekursīvi pārbaudiet, vai karalienes ievietošana šeit noved pie risinājuma.
- Ja ievietojat karalieni [rinda, kolonna] noved pie risinājuma, tad atgriežas taisnība .
- Ja karalienes ievietošana nenoved pie risinājuma, noņemiet atzīmi [rinda, kolonna] pēc tam atgriezieties un izmēģiniet citas rindas.
- Ja visas rindas ir izmēģinātas un derīgs risinājums nav atrasts, atgriezieties viltus lai izraisītu atkāpšanos.
- Ja karalieni var droši novietot šajā rindā
Lai labāk vizualizētu šo atkāpšanās pieeju, lūdzu, skatiet 4 Karalienes problēma .
Piezīme: Mēs varam arī atrisināt šo problēmu, ievietojot dāmas arī rindās.
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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]) return false; // Pārbaudiet apakšējā diagonāle kreisajā pusē (i = rinda, j = kolonna; j>= 0 && i if (board[i][j]) return false; return true; } // Rekursīva lietderības funkcija, lai atrisinātu N // Queen problem bool solveNQUtil(int board[N][N], int col) { // bāzes reģistrs: Ja visas dāmas ir novietotas // tad atgriež true if (col>= N) return true // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienam for (int i = 0; i // Pārbaudiet, vai dāmu var novietot uz // board[i][col] if (isSafe(board, i, col) ) { // Ievietojiet šo dāmu dēlī[i][col] = 1 // atkārtojiet, lai novietotu pārējās dāmas if (solveNQUtil(board, col + 1)) return true //; Ja dāmas ievietošana dēlī[i][col] // nenoved pie risinājuma, tad // noņemiet dāmu no dēļa[i][col] board[i][col] = 0 // BACKTRACK } }; // Ja karalieni nevar ievietot nevienā rindā šajā kolonnā, tad atgriež false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil(), lai atrisinātu problēmu . Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0}}; if (risinātNQUtil(dēlis, 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)> |
>
tipa konvertēšana un liešana java
>
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]) return false; // Pārbaudiet apakšējā diagonāle kreisajā pusē (i = rinda, j = kolonna; j>= 0 && i if (board[i][j]) return false; return true; } // Rekursīva lietderības funkcija, lai atrisinātu N // Queen problem bool solveNQUtil(int board[N][N], int col) { // Bāzes gadījums: Ja visas dāmas ir novietotas // tad atgriež true if (col>= N) return true // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienam for (int i = 0; i // Pārbaudiet, vai dāmu var novietot uz // board[i][col] if (isSafe(board, i, col) ) { // Novietojiet šo dāmu dēlī[i][col] = 1 // Atkārtojiet, lai novietotu pārējās dāmas, ja (solveNQUtil(board, col + 1)) return true //; Ja dāmas ievietošana dēlī[i][col] // nenoved pie risinājuma, tad // noņemiet dāmu no dēļa[i][col] board[i][col] = 0 // BACKTRACK } }; // Ja karalieni nevar ievietot nevienā rindā šajā kolonnā, tad atgriež false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil(), lai atrisinātu problēmu . Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formātā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0}}; if (solveNQUtil(board, 0) == false) { printf('Risinājums neeksistē'); return false; } printSolution(board); atgriezt patiesu; } // Draivera programma, lai pārbaudītu iepriekš minēto funkciju int main() { solveNQ(); atgriezties 0; } // Šo kodu ir sagatavojusi Aditya Kumar (adityakumar129)> |
>
>
Java
// Java program to solve N Queen Problem using backtracking> public> class> NQueenProblem {> >final> int> N =>4>;> >// A utility function to print solution> >void> printSolution(>int> board[][])> >{> >for> (>int> i =>0>; i for (int j = 0; j if (board[i][j] == 1) System.out.print('Q '); else System.out.print('. '); } System.out.println(); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when 'col' queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens boolean isSafe(int board[][], int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row][i] == 1) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i][j] == 1) return false; // Pārbaudiet apakšējā diagonāle kreisajā pusē (i = rinda, j = kolonna; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Rekursīva utilīta funkcija lai atrisinātu N // Queen problem Būla solveNQUtil(int board[][], int col) { // Bāzes gadījums: Ja visas dāmas ir novietotas // tad atgriež true if (col>= N) return true // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienam for (int i = 0; i // Pārbaudiet, vai dāmu var novietot uz // board[i][col] if (isSafe(board, i, col )) { // Novietojiet šo dāmu dēlī[i][col] board[i][col] = 1 // Atkārtojiet, lai novietotu pārējās dāmas if (solveNQUtil(board, col + 1) == true) return; true // Ja dāmas ievietošana dēlī[i][col] // nenoved pie risinājuma, tad // noņem dāmu no dēļa[i][col] = 0; BACKTRACK } } // Ja karalieni nevar ievietot nevienā rindā šajā kolonnā, tad atgriež false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking () to // atrisināt problēmu. Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formātā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. Būla solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0}}; if (solveNQUtil(board, 0) == false) { System.out.print('Risinājums neeksistē'); return false; } printSolution(board); atgriezt patiesu; } // Draivera programma, lai pārbaudītu iepriekš minēto funkciju public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // Šī koda autors ir 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>>> >return> True> ># Consider this column and try placing> ># this queen in all rows one by one> >for> i>in> range>(N):> >if> isSafe(board, i, col):> ># Place this queen in board[i][col]> >board[i][col]>=> 1> ># Recur to place rest of the queens> >if> solveNQUtil(board, col>+> 1>)>=>=> True>:> >return> True> ># If placing queen in board[i][col> ># doesn't lead to a solution, then> ># queen from board[i][col]> >board[i][col]>=> 0> ># If the queen can not be placed in any row in> ># this column col then return false> >return> False> # This function solves the N Queen problem using> # Backtracking. It mainly uses solveNQUtil() to> # solve the problem. It returns false if queens> # cannot be placed, otherwise return true and> # placement of queens in the form of 1s.> # note that there may be more than one> # solutions, this function prints one of the> # feasible solutions.> def> solveNQ():> >board>=> [[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>],> >[>0>,>0>,>0>,>0>]]> >if> solveNQUtil(board,>0>)>=>=> False>:> >print>(>'Solution does not exist'>)> >return> False> >printSolution(board)> >return> True> # Driver Code> if> __name__>=>=> '__main__'>:> >solveNQ()> # This code is contributed by Divyanshu Mehta> |
>
>
C#
// C# program to solve N Queen Problem> // using backtracking> using> System;> > class> GFG> {> >readonly> int> N = 4;> >// A utility function to print solution> >void> printSolution(>int> [,]board)> >{> >for> (>int> i = 0; i { for (int j = 0; j { if (board[i, j] == 1) Console.Write('Q '); else Console.Write('. '); } Console.WriteLine(); } } // A utility function to check if a queen can // be placed on board[row,col]. Note that this // function is called when 'col' queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens bool isSafe(int [,]board, int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row,i] == 1) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i,j] == 1) return false; // Pārbaudiet apakšējā diagonāle kreisajā pusē (i = rinda, j = kolonna; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Rekursīva utilīta funkcija solve N // Queen problem bool solveNQUtil(int [,]board, int col) { // Bāzes gadījums: Ja visas dāmas ir novietotas // then return true if (col>= N) return true // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienam for (int i = 0; i { // Pārbaudiet, vai dāmu var novietot uz // dēļa[i,col] if (isSafe(board, i, col)) { // Ievietojiet šo dāmu dēlī[i,col] board[i, col] = 1 // Atkārtojiet, lai novietotu pārējās dāmas if (solveNQUtil(board, col + 1) == true) return true //; Ja dāmas ievietošana dēlī[i,col] // nenoved pie risinājuma, tad // noņemiet dāmu no dēļa[i,kola] = 0 // BACKTRACK } } // Ja queen nevar ievietot nevienā rindā šajā kolonnā, tad atgriež false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil (), lai atrisinātu problēmu. Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formātā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. 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('Risinājums neeksistē'); return false; } printSolution(board); atgriezt patiesu; } // Draivera kods public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // Šo kodu ir sagatavojis Princi Singhs> |
>
javascript nolaižamā izvēlne
>
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 // Pārbaudiet apakšējā diagonāle kreisajā pusē (i = rinda, j = kolonna; j>= 0 && i if (board[i] [j]) return false return true } funkcija solveNQUtil(board, col){ // pamata gadījums: Ja visas dāmas ir novietotas // tad atgriež true if(col>= N) return true // Apsveriet šo kolonnu un mēģiniet ievietot // / šī karaliene visās rindās pa vienai for(let i=0;i if(isSafe(board, i, col)==true){ // Novietojiet šo karalieni board[i][col] board[i][ col] = 1 // atkārto, lai novietotu pārējās dāmas if(solveNQUtil(board, col + 1) == true) return true // Ja dāmas ievietošana dēlī[i][col // nenoved pie risinājums, tad // karaliene no board[i][col] board[i][col] = 0 } } // ja dāmu nevar ievietot nevienā rindā // šajā kolonnā kolonna, tad atgriež false return false } / / Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil(), lai // atrisinātu problēmu. Tā atgriež false, ja nevar ievietot dāmas, pretējā gadījumā atgriež true un // dāmu izvietojumu. 1s. // ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. funkcija solveNQ(){ let board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] ja (solveNQUtil(board, 0) == false){ document.write('Risinājums neeksistē') return false } printSolution(board) return true } // Draivera kods solveNQ() // Šo kodu piedāvā shinjanpatra>> |
>. . Q . Q . . . . . . Q . Q . .>
Laika sarežģītība: O (N!)
Palīgtelpa: O(N2)
Papildu optimizācija is_safe() funkcijā:
Ideja nav pārbaudīt katru elementu labajā un kreisajā diagonālē, tā vietā izmantojiet diagonāļu īpašību:
- Summa no i un j ir nemainīgs un unikāls katrai labai diagonālei, kur i ir elementu rinda un j ir
elementu kolonna.- Atšķirība starp i un j ir nemainīga un unikāla katrai kreisajai diagonālei, kur i un j ir attiecīgi elementa rinda un kolonna.
Tālāk ir norādīta ieviešana:
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) atgriež patiesu; // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienam, lai (int i = 0; i // Pārbaudiet, vai karalieni var novietot uz // dēļa[i][col] // Lai pārbaudītu, vai dāmu var novietot uz // dēļa[rinda][kolonna]. Mums vienkārši jāatzīmē // ld[rinda+n-1] un rd[rinda+kolna], kur // ld un rd ir kreisais un pa labi // diagonāli attiecīgi if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Novietojiet šo dāmu dēlī[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1, ja (solveNQUtil(board, col + 1)) return true // Ja dāmas ievietošana dēlī[i][col] // nenoved pie risinājuma, tad // noņemiet dāmu no dēļa[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Ja karalieni nevar ievietot rindu // šajā kolonnā, tad atgriež false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil(), lai // atrisinātu problēmu. Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formātā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0}}; if (risinātNQUtil(dēlis, 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
java elseif
// 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) atgriež patiesu; // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienam, lai (int i = 0; i // Pārbaudiet, vai karalieni var novietot uz // dēļa[i][col] // Lai pārbaudītu, vai dāmu var novietot uz // dēļa[rinda][kolonna]. Mums vienkārši jāatzīmē // ld[rinda+n-1] un rd[rinda+kolna], kur // ld un rd ir kreisais un pa labi // diagonāli attiecīgi if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Novietojiet šo dāmu dēlī[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1, ja (solveNQUtil(board, col + 1)) return true // Ja dāmas ievietošana dēlī[i][col] // nenoved pie risinājuma, tad // noņemiet dāmu no dēļa[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Ja karalieni nevar ievietot rindu // šajā kolonnā, tad atgriež false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil(), lai // atrisinātu problēmu. Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formātā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. statisks Būla solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0} }; if (solveNQUtil(board, 0) == false) { System.out.printf('Risinājums neeksistē'); return false; } printSolution(board); atgriezt patiesu; } // Draivera kods public static void main(String[] args) { solveNQ(); } } // Šo kodu ir sagatavojis Princi Singhs> |
>
>
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>>> >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) atgriež patiesu; // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienam for (int i = 0; i // Pārbaudiet, vai karalieni var novietot uz // dēļa[i,col] // Lai pārbaudītu, vai dāmu var novietot uz // dēļa[rinda,kola]. Mums vienkārši jāatzīmē // ld[rinda-kola+n-1] un rd[rinda+kolons], kur // ld un rd ir pa kreisi un pa labi / / diagonāle attiecīgi if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Novietojiet šo dāmu dēlī[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; , col + 1)) return true // Ja dāmas ievietošana dēlī[i,col] // nenoved pie risinājuma, tad // noņemiet dāmu no board[i,col] board[i,col]; = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Ja karalieni nevar ievietot nevienā rindā šajā kolonnā then return false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil(), lai // atrisinātu problēmu. Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formātā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. static Bool solveNQ() { int[, ] dēlis = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0}}; if (solveNQUtil(board, 0) == false) { Console.Write('Risinājums neeksistē'); return false; } printSolution(board); atgriezt patiesu; } // Draivera kods public static void Main(String[] args) { solveNQ(); } } // Šo kodu sniedz Rajput-Ji> |
>
>
Javascript
kinoaktrise Kajal
> >// 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) atgriež patiesu; // Apsveriet šo kolonnu un mēģiniet ievietot // šo dāmu visās rindās pa vienai (lai i = 0; i { // Pārbaudiet, vai karalieni var novietot uz // dēļa[i][col] // Lai pārbaudītu ja dāmu var novietot uz // dēļa[rinda][kolonna]. Mums vienkārši jāatzīmē // ld[rinda-kola+n-1] un rd[rinda+kolons], kur // ld un rd ir pa kreisi un pa labi // attiecīgi pa diagonāli if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Novietojiet šo dāmu dēlī [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; if (solveNQUtil(board, col + 1)) return true // Ja dāmas ievietošana board[i][col] // nenoved pie risinājuma, tad // noņem dāmu no dēļa[i][col; ] board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Ja nevar ievietot karalieni jebkura rindiņa // šajā kolonnā, tad atgriež false return false } // Šī funkcija atrisina N Queen problēmu, izmantojot // Backtracking Tā galvenokārt izmanto solveNQUtil(), lai // atrisinātu problēmu. Tas atgriež false, ja dāmas // nevar novietot, pretējā gadījumā atgriež patiesu un // izdrukā dāmu izvietojumu 1 formātā. // Lūdzu, ņemiet vērā, ka var būt vairāki // risinājumi, šī funkcija izdrukā vienu no // iespējamajiem risinājumiem. funkcija 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('Risinājums neeksistē'); return false; } printSolution(board); atgriezt patiesu; } // Draivera kods solveNQ(); // Šo kodu ir sagatavojis sanjoy_62.>> |
>. . Q . Q . . . . . . Q . Q . .>
Laika sarežģītība: O (N!)
Palīgtelpa: O(N)
Saistītie raksti:
- Visu N-Queen problēmas risinājumu drukāšana