우리는 논의했습니다 기사의 투어 그리고 미로 속의 쥐 이전에 역추적 문제의 예로 문제를 설명했습니다. 역추적을 사용하여 해결할 수 있는 또 다른 문제의 예로 N Queen에 대해 논의해 보겠습니다.

N-퀸 문제란 무엇인가?

그만큼 N 퀸은 배치가 문제야 N 체스 퀸즈 N×N 두 명의 여왕이 서로 공격하지 않도록 체스판을 만듭니다.

예를 들어, 다음은 4 Queen 문제에 대한 해결책입니다.

예상되는 출력은 ' 큐 퀸이 배치되는 블록에 대한 것이며 빈 공간은 다음과 같이 표시됩니다. '.' . 예를 들어 다음은 위의 4-Queen 솔루션에 대한 출력 행렬입니다.

. 질문. .
. . . 큐
질문. . .
. . 질문.

권장 사항: 해결해 보세요. 관행 먼저, 솔루션으로 넘어가기 전에.

N Queen 사용 중 문제 역추적 :

아이디어는 퀸을 가장 왼쪽 열부터 시작하여 다른 열에 하나씩 배치하는 것입니다. 열에 퀸을 배치할 때 이미 배치된 퀸과 충돌하는지 확인합니다. 현재 열에서 충돌이 없는 행을 찾으면 이 행과 열을 솔루션의 일부로 표시합니다. 충돌로 인해 그러한 행을 찾지 못하면 역추적하여 돌아옵니다. 거짓 .

다음은 위 접근 방식의 재귀 트리입니다.

N Queen 문제에 대한 재귀 트리

아이디어를 구현하려면 아래에 언급된 단계를 따르세요.

• 가장 왼쪽 열에서 시작
• 모든 퀸이 배치되면 true를 반환합니다.
• 현재 열의 모든 행을 시도해 보세요. 모든 행에 대해 다음을 수행합니다.
  • 여왕이 이 열에 안전하게 배치될 수 있다면
    • 그럼 이것을 표시해 보세요 [행, 열] 솔루션의 일부로 여기에 퀸을 배치하면 솔루션이 발생하는지 재귀적으로 확인합니다.
    • 퀸을 넣으면 [행, 열] 해결책을 찾은 후 돌아옴 진실 .
    • 퀸을 배치해도 문제가 해결되지 않으면 이 항목의 표시를 해제하세요. [행, 열] 그런 다음 역추적하여 다른 행을 시도해 보세요.
  • 모든 행을 시도했지만 유효한 솔루션을 찾을 수 없는 경우 반환 거짓 역추적을 트리거합니다.

이 역추적 접근 방식을 더 잘 시각화하려면 다음을 참조하세요. 4 여왕 문제 .

메모: 퀸을 행으로 배치하여 이 문제를 해결할 수도 있습니다.

