diskutovali jsme Rytířská prohlídka a Krysa v bludišti problém dříve jako příklady problémů se zpětným sledováním. Proberme N Queen jako další příklad problému, který lze vyřešit pomocí backtrackingu.

Co je problém N-Queen?

The N Královna je problém umístění N šachové královny na an N×N šachovnici tak, aby na sebe neútočily dvě královny.

Například následující je řešení problému 4 královen.

Očekávaný výstup je ve formě matice, která má „ Q 's pro bloky, kde jsou umístěny královny a prázdná místa jsou reprezentována '.' . Například následující je výstupní matice pro výše uvedené řešení 4-Queen.

. Q . .
. . . Q
Q . . .
. . Q .

Doporučeno: Vyřešte to na PRAXE nejprve, než přejdete k řešení.

N Queen Problém při používání Zpětné sledování :

Cílem je umístit královny jednu po druhé do různých sloupců, počínaje sloupcem zcela vlevo. Když umístíme královnu do sloupce, kontrolujeme střety s již umístěnými královnami. Pokud v aktuálním sloupci najdeme řádek, u kterého není kolize, označíme tento řádek a sloupec jako součást řešení. Pokud takovou řadu kvůli střetům nenajdeme, vrátíme se a vrátíme se Nepravdivé .

Níže je rekurzivní strom výše uvedeného přístupu:

Rekurzivní strom pro problém N Queen

Při realizaci nápadu postupujte podle níže uvedených kroků:

• Začněte ve sloupci zcela vlevo
• Pokud jsou umístěny všechny královny, vrátí true
• Vyzkoušejte všechny řádky v aktuálním sloupci. Pro každý řádek proveďte následující.
  • Pokud se dá dáma bezpečně umístit do této řady
    • Pak označte toto [řádek sloupec] jako součást řešení a rekurzivně zkontrolujte, zda umístění královny zde vede k řešení.
    • Pokud umístíte královnu [řádek sloupec] vede k řešení a poté se vrátí skutečný .
    • Pokud umístění královny nevede k řešení, zrušte označení [řádek sloupec] pak se vraťte a zkuste jiné řádky.
  • Pokud byly vyzkoušeny všechny řádky a nebylo nalezeno platné řešení, vraťte se Nepravdivé spustit backtracking.

Pro lepší vizualizaci tohoto backtrackingového přístupu viz 4 Problém s královnou .

Poznámka: Tento problém můžeme také vyřešit umístěním matek do řad.

Níže je uvedena implementace výše uvedeného přístupu:

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; // Zkontrolujte spodní úhlopříčku na levé straně, zda neobsahuje (i = řádek, j = sloupec; j>= 0 && i if (board[i][j]) return false; return true; } // Rekurzivní obslužná funkce pro řešení N // Problém s královnou bool solveNQUtil(int board[N][N], int col) { // základní případ: Pokud jsou umístěny všechny královny // potom vrátí true if (col>= N) return true // Uvažujme tento sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (int i = 0; i // Zkontrolujte, zda lze dámu umístit na // board[i][col] if (isSafe(board, i, col) ) { // Umístěte tuto královnu na board[i][col] board[i][col] = 1 // opakujte umístění zbývajících dam if (solveNQUtil(board, col + 1)) return true; Pokud umístění dámy na board[i][col] // nevede k řešení, pak // odeberte dámu z boardu[i][col] board[i][col] = 0 // BACKTRACK } } // Pokud královnu nelze umístit do žádného řádku v // tomto sloupci, vrátí false return false } // Tato funkce řeší problém N královny pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil(). . Vrátí false, pokud královny // nelze umístit, jinak vrátí hodnotu true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} }; if (solveNQUtil(deska, 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]) return false; // Zkontrolujte spodní úhlopříčku na levé straně, zda neobsahuje (i = řádek, j = sloupec; j>= 0 && i if (board[i][j]) return false; return true; } // Rekurzivní obslužná funkce pro řešení N // Problém s královnou bool solveNQUtil(int board[N][N], int col) { // Základní případ: Pokud jsou umístěny všechny královny // pak vrátí true if (col>= N) return true // Uvažujme tento sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (int i = 0; i // Zkontrolujte, zda lze dámu umístit na // board[i][col] if (isSafe(board, i, col) ) { // Umístěte tuto královnu na board[i][col] board[i][col] = 1 // Opakujte umístění zbývajících dam if (solveNQUtil(board, col + 1)) return true; Pokud umístění dámy na board[i][col] // nevede k řešení, pak // odeberte dámu z boardu[i][col] board[i][col] = 0 // BACKTRACK } } // Pokud královnu nelze umístit do žádného řádku v // tomto sloupci, vrátí false return false } // Tato funkce řeší problém N královny pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil(). . Vrátí false, pokud královny // nelze umístit, jinak vrátí hodnotu true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} }; if (solveNQUtil(deska, 0) == false) { printf('Řešení neexistuje'); vrátit false; } printSolution(deska); vrátit true; } // Program ovladače k ​​otestování výše uvedené funkce int main() { solveNQ(); návrat 0; } // Tento kód přispěl Aditya Kumar (adityakumar129)>

