私たちは話し合いました 騎士のツアー そして 迷路の中のネズミ バックトラッキング問題の例として、前述の問題を取り上げます。バックトラッキングを使用して解決できる別の問題例として、N クイーンについて説明します。
N-Queen問題とは何ですか?
の N クイーンは配置の問題 N チェスの女王 N×N 2人のクイーンが互いに攻撃しないようにチェス盤を調整します。
たとえば、次は 4 クイーン問題の解決策です。
期待される出力は、「 Q はクイーンが配置されるブロックを表し、空のスペースは で表されます。 「。」 。たとえば、次は上記の 4-Queen ソリューションの出力行列です。
推奨: で解決してください 練習する 解決策に進む前に、まず。。 Q . 。
。 。 。 Q
Q . 。 。
。 。 Q .
Nクイーンの使用上の問題 後戻り :
このアイデアは、左端の列から始めて、異なる列に 1 つずつクイーンを配置することです。クイーンを列に配置するとき、すでに配置されているクイーンとの衝突がないかチェックします。現在の列で、干渉がない行が見つかった場合、その行と列を解決策の一部としてマークします。衝突によりそのような行が見つからない場合は、バックトラックして戻ります。 間違い 。
以下は、上記のアプローチの再帰ツリーです。
N クイーン問題の再帰ツリー
このアイデアを実装するには、以下の手順に従ってください。
- 一番左の列から開始
- すべてのクイーンが配置されている場合は 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]) は false を返します。 // 左側の下対角をチェック for (i = row, j =col; j>= 0 && i if (board[i][j]) return false; return true; } // N を解くための再帰ユーティリティ関数// クイーンの問題 boolsolveNQUtil(int board[N][N], int col) { // 基本ケース: すべてのクイーンが配置されている場合 // true を返す if (col>= N) return true; // この列を考慮します。 // このクイーンをすべての行に 1 つずつ配置してみます 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]からクイーンを削除します。 // この列のどの行にもクイーンを配置できない場合は、 // return false return false; } // この関数は、 // バックトラッキングを使用して N クイーン問題を解決します。 // 問題を解決するには、主にsolveNQUtil() を使用します。 。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 boolsolveNQ() { 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) { 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
2対1マルチプレクサ
// 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]) は false を返します。 // 左側の下対角をチェック for (i = row, j =col; j>= 0 && i if (board[i][j]) return false; return true; } // N を解くための再帰ユーティリティ関数// クイーンの問題 boolsolveNQUtil(int board[N][N], intcol) { // 基本ケース: すべてのクイーンが配置されている場合 // true を返す if (col>= N) return true; // この列を検討します。 // このクイーンをすべての行に 1 つずつ配置してみます 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]からクイーンを削除します。 // この列のどの行にもクイーンを配置できない場合は、 // return false return false; } // この関数は、 // バックトラッキングを使用して N クイーン問題を解決します。 // 問題を解決するには、主にsolveNQUtil() を使用します。 。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 boolsolveNQ() { 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('ソリューションが存在しません'); false を返します。 printSolution(ボード); true を返します。 } // 上記をテストするドライバープログラム function int main() {solveNQ(); 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) は false を返します。 // 左側の下対角をチェック for (i = row, j =col; j>= 0 && i if (board[i][j] == 1) return false; return true; } // 再帰ユーティリティ関数N を解決する // クイーンの問題 booleansolveNQUtil(int board[][], int col) { // 基本ケース: すべてのクイーンが配置されている場合 // true を返す if (col>= N) return true; // これを考慮します。 // このクイーンをすべての行に 1 つずつ配置してみます 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]からクイーンを削除します。 BACKTRACK } } // この列のどの行にもクイーンを配置できない場合は、 // return false return false; // この関数は、 // バックトラッキングを使用して N クイーン問題を解決します。 // 問題を解く。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 booleansolveNQ() { 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('ソリューションが存在しません'); false を返します。 printSolution(ボード); true を返します。 } // 上記をテストするドライバー プログラム function public static void main(String args[]) { NQueen問題 Queen = new NQueen問題(); Queen.solveNQ(); } } // このコードは 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) は false を返します。 // 左側の下対角をチェック for (i = row, j =col; j>= 0 && i if (board[i, j] == 1) return false; return true; } // 再帰ユーティリティ関数solve N // クイーンの問題 boolsolveNQUtil(int [,]board, intcol) { // 基本ケース: すべてのクイーンが配置されている場合 // true を返す if (col>= N) return true; // この列を考慮します。 // このクイーンをすべての行に 1 つずつ配置してみます 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]から削除します。 // この列のどの行にも queen を配置することはできません。col の場合、 return false return false; } // この関数は、 // バックトラッキングを使用して N Queen 問題を解決します。 // 問題を解決するには、 // 主にsolveNQUtil () を使用します。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 boolsolveNQ() { 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('ソリューションが存在しません'); false を返します。 printSolution(ボード); true を返します。 } // ドライバーコード public static void Main(String []args) { GFG Queen = new GFG(); Queen.solveNQ(); } } // このコードは 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 // (i = row, j =col; j>= 0 && i if (board[i]) について左側の下対角をチェックします[j]) return false return true } functionsolveNQUtil(board,col){ // 基本ケース: すべてのクイーンが配置されている場合 // true を返す if(col>= N) return true // この列を考慮して配置してみます / / このクイーンをすべての行に 1 つずつ配置します for(let i=0;i if(isSafe(board, i,col)==true){ // このクイーンをボード[i][col]ボード[i][に配置しますCol] = 1 // 再帰的に残りのクイーンを配置します。 if(solveNQUtil(board,col + 1) == true) return true // クイーンをboard[i][col // に配置しても結果が得られない場合解決策、その後 // ボードからのクイーンボード[i][col] ボード[i][col] = 0 } } // この列のどの行にもクイーンを配置できない場合は、col then return false return false } / / この関数は、バックトラッキングを使用して N クイーン問題を解決します。 // 問題を解決するために、 // クイーンを配置できない場合は false を返し、 // クイーンを配置できない場合は true を返し、 // クイーンの配置を返します。 1秒。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 functionsolveNQ(){ 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('ソリューションが存在しません') return false } printSolution(board) return true } // ドライバー コードsolveNQ() // このコードは shinjanpatra によって提供されています>> |
>
>出力
. . Q . Q . . . . . . Q . Q . .>
時間計算量: の上！）
補助スペース: の上2)
is_safe() 関数のさらなる最適化:
アイデアは、右と左の対角線のすべての要素をチェックするのではなく、代わりに対角線のプロパティを使用することです。
- 合計 私 そして j は定数であり、右対角線ごとに一意です。 私 は要素の行であり、 j それは
要素の列。- の違い 私 そして j は定数であり、左対角線ごとに一意です。 私 そして j はそれぞれ要素の行と列です。
以下に実装を示します。
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 を返します。 // この列を考慮して、 // このクイーンをすべての行に 1 つずつ配置してみます for (int i = 0; i // クイーンを配置できるかどうかを確認します // board[i][col] // かどうかを確認するにはクイーンは // board[row][col] に配置できます。 // ld[row-col+n-1] と rd[row+coln] をチェックするだけです。 // ld と rd は left と 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; // 残りのクイーンを再配置します。 (solveNQUtil(board,col + 1)) return true; // クイーンをboard[i][col]に配置しても解決にならない場合、 // クイーンをboard[i][col]から削除します。 board[i][col] = 0; // BACKTRACK ld[i -col + N - 1] = rd[i +col] = cl[i] = 0; // クイーンがどの場所にも配置できない場合row in // この列col then return false return false; } // この関数は、 // バックトラッキングを使用して N Queen 問題を解決します。 // 問題を解決するには、主にsolveNQUtil() を使用します。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 boolsolveNQ() { 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) { 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 を返します。 // この列を考慮して、 // このクイーンをすべての行に 1 つずつ配置してみます for (int i = 0; i // クイーンを配置できるかどうかを確認します // board[i][col] // かどうかを確認するにはクイーンは // board[row][col] に配置できます。 // ld[row-col+n-1] と rd[row+coln] をチェックするだけです。 // ld と rd は left と 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; // 残りのクイーンを再配置します。 (solveNQUtil(board,col + 1)) return true; // クイーンをboard[i][col]に配置しても解決にならない場合、 // クイーンをboard[i][col]から削除します。 board[i][col] = 0; // BACKTRACK ld[i -col + N - 1] = rd[i +col] = cl[i] = 0; // クイーンがどの場所にも配置できない場合row in // この列col then return false return false; } // この関数は、 // バックトラッキングを使用して N Queen 問題を解決します。 // 問題を解決するには、主にsolveNQUtil() を使用します。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 static booleansolveNQ() { 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('ソリューションが存在しません'); false を返します。 printSolution(ボード); true を返します。 } // ドライバーコード public static void main(String[] args) {solveNQ(); } } // このコードは Princi 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) true を返します。 // この列を考慮して、 // このクイーンをすべての行に 1 つずつ配置してみます for (int i = 0; i // クイーンを配置できるかどうかを確認します // board[i,col] //クイーンは // 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) { // このクイーンを board[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; // BACKTRACK ld[i -col + N - 1] = rd[i +col] = cl[i] = 0; // この列のどの行にもクイーンを配置できない場合then return false return false; } // この関数は、 // バックトラッキングを使用して N Queen 問題を解決します。 // 問題を解決するには、主にsolveNQUtil() を使用します。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 static boolsolveNQ() { 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('ソリューションが存在しません'); false を返します。 printSolution(ボード); true を返します。 } // ドライバーコード public static void Main(String[] args) {solveNQ(); } } // このコードは 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) true を返します。 // この列を考慮して、 // このクイーンをすべての行に 1 つずつ配置してみます for (let i = 0; i { // クイーンを配置できるかどうかを確認します // board[i][col] // 確認するには// ボード[行][列]にクイーンを配置できるかどうか。 // ld[行-列+n-1] と rd[行+列] を確認するだけです。 // 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; // クイーンをboard[i][col]に配置しても解決にならない場合、 // クイーンをboard[i][col]から削除します。 ] board[i][col] = 0; // BACKTRACK ld[i -col + N - 1] = rd[i +col] = cl[i] = 0; // クイーンを配置できない場合// この列の任意の行 Col then return false return false; } // この関数は、 // バックトラッキングを使用して N Queen 問題を解決します。 // 問題を解決するには、 // 主にsolveNQUtil() を使用します。 // クイーンを配置できない場合は false を返し、それ以外の場合は true を返し、 // クイーンの配置を 1 の形式で出力します。 // 複数の解決策が存在する可能性があることに注意してください。 // この関数は、実行可能な解決策の 1 つを出力します。 functionsolveNQ() { 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('ソリューションが存在しません'); false を返します。 printSolution(ボード); true を返します。 } // ドライバーコードsolveNQ(); // このコードは sanjoy_62 によって提供されました。>> |
>
>出力
. . Q . Q . . . . . . Q . Q . .>
時間計算量: の上！）
補助スペース: の上）
関連記事：
- N-Queen 問題のすべての解を出力する