다음은 위의 접근 방식을 구현한 것입니다.

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; // 왼쪽의 아래쪽 대각선을 확인합니다 for (i = row, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // N을 해결하기 위한 재귀 유틸리티 함수 // Queen 문제 boolsolveNQUtil(int board[N][N], int col) { // 기본 사례: 모든 퀸이 배치된 경우 // true를 반환합니다. if (col>= N) return true // 이 열을 고려합니다. // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (int i = 0; i // 퀸을 // Board[i][col] if (isSafe(board, i, col)에 배치할 수 있는지 확인하세요. ) { // 이 퀸을 board[i][col]에 배치합니다. board[i][col] = 1; // 나머지 퀸을 배치하기 위해 반복됩니다. if (solveNQUtil(board, col + 1)) return true; 보드[i][col]에 퀸을 배치해도 문제가 해결되지 않으면 // 보드[i][col]에서 퀸을 제거하세요. board[i][col] = 0 // BACKTRACK } } // 이 열의 어떤 행에도 // Queen을 배치할 수 없으면 return false return false } // 이 함수는 // 역추적을 사용하여 N Queen 문제를 해결합니다. // 문제를 해결하기 위해 // . // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. boolsolvNQ() { int 보드[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 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; // 왼쪽의 아래쪽 대각선을 확인합니다 for (i = row, j = col; j>= 0 && i if (board[i][j]) return false; return true; } // N을 해결하기 위한 재귀 유틸리티 함수 // Queen 문제 boolsolveNQUtil(int board[N][N], int col) { // 기본 사례: 모든 퀸이 배치된 경우 // true를 반환합니다. if (col>= N) return true // 이 열을 고려합니다. // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (int i = 0; i // 퀸을 // Board[i][col] if (isSafe(board, i, col)에 배치할 수 있는지 확인하세요. ) { // 이 퀸을 board[i][col]에 배치합니다. board[i][col] = 1; // 나머지 퀸을 배치하기 위해 반복됩니다. if (solveNQUtil(board, col + 1)) return true; 보드[i][col]에 퀸을 배치해도 문제가 해결되지 않으면 // 보드[i][col]에서 퀸을 제거하세요. board[i][col] = 0 // BACKTRACK } } // 이 열의 어떤 행에도 // Queen을 배치할 수 없으면 return false return false } // 이 함수는 // 역추적을 사용하여 N Queen 문제를 해결합니다. // 문제를 해결하기 위해 // . // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. boolsolvNQ() { int 보드[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { printf('솔루션이 존재하지 않습니다'); 거짓을 반환; } printSolution(보드); 사실을 반환; } // 위 테스트를 위한 드라이버 프로그램 function int main() {solvNQ(); 0을 반환합니다. } // 이 코드는 Aditya Kumar(adityakumar129)가 제공한 것입니다.>

자바

// 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; // 왼쪽 아래 대각선을 확인합니다 for (i = row, j = col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // 재귀 유틸리티 함수 N을 해결하려면 // Queen 문제 booleansolveNQUtil(int board[][], int col) { // 기본 사례: 모든 Queen이 배치된 경우 // true를 반환합니다. if (col>= N) return true // 이것을 고려합니다. // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (int i = 0; i // 퀸을 배치할 수 있는지 // Board[i][col] if (isSafe(board, i, col) )) { // 이 퀸을 board[i][col]에 배치합니다. board[i][col] = 1; // 나머지 퀸을 배치하기 위해 반복됩니다. if (solveNQUtil(board, col + 1) == true) return true; // 보드[i][col]에 퀸을 배치해도 // 해결되지 않으면 // 보드에서 퀸을 제거합니다[i][col] board[i][col] = 0; BACKTRACK } } // 이 열의 어떤 행에도 // 퀸을 배치할 수 없으면 false를 반환합니다. return false } // 이 함수는 // 역추적을 사용하여 N Queen 문제를 해결합니다. // 문제를 풀다. // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. booleansolvNQ() { int 보드[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { System.out.print('솔루션이 존재하지 않습니다'); 거짓을 반환; } printSolution(보드); 사실을 반환; } // 위 함수를 테스트하기 위한 드라이버 프로그램 public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } } // 이 코드는 Abhishek Shankhadhar가 제공한 것입니다.>

파이썬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>> => 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# 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; // 왼쪽의 아래쪽 대각선을 확인합니다 for (i = row, j = col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // 재귀 유틸리티 함수 solv N // Queen 문제 boolsolveNQUtil(int [,]board, int col) { // 기본 사례: 모든 Queen이 배치된 경우 // true를 반환합니다. if (col>= N) return true // 이 열을 고려하고 // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (int i = 0; i { // 퀸을 // Board[i,col] if (isSafe(board, i, col))에 배치할 수 있는지 확인하세요. { // 이 퀸을 board[i,col]에 배치합니다. board[i, col] = 1; // 나머지 퀸을 배치하기 위해 반복됩니다. if (solveNQUtil(board, col + 1) == true) return true; 보드[i,col]에 퀸을 배치해도 문제가 해결되지 않으면 // 보드[i,col]에서 퀸을 제거하세요. board[i, col] = 0 // BACKTRACK } } // queen은 // 이 열의 어떤 행에도 배치될 수 없으며, false를 반환합니다. return false } // 이 함수는 // 역추적을 사용하여 N Queen 문제를 해결합니다. // 문제를 해결하기 위해 // // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. boolsolvNQ() { 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('솔루션이 존재하지 않습니다'); 거짓을 반환; } printSolution(보드); 사실을 반환; } // 드라이버 코드 public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // 이 코드는 Princi Singh이 제공한 것입니다.>