Jáva

// 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; // Zkontrolujte spodní úhlopříčku na levé straně pro (i = řádek, j = sloupec; j>= 0 && i if (board[i][j] == 1) return false; return true; } // Rekurzivní utilitní funkce k vyřešení N // Problém s královnou boolean solveNQUtil(int board[][], int col) { // Základní případ: Jsou-li umístěny všechny královny // pak vrátí true if (col>= N) return true // Uvažujme o tom sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (int i = 0; i // Zkontrolujte, zda lze dámu umístit na // board[i][col] if (isSafe(board, i, col )) { // Umístěte tuto královnu na board[i][col] board[i][col] = 1 // Opakujte umístění zbývajících dam if (solveNQUtil(board, col + 1) == true) return; true // Pokud umístění dámy na board[i][col] // nevede k řešení, pak // odeberte dámu z boardu[i][col] board[i][col] = 0; BACKTRACK } } // Pokud královnu nelze umístit do žádného řádku // tohoto sloupce, pak vrátí false return false } // Tato funkce řeší problém N Queen pomocí // Backtracking // vyřešit problém. Vrátí false, pokud královny // nelze umístit, jinak vrátí hodnotu true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} }; if (solveNQUtil(deska, 0) == false) { System.out.print('Řešení neexistuje'); vrátit false; } printSolution(deska); vrátit true; } // Program ovladače k ​​otestování výše uvedené funkce public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // Tento kód přispěl Abhishek Shankhadhar>

Python3

# Python3 program to solve N Queen> # Problem using backtracking> global> N> N> => 4> def> printSolution(board):> > for> i> in> range> (N):> > for> j> in> range> (N):> > if> board[i][j]> => => 1> :> > print> (> 'Q'> ,end> => )> > else> :> > print> (> '.'> ,end> => )> > print> ()> # A utility function to check if a queen can> # be placed on board[row][col]. Note that this> # function is called when 'col' queens are> # already placed in columns from 0 to col -1.> # So we need to check only left side for> # attacking queens> def> isSafe(board, row, col):> > # Check this row on left side> > for> i> in> range> (col):> > if> board[row][i]> => => 1> :> > return> False> > # Check upper diagonal on left side> > for> i, j> in> zip> (> range> (row,> -> 1> ,> -> 1> ),> > range> (col,> -> 1> ,> -> 1> )):> > if> board[i][j]> => => 1> :> > return> False> > # Check lower diagonal on left side> > for> i, j> in> zip> (> range> (row, N,> 1> ),> > range> (col,> -> 1> ,> -> 1> )):> > if> board[i][j]> => => 1> :> > return> False> > return> True> def> solveNQUtil(board, col):> > # Base case: If all queens are placed> > # then return true> > if> col>> => N:> > return> True> > # Consider this column and try placing> > # this queen in all rows one by one> > for> i> in> range> (N):> > if> isSafe(board, i, col):> > # Place this queen in board[i][col]> > board[i][col]> => 1> > # Recur to place rest of the queens> > if> solveNQUtil(board, col> +> 1> )> => => True> :> > return> True> > # If placing queen in board[i][col> > # doesn't lead to a solution, then> > # queen from board[i][col]> > board[i][col]> => 0> > # If the queen can not be placed in any row in> > # this column col then return false> > return> False> # This function solves the N Queen problem using> # Backtracking. It mainly uses solveNQUtil() to> # solve the problem. It returns false if queens> # cannot be placed, otherwise return true and> # placement of queens in the form of 1s.> # note that there may be more than one> # solutions, this function prints one of the> # feasible solutions.> def> solveNQ():> > board> => [[> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ]]> > if> solveNQUtil(board,> 0> )> => => False> :> > print> (> 'Solution does not exist'> )> > return> False> > printSolution(board)> > return> True> # Driver Code> if> __name__> => => '__main__'> :> > solveNQ()> # This code is contributed by Divyanshu Mehta>

C#

