Olemme keskustelleet Ritarin kiertue ja Rotta sokkelossa ongelma aiemmin esimerkkeinä Backtracking-ongelmista. Tarkastellaanpa N Queeniä toisena esimerkkiongelmana, joka voidaan ratkaista paluumatkalla.
Mikä on N-Queen-ongelma?
The N Queen on sijoittamisen ongelma N shakki kuningattaret an N × N shakkilaudalla, jotta kaksi kuningatarta ei hyökkää toisiaan vastaan.
Esimerkiksi seuraava on ratkaisu 4 Queen -ongelmaan.
Odotettu tulos on matriisin muodossa, jossa on ' K 's lohkoille, joihin kuningattaret on sijoitettu ja tyhjiä tiloja edustaa '.' . Esimerkiksi seuraava on lähtömatriisi yllä olevalle 4-Queen-ratkaisulle.
Suositus: Ratkaise se HARJOITELLA ensin, ennen kuin siirryt ratkaisuun.. Q . .
. . . K
Q . . .
. . Q .
N Queen Ongelma käytössä Perääntyminen :
Ideana on sijoittaa kuningattaret yksitellen eri sarakkeisiin alkaen vasemmanpuoleisesta sarakkeesta. Kun sijoitamme kuningattaren sarakkeeseen, tarkistamme, onko ristiriitoja jo asetettujen kuningattareiden kanssa. Jos nykyisestä sarakkeesta löydämme rivin, jolle ei ole ristiriitaa, merkitsemme tämän rivin ja sarakkeen osaksi ratkaisua. Jos emme löydä tällaista riviä yhteenottojen vuoksi, perääntymme ja palaamme väärä .
Alla on yllä olevan lähestymistavan rekursiivinen puu:
Rekursiivinen puu N Queen -ongelmalle
Toteuta idea noudattamalla alla mainittuja vaiheita:
- Aloita vasemmanpuoleisesta sarakkeesta
- Jos kaikki kuningattaret sijoitetaan, palauta tosi
- Kokeile kaikkia nykyisen sarakkeen rivejä. Tee seuraava jokaiselle riville.
- Jos kuningatar voidaan sijoittaa turvallisesti tähän riviin
- Merkitse sitten tämä [rivi sarake] osana ratkaisua ja tarkista rekursiivisesti, johtaako kuningattaren sijoittaminen tähän ratkaisuun.
- Jos laitat kuningattaren sisään [rivi sarake] johtaa ratkaisuun ja palaa sitten takaisin totta .
- Jos kuningattaren sijoittaminen ei johda ratkaisuun, poista tämä merkki [rivi sarake] palaa sitten taaksepäin ja kokeile muita rivejä.
- Jos kaikki rivit on kokeiltu ja kelvollista ratkaisua ei löydy, palauta väärä käynnistääkseen perääntymisen.
- Jos kuningatar voidaan sijoittaa turvallisesti tähän riviin
Jos haluat visualisoida paremmin tätä taaksepäin suuntautuvaa lähestymistapaa, katso 4 Queen-ongelma .
Huomautus: Voimme myös ratkaista tämän ongelman sijoittamalla kuningattaret myös riveihin.
Alla on yllä olevan lähestymistavan toteutus:
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; // Tarkista vasemman puolen alempi diagonaali (i = rivi, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Rekursiivinen apufunktio ratkaisemaan N // Kuningatar ongelma bool solveNQUtil(int board[N][N], int col) { // perustapaus: Jos kaikki kuningattaret on sijoitettu // niin palauttaa true if (col>= N) return true // Tarkastellaan tätä saraketta ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (int i = 0; i // Tarkista, voidaanko kuningatar sijoittaa // board[i][col] if (isSafe(board, i, col) ) { // Aseta tämä kuningatar boardiin[i][col] = 1 // toista loput kuningattaret jos (solveNQUtil(board, col + 1)) return true //; Jos kuningattaren sijoittaminen boardiin[i][col] // ei johda ratkaisuun, // poista emo boardista[i][col] board[i][col] = 0 // BACKTRACK } }; // Jos kuningatarta ei voi sijoittaa millekään riville // tässä sarakkeessa, palauttaa false return false } // Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtrackingia . Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (ratkaiseNQUtil(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)> |
satunnaisarvogeneraattori javassa
>
>
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; // Tarkista vasemman puolen alempi diagonaali (i = rivi, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // Rekursiivinen apufunktio ratkaisemaan N // Kuningatarongelma bool solveNQUtil(int board[N][N], int col) { // Perustapaus: Jos kaikki kuningattaret on sijoitettu // niin palauttaa true if (col>= N) return true // Tarkastellaan tätä saraketta ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (int i = 0; i // Tarkista, voidaanko kuningatar sijoittaa // board[i][col] if (isSafe(board, i, col) ) { // Aseta tämä kuningatar boardiin[i][col] board[i][col] = 1 // Toista loput kuningattaret jos (solveNQUtil(board, col + 1)) return true //; Jos kuningattaren sijoittaminen boardiin[i][col] // ei johda ratkaisuun, // poista emo boardista[i][col] board[i][col] = 0 // BACKTRACK } }; // Jos kuningatarta ei voi sijoittaa millekään riville // tässä sarakkeessa, palauttaa false return false } // Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtrackingia . Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. 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('Ratkaisua ei ole olemassa'); palauttaa väärä; } printSolution(board); palauttaa tosi; } // Ohjainohjelma yllä olevan funktion testaamiseen int main() { solveNQ(); paluu 0; } // Tämän koodin on antanut 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; // Tarkista vasemman puolen alempi diagonaali (i = rivi, j = col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Rekursiivinen apufunktio ratkaista N // Kuningatarongelma Boolean solveNQUtil(int board[][], int col) { // Perustapaus: Jos kaikki kuningattaret on sijoitettu // niin palauttaa true if (col>= N) return true // Harkitse tätä sarake ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (int i = 0; i // Tarkista, voidaanko kuningatar sijoittaa // board[i][col] if (isSafe(board, i, col )) { // Aseta tämä kuningatar boardiin[i][col] board[i][col] = 1 // Toista asettaaksesi loput kuningattaret if (solveNQUtil(board, col + 1) == true) return; true // Jos kuningattaren asettaminen laudalle[i][col] // ei johda ratkaisuun, // poista kuningatar board[i][col] = 0; BACKTRACK } } // Jos kuningatarta ei voi sijoittaa millekään riville // tässä sarakkeessa, palauttaa false return false } // Tämä funktio ratkaisee N Queen -ongelman käyttämällä // Backtracking -toimintoa // ratkaise ongelma. Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. boolean 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('Ratkaisua ei ole olemassa'); palauttaa väärä; } printSolution(board); palauttaa tosi; } // Ohjainohjelma testattavaksi yllä oleva toiminto public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // Tämän koodin on antanut Abhishek Shankhadhar> |
>
>
Python 3
# 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#
distributiivinen laki Boolen algebra
// 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; // Tarkista vasemman puolen alempi diagonaali (i = rivi, j = col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Rekursiivinen apufunktio ratkaista N // Kuningatarongelma bool solveNQUtil(int [,]board, int col) { // Perustapaus: Jos kaikki kuningattaret on sijoitettu // niin palauttaa true if (col>= N) return true // Tarkastellaan tätä saraketta ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (int i = 0; i { // Tarkista, voidaanko kuningatar sijoittaa // board[i,col] jos (isSafe(board, i, col)) { // Aseta tämä kuningatar board[i, col] = 1 // Toista loput kuningattaret if (solveNQUtil(board, col + 1) == true) return true //; Jos kuningattaren sijoittaminen boardiin[i,col] // ei johda ratkaisuun, // poista kuningatar board[i,col] = 0 // BACKTRACK } } // Jos kuningatarta ei voi sijoittaa millekään riville // tässä sarakkeessa, sitten palauttaa false return false } // Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtracking -toimintoa. Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. 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('Ratkaisua ei ole olemassa'); palauttaa väärä; } printSolution(board); palauttaa tosi; } // Ohjainkoodi public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // Tämän koodin on toimittanut 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 (board[i][j]) return false // Tarkista vasemman puolen alempi diagonaali (i = rivi, j = sarake; j>= 0 && i if (board[i] [j]) return false return true } funktio solveNQUtil(board, col){ // perustapaus: Jos kaikki kuningattaret on sijoitettu // niin palauta tosi if(col>= N) return true // Harkitse tätä saraketta ja yritä sijoittaa // / tämä kuningatar kaikilla riveillä yksitellen for(olkoon i=0;i if(isSafe(board, i, col)==true){ // Sijoita tämä kuningatar boardiin[i][col] board[i][ col] = 1 // toista loput kuningattaret if(solveNQUtil(board, col + 1) == true) return true // Jos kuningattaren sijoittaminen boardiin[i][col // ei johda ratkaisu, sitten // queen from board[i][col] board[i][col] = 0 } } // jos kuningatarta ei voi sijoittaa millekään riville // tässä sarakkeessa sarake niin palauta false return false } / / Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtrackingia. Se käyttää pääasiassa solveNQUtil()-komentoa ongelman ratkaisemiseen // Palauttaa epätosi, jos kuningattaret // eivät voi sijoittaa, muussa tapauksessa palauttaa true ja // kuningattareiden sijoittelun. 1s. // Huomaa, että ratkaisuja voi olla useampia //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. funktio solveNQ(){ anna board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] jos (solveNQUtil(board, 0) == false){ document.write('Ratkaisua ei ole olemassa') return false } printSolution(board) return tosi } // Ohjainkoodi solveNQ() // Tämän koodin tarjoaa shinjanpatra>> |
>. . Q . Q . . . . . . Q . Q . .>
Aika monimutkaisuus: PÄÄLLÄ!)
Aputila: PÄÄLLÄ2)
Lisäoptimointi is_safe()-funktiossa:
Ajatuksena ei ole tarkistaa jokaista elementtiä oikeasta ja vasemmasta diagonaalista, vaan käyttää diagonaalien ominaisuutta:
- Summa i ja j on vakio ja yksilöllinen jokaiselle oikealle diagonaalille, missä i on elementtirivi ja j on
elementtien sarake.- Ero välillä i ja j on vakio ja yksilöllinen jokaiselle vasemmalle lävistäjälle, missä i ja j ovat elementin rivi ja sarake.
Alla toteutus:
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) palauttaa tosi; // Harkitse tätä saraketta ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (int i = 0; i // Tarkista, voidaanko kuningatar sijoittaa // board[i][col] // kuningatar voidaan asettaa // laudalle[rivi][sara]. Meidän tarvitsee vain tarkistaa // ld[rivi-sarake+n-1] ja rd[rivi+sarake] missä // ld ja rd tarkoittavat vasenta ja oikea // diagonaali vastaavasti if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Aseta tämä kuningatar laudalle[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Toista loput kuningattareista; (solveNQUtil(board, col + 1)) return true // Jos kuningattaren asettaminen boardiin[i][col] // ei johda ratkaisuun, // poista kuningatar boardista[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Jos kuningatarta ei voi sijoittaa mihinkään; rivi // tämän sarakkeen sarake palauttaa sitten false return false } // Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtracking -toimintoa. Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (ratkaiseNQUtil(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)> |
>
>
Java
mvc javalle
// 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) palauttaa tosi; // Harkitse tätä saraketta ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (int i = 0; i // Tarkista, voidaanko kuningatar sijoittaa // board[i][col] // kuningatar voidaan asettaa // laudalle[rivi][sara]. Meidän tarvitsee vain tarkistaa // ld[rivi-sarake+n-1] ja rd[rivi+sarake] missä // ld ja rd tarkoittavat vasenta ja oikea // diagonaali vastaavasti if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Aseta tämä kuningatar laudalle[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Toista loput kuningattareista; (solveNQUtil(board, col + 1)) return true // Jos kuningattaren asettaminen boardiin[i][col] // ei johda ratkaisuun, // poista kuningatar boardista[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Jos kuningatarta ei voi sijoittaa mihinkään; rivi // tämän sarakkeen sarake palauttaa sitten false return false } // Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtracking -toimintoa. Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. staattinen looginen 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('Ratkaisua ei ole olemassa'); palauttaa väärä; } printSolution(board); palauttaa tosi; } // Ohjainkoodi public static void main(String[] args) { solveNQ(); } } // Tämän koodin on toimittanut Princi Singh> |
>
>
Python 3
# 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) palauttaa tosi; // Harkitse tätä saraketta ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (int i = 0; i // Tarkista, voidaanko kuningatar sijoittaa // board[i,col] // Tarkistaaksesi onko kuningatar voidaan sijoittaa // boardiin[rivi,sara].Meidän tarvitsee vain tarkistaa // ld[rivi-sarake+n-1] ja rd[rivi+sarake] missä // ld ja rd ovat vasenta ja oikeaa // / diagonaali vastaavasti if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Aseta tämä kuningatar laudalle[i, col] board[i, col] = 1 , sarake + 1)) return true // Jos kuningattaren sijoittaminen boardiin[i,col] // ei johda ratkaisuun, niin // poista emo boardista[i,col] board[i,col]; = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Jos kuningatarta ei voi sijoittaa millekään riville // tässä sarakkeessa sitten return false return false } // Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtracking -toimintoa. Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. staattinen 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('Ratkaisua ei ole olemassa'); palauttaa väärä; } printSolution(board); palauttaa tosi; } // Ohjainkoodi public static void Main(String[] args) { solveNQ(); } } // Tämän koodin tarjoaa Rajput-Ji> |
>
>
Javascript
mamta kulkarni
> >// 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) palauttaa tosi; // Harkitse tätä saraketta ja yritä sijoittaa // tämä kuningatar kaikille riveille yksitellen for (olkoon i = 0; i { // Tarkista, voidaanko kuningatar sijoittaa // board[i][col] // Tarkistaaksesi jos kuningatar voidaan sijoittaa // laudalle[rivi][sara].Meidän tarvitsee vain tarkistaa // ld[rivi-sarake+n-1] ja rd[rivi+sarake] missä // ld ja rd ovat vasemmalle ja oikea // diagonaali, jos ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Aseta tämä kuningatar laudalle [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; if (solveNQUtil(board, col + 1)) return true // Jos kuningattaren sijoittaminen boardiin[i][col] // ei johda ratkaisuun, sitten // poista kuningatar boardista[i][col; ] board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Jos kuningatarta ei voi sijoittaa; mikä tahansa rivi // tässä sarakkeessa palauttaa sitten false return false } // Tämä funktio ratkaisee N Queen -tehtävän käyttämällä // Backtrackingia. Se palauttaa epätosi, jos kuningattaret // ei voi sijoittaa, muussa tapauksessa palauttaa tosi ja // tulostaa kuningattareiden sijoittelun ykkösten muodossa. // Huomaa, että ratkaisuja voi olla useita //, tämä funktio tulostaa yhden // mahdollisista ratkaisuista. funktio solveNQ() { anna board = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == false) { document.write('Ratkaisua ei ole olemassa'); palauttaa väärä; } printSolution(board); palauttaa tosi; } // Ohjainkoodi solveNQ(); // Tämän koodin tarjoaa sanjoy_62.>> |
>. . Q . Q . . . . . . Q . Q . .>
Aika monimutkaisuus: PÄÄLLÄ!)
Aputila: PÄÄLLÄ)
Aiheeseen liittyvät artikkelit:
- Tulostetaan kaikki ratkaisut N-Queen-ongelmassa