자바스크립트

> // 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 // (i = row, j = col; j>= 0 && i if (board[i])에 대해 왼쪽에서 아래쪽 대각선을 확인합니다. [j]) return false return true } functionsolvNQUtil(board, col){ // 기본 사례: 모든 퀸이 배치된 경우 // true를 반환합니다. if(col>= N) return true // 이 열을 고려하고 배치를 시도합니다. / / 이 퀸을 모든 행에 하나씩 for(let i=0;i if(isSafe(board, i, col)==true){ // 이 퀸을 보드에 배치[i][col] 보드[i][ col] = 1 // 나머지 퀸을 배치하기 위해 반복 if(solveNQUtil(board, col + 1) == true) return true // 보드에 퀸을 배치하는 경우[i][col // 결과가 발생하지 않음 해결 방법, // 보드[i][col]의 퀸 보드[i][col] = 0 } } // 퀸을 // 이 열의 어떤 행에도 배치할 수 없는 경우 // 이 열 col에서는 false를 반환합니다. return false } / / 이 함수는 // Backtracking을 사용하여 N Queen 문제를 해결합니다. // 문제를 해결하기 위해 // Queens를 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 1초. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하세요. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. functionsolvNQ(){ 보드 = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] if (solveNQUtil(board, 0) == false){ document.write('솔루션이 존재하지 않습니다') return false } printSolution(board) return true } // 드라이버 코드solveNQ() // 이 코드는 shinjanpatra가 제공합니다.>

산출

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

시간 복잡도: 에!)
보조 공간: 에 ² )

is_safe() 함수의 추가 최적화:

아이디어는 오른쪽과 왼쪽 대각선의 모든 요소를 ​​확인하는 것이 아니라 대신 대각선의 속성을 사용하는 것입니다.

• 의 합 나 그리고 제이 각 오른쪽 대각선에 대해 일정하고 고유하며, 여기서 나 요소의 행이고 제이 은
  요소 열입니다.
• 차이점은 다음과 같습니다. 나 그리고 제이 각 왼쪽 대각선에 대해 일정하고 고유하며, 여기서 나 그리고 제이 각각 요소의 행과 열입니다.

구현은 다음과 같습니다.

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) true를 반환합니다. // 이 열을 고려하고 // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (int i = 0; i // 퀸을 배치할 수 있는지 확인합니다 // Board[i][col] // 확인하려면 // 보드[row][col]에 퀸을 배치할 수 있습니다. // ld[row-col+n-1] 및 rd[row+coln]을 확인하면 됩니다. 여기서 // ld와 rd는 왼쪽과 rd에 해당합니다. right // 각각 대각선 if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // 이 퀸을 보드에 놓습니다[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; (solveNQUtil(board, col + 1)) return true; // 보드[i][col]에 퀸을 배치해도 // 해결되지 않으면 // 보드[i][col]에서 퀸을 제거합니다. board[i][col] = 0; // 역추적 ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // 퀸을 어디에도 배치할 수 없는 경우 row in // 이 열 col then return false return false } // 이 함수는 // 역추적을 사용하여 N Queen 문제를 해결합니다. // 문제를 해결하는 데는solvNQUtil()이 사용됩니다. // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. boolsolvNQ() { int 보드[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)>

자바

// 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) true를 반환합니다. // 이 열을 고려하고 // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (int i = 0; i // 퀸을 배치할 수 있는지 확인합니다 // Board[i][col] // 확인하려면 // 보드[row][col]에 퀸을 배치할 수 있습니다. // ld[row-col+n-1] 및 rd[row+coln]을 확인하면 됩니다. 여기서 // ld와 rd는 왼쪽과 rd에 해당합니다. right // 각각 대각선 if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // 이 퀸을 보드에 놓습니다[ i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; (solveNQUtil(board, col + 1)) return true; // 보드[i][col]에 퀸을 배치해도 // 해결되지 않으면 // 보드[i][col]에서 퀸을 제거합니다. board[i][col] = 0; // 역추적 ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // 퀸을 어디에도 배치할 수 없는 경우 row in // 이 열 col then return false return false } // 이 함수는 // 역추적을 사용하여 N Queen 문제를 해결합니다. // 문제를 해결하는 데는solvNQUtil()이 사용됩니다. // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. static booleansolvNQ() { int 보드[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0 , 0 } }; if (solveNQUtil(board, 0) == false) { System.out.printf('솔루션이 존재하지 않습니다'); 거짓을 반환; } printSolution(보드); 사실을 반환; } // 드라이버 코드 public static void main(String[] args) {solvNQ(); } } // 이 코드는 Princi Singh이 제공한 것입니다.>