// C# program to solve N Queen Problem> // using backtracking> using> System;> > class> GFG> {> > readonly> int> N = 4;> > // A utility function to print solution> > void> printSolution(> int> [,]board)> > {> > for> (> int> i = 0; i { for (int j = 0; j { if (board[i, j] == 1) Console.Write('Q '); else Console.Write('. '); } Console.WriteLine(); } } // A utility function to check if a queen can // be placed on board[row,col]. Note that this // function is called when 'col' queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens bool isSafe(int [,]board, int row, int col) { int i, j; // Check this row on left side for (i = 0; i if (board[row,i] == 1) return false; // Check upper diagonal on left side for (i = row, j = col; i>= 0 && j>= 0; i--, j--) if (board[i,j] == 1) return false; // Zkontrolujte spodní úhlopříčku na levé straně pro (i = řádek, j = sloupec; j>= 0 && i if (board[i, j] == 1) return false; return true; } // Rekurzivní obslužná funkce pro řešit N // Problém s královnou bool solveNQUtil(int [,]board, int col) { // Základní případ: Pokud jsou umístěny všechny královny // pak vrátí true if (col>= N) return true // Uvažujme tento sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (int i = 0; i { // Zkontrolujte, zda lze dámu umístit na // board[i,col] if (isSafe(board, i, col)) { // Umístěte tuto královnu do desky[i,col] deska[i, col] = 1 // Opakujte umístění zbývajících dam if (solveNQUtil(board, col + 1) == true) return true; Pokud umístění královny na board[i,col] // nevede k řešení, pak // odeberte královnu z boardu[i,col] board[i, col] = 0 // BACKTRACK } } // Pokud; queen nelze umístit do žádného řádku v // tomto sloupci col, pak return false return false } // Tato funkce řeší problém N Queen pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil (). Vrátí false, pokud královny // nelze umístit, jinak vrátí hodnotu true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. 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('Řešení neexistuje'); vrátit false; } printSolution(deska); vrátit true; } // Kód ovladače public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // Tento kód přispěl Prince 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 // Zkontrolujte spodní úhlopříčku na levé straně pro (i = řádek, j = sloupec; j>= 0 && i if (board[i] [j]) return false return true } funkce solveNQUtil(board, col){ // základní případ: Pokud jsou umístěny všechny královny // pak vrátí true if(col>= N) vrátí true // Zvažte tento sloupec a zkuste umístit / / tuto královnu ve všech řadách jednu po druhé pro (ať i=0;i if(isSafe(board, i, col)==true){ // Umístěte tuto královnu na desku[i][col] desku[i][ col] = 1 // opakujte, abyste umístili zbytek dam if(solveNQUtil(board, col + 1) == true) return true // Pokud umístění dámy na board[i][col // nevede k řešení, pak // královna z boardu[i][col] board[i][col] = 0 } } // pokud královnu nelze umístit do žádného řádku v // tomto sloupci col then return false return false } / / Tato funkce řeší problém N Queen pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil() Vrací false, pokud královny // nelze umístit, jinak vrací true a // umístění královen ve tvaru. 1s. // všimněte si, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. funkce solveNQ(){ let board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] pokud (solveNQUtil(deska, 0) == false){ document.write('Řešení neexistuje') return false } printSolution(board) return true } // Kód ovladače solveNQ() // Tento kód přispěl shinjanpatra>

Výstup

. . Q . Q . . . . . . Q . Q . . 

Časová náročnost: NA!)
Pomocný prostor: NA ² )

Další optimalizace ve funkci is_safe():

Cílem není kontrolovat každý prvek v pravé a levé diagonále, místo toho použít vlastnost diagonály:

• Součet i a j je konstantní a jedinečný pro každou pravou úhlopříčku, kde i je řada prvků a j je
  sloupec prvků.
• Rozdíl mezi i a j je konstantní a jedinečné pro každou levou úhlopříčku, kde i a j jsou řádek a sloupec prvku.

Níže je implementace:

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) návrat true; // Zvažte tento sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (int i = 0; i // Zkontrolujte, zda lze dámu umístit na // board[i][col] // Chcete-li zkontrolovat, zda dáma může být umístěna na // board[řádek][sloupec]. Potřebujeme jen zkontrolovat // ld[řádek-sloupec+n-1] a rd[řádek+sloupec], kde // ld a rd jsou pro levou a vpravo // diagonálně, respektive if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umístěte tuto královnu na desku[ i][col] board[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // opakujte umístění zbývajících dam; (solveNQUtil(board, col + 1)) return true // Pokud umístění dámy na board[i][col] // nevede k řešení, pak // odeberte dámu z boardu[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Pokud královnu nelze umístit do žádné; řádek v // tento sloupec col then return false return false } // Tato funkce řeší problém N Queen pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil(). Vrátí false, pokud královny // nelze umístit, jinak vrátí hodnotu true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. bool solveNQ() { int board[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} }; if (solveNQUtil(deska, 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)>