파이썬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>> => 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# 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) true를 반환합니다. // 이 열을 고려하고 // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (int i = 0; i // 퀸을 배치할 수 있는지 확인합니다. // Board[i,col] // queen은 //board[row,col]에 배치될 수 있습니다. // ld[row-col+n-1] 및 rd[row+coln]을 확인하면 됩니다. 여기서 // ld와 rd는 왼쪽과 오른쪽에 대한 것입니다. / 대각선 각각 if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // 이 퀸을 보드에 배치합니다[i, col] board[i, col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // 나머지 퀸을 배치하기 위해 반복 if (solveNQUtil(board , col + 1)) return true; // 보드[i,col]에 퀸을 배치해도 문제가 해결되지 않으면 // 보드[i,col]에서 퀸을 제거합니다. = 0; // 역추적 ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // 이 열의 어떤 행에도 // 배치할 수 없는 경우 col then return false return false } // 이 함수는 역추적을 사용하여 // N Queen 문제를 해결합니다. // 문제를 해결하기 위해solvNQUtil()을 사용합니다. // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. static boolsolvNQ() { int[, ] 보드 = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveNQUtil(board, 0) == false) { Console.Write('솔루션이 존재하지 않습니다'); 거짓을 반환; } printSolution(보드); 사실을 반환; } // 드라이버 코드 public static void Main(String[] args) {solvNQ(); } } // 이 코드는 Rajput-Ji가 제공한 것입니다.>

자바스크립트

> > // 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) true를 반환합니다. // 이 열을 고려하고 // 이 퀸을 모든 행에 하나씩 배치해 보세요. for (let i = 0; i { // 퀸이 // 보드에 배치될 수 있는지 확인하세요.[i][col] // 확인하려면 // 보드[row][col]에 퀸을 배치할 수 있는지 확인하면 됩니다. // ld[row-col+n-1] 및 rd[row+coln]을 확인하면 됩니다. 여기서 // ld와 rd는 왼쪽에 해당합니다. 및 오른쪽 // 대각선 if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // 이 퀸을 보드에 놓습니다. [i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; if (solveNQUtil(board, col + 1)) return true; // 보드[i][col]에 퀸을 배치해도 // 해결책이 나오지 않으면 // 보드[i][col]에서 퀸을 제거합니다. ] board[i][col] = 0; // 역추적 ld[i - col + N - 1] = rd[i + col] = cl[i] = 0 } } // 퀸을 배치할 수 없는 경우 // 이 열의 모든 행은 false를 반환합니다. return false } // 이 함수는 // 역추적을 사용하여 N Queen 문제를 해결합니다. 이 함수는 문제를 해결하기 위해 // 주로solvNQUtil()을 사용합니다. // 퀸을 배치할 수 없으면 false를 반환하고, 그렇지 않으면 true를 반환하고 // 퀸의 배치를 1의 형태로 인쇄합니다. // 하나 이상의 솔루션이 있을 수 있다는 점에 유의하십시오. // 이 함수는 실행 가능한 솔루션 중 하나를 // 인쇄합니다. functionsolvNQ() { 보드 = [[ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ]]; if (solveNQUtil(board, 0) == false) { document.write('솔루션이 존재하지 않습니다'); 거짓을 반환; } printSolution(보드); 사실을 반환; } // 드라이버 코드solvNQ(); // 이 코드는 sanjoy_62가 제공한 것입니다.>

산출

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

시간 복잡도: 에!)
보조 공간: 에)

관련 기사:

• N-Queen 문제의 모든 솔루션 인쇄