Jáva

// 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) návrat true; // Zvažte tento sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (int i = 0; i // Zkontrolujte, zda lze dámu umístit na // board[i][col] // Chcete-li zkontrolovat, zda dáma může být umístěna na // board[řádek][sloupec]. Potřebujeme jen zkontrolovat // ld[řádek-sloupec+n-1] a rd[řádek+sloupec], kde // ld a rd jsou pro levou a vpravo // diagonálně, respektive if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umístěte tuto královnu na desku[ i][col] board[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // opakujte umístění zbývajících dam; (solveNQUtil(board, col + 1)) return true // Pokud umístění dámy na board[i][col] // nevede k řešení, pak // odeberte dámu z boardu[i][col]; board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Pokud královnu nelze umístit do žádné; řádek v // tento sloupec col then return false return false } // Tato funkce řeší problém N Queen pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil(). Vrátí false, pokud královny // nelze umístit, jinak vrátí hodnotu true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. static boolean solveNQ() { int board[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0} }; if (solveNQUtil(deska, 0) == false) { System.out.printf('Řešení neexistuje'); vrátit false; } printSolution(deska); vrátit true; } // Kód ovladače public static void main(String[] args) { solveNQ(); } } // Tento kód přispěl Prince Singh>

Python3

# Python3 program to solve N Queen Problem using> # backtracking> N> => 4> # ld is an array where its indices indicate row-col+N-1> # (N-1) is for shifting the difference to store negative> # indices> ld> => [> 0> ]> *> 30> # rd is an array where its indices indicate row+col> # and used to check whether a queen can be placed on> # right diagonal or not> rd> => [> 0> ]> *> 30> # Column array where its indices indicates column and> # used to check whether a queen can be placed in that> # row or not> cl> => [> 0> ]> *> 30> # A utility function to print solution> def> printSolution(board):> > for> i> in> range> (N):> > for> j> in> range> (N):> > print> (board[i][j], end> => )> > print> ()> # A recursive utility function to solve N> # Queen problem> def> solveNQUtil(board, col):> > # Base case: If all queens are placed> > # then return True> > if> (col>> => N):> > return> True> > # Consider this column and try placing> > # this queen in all rows one by one> > for> i> in> range> (N):> > # Check if the queen can be placed on board[i][col]> > # To check if a queen can be placed on> > # board[row][col] We just need to check> > # ld[row-col+n-1] and rd[row+coln]> > # where ld and rd are for left and> > # right diagonal respectively> > if> ((ld[i> -> col> +> N> -> 1> ] !> => 1> and> > rd[i> +> col] !> => 1> )> and> cl[i] !> => 1> ):> > # Place this queen in board[i][col]> > board[i][col]> => 1> > ld[i> -> col> +> N> -> 1> ]> => rd[i> +> col]> => cl[i]> => 1> > # Recur to place rest of the queens> > if> (solveNQUtil(board, col> +> 1> )):> > return> True> > # If placing queen in board[i][col]> > # doesn't lead to a solution,> > # then remove queen from board[i][col]> > board[i][col]> => 0> # BACKTRACK> > ld[i> -> col> +> N> -> 1> ]> => rd[i> +> col]> => cl[i]> => 0> > # If the queen cannot be placed in> > # any row in this column col then return False> > return> False> # This function solves the N Queen problem using> # Backtracking. It mainly uses solveNQUtil() to> # solve the problem. It returns False if queens> # cannot be placed, otherwise, return True and> # prints placement of queens in the form of 1s.> # Please note that there may be more than one> # solutions, this function prints one of the> # feasible solutions.> def> solveNQ():> > board> => [[> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ],> > [> 0> ,> 0> ,> 0> ,> 0> ]]> > if> (solveNQUtil(board,> 0> )> => => False> ):> > printf(> 'Solution does not exist'> )> > return> False> > printSolution(board)> > return> True> # Driver Code> if> __name__> => => '__main__'> :> > solveNQ()> # This code is contributed by SHUBHAMSINGH10>

C#

// C# program to solve N Queen Problem using backtracking> using> System;> class> GFG {> > static> int> N = 4;> > // ld is an array where its indices indicate row-col+N-1> > // (N-1) is for shifting the difference to store> > // negative indices> > static> int> [] ld => new> int> [30];> > // rd is an array where its indices indicate row+col> > // and used to check whether a queen can be placed on> > // right diagonal or not> > static> int> [] rd => new> int> [30];> > // Column array where its indices indicates column and> > // used to check whether a queen can be placed in that> > // row or not> > static> int> [] cl => new> int> [30];> > // A utility function to print solution> > static> void> printSolution(> int> [, ] board)> > {> > for> (> int> i = 0; i for (int j = 0; j Console.Write(' {0} ', board[i, j]); Console.Write(' '); } } // A recursive utility function to solve N // Queen problem static bool solveNQUtil(int[, ] board, int col) { // Base case: If all queens are placed // then return true if (col>= N) návrat true; // Zvažte tento sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (int i = 0; i // Zkontrolujte, zda lze dámu umístit na // board[i,col] // Chcete-li zkontrolovat, zda a dáma může být umístěna na // board[row,col]. Potřebujeme jen zkontrolovat // ld[row-coll+n-1] a rd[row+col], kde // ld a rd jsou pro levou a pravou / / diagonálně if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umístěte tuto královnu na desku[i, col] board[i, col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // Opakujte umístění zbývajících královen if (solveNQUtil(board , col + 1)) return true // Pokud umístění dámy na board[i,col] // nevede k řešení, pak // odebere dámu z boardu[i,col] board[i, col]; = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // Pokud královnu nelze umístit do žádného řádku v // tomto sloupci; then return false return false } // Tato funkce řeší problém N Queen pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil(). Vrátí false, pokud královny // nelze umístit, jinak vrátí true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. static bool solveNQ() { int[, ] deska = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0} }; if (solveNQUtil(board, 0) == false) { Console.Write('Řešení neexistuje'); vrátit false; } printSolution(deska); vrátit true; } // Kód ovladače public static void Main(String[] args) { solveNQ(); } } // Tento kód přispěl Rajput-Ji>

Javascript

> > // JavaScript code to implement the approach> let N = 4;> > // ld is an array where its indices indicate row-col+N-1> // (N-1) is for shifting the difference to store negative> // indices> let ld => new> Array(30);> > // rd is an array where its indices indicate row+col> // and used to check whether a queen can be placed on> // right diagonal or not> let rd => new> Array(30);> > // Column array where its indices indicates column and> // used to check whether a queen can be placed in that> // row or not> let cl => new> Array(30);> > // A utility function to print solution> function> printSolution( board)> {> > for> (let i = 0; i { for (let j = 0; j document.write(board[i][j] + ' '); document.write(' '); } } // A recursive utility function to solve N // Queen problem function solveNQUtil(board, col) { // Base case: If all queens are placed // then return true if (col>= N) návrat true; // Zvažte tento sloupec a zkuste umístit // tuto dámu do všech řad jednu po druhé pro (nechť i = 0; i { // Zkontrolujte, zda lze dámu umístit na // board[i][col] // Chcete-li zkontrolovat pokud lze umístit dámu na // board[řádek][sloupec]. Potřebujeme jen zkontrolovat // ld[řádek-sloupec+n-1] a rd[řádek+sloupec], kde // ld a rd jsou vlevo a vpravo // diagonálně if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Umístěte tuto královnu na desku [i][col] board[i][col] = 1 ld[i - col + N - 1] = rd[i + col] = cl[i] = 1 // opakujte umístění zbývajících dam; if (solveNQUtil(board, col + 1)) return true // Pokud umístění dámy na board[i][col] // nevede k řešení, pak // odeberte dámu z boardu[i][col]; ] board[i][col] = 0 // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } // Pokud nelze umístit dámu; libovolný řádek v // tomto sloupci col then return false return false } // Tato funkce řeší problém N Queen pomocí // Backtracking K // řešení problému používá hlavně solveNQUtil(). Vrátí false, pokud královny // nelze umístit, jinak vrátí hodnotu true a // vypíše umístění královen ve tvaru 1s. // Upozorňujeme, že může existovat více // řešení, tato funkce vypíše jedno z // možných řešení. funkce solveNQ() { let board = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(deska, 0) == false) { document.write('Řešení neexistuje'); vrátit false; } printSolution(deska); vrátit true; } // Kód ovladače solveNQ(); // Tento kód přispěl sanjoy_62.>

Výstup

 . . Q . Q . . . . . . Q . Q . . 

Časová náročnost: NA!)
Pomocný prostor: NA)

Související články:

• Tisk všech řešení v problému N-Queen