簡単な演習 (例: フィボナッチ) を行ったにもかかわらず、再帰とバックトラックを理解するのに苦労しています。ここで私の「脳の流れ」を紹介させてください。
私は教科書を読み、現在の位置が次の列に次のクイーンを配置する可能性を排除する場合、バックトラックを使用して前のクイーンを削除できることを知っています. したがって、これは簡単に思えます。私がする必要があるのは、それを削除して、プログラムに次の可能な場所を決定させることだけです。
しばらくすると、プログラムが 6 番目のクィーンで止まっていることがわかったので、単に 5 番目のクィーンを削除すると、プログラムは単純に現在の位置に戻すことがわかりました (つまり、最初の 4 つのクィーンが与えられた場合、5 番目のクィーンは常に同じクィーンに分類されます)。驚くべきことではありません）。そこで、最後の女王の位置を追跡する必要があると考えました。
これは私が困惑したときです。最後のクイーンの位置を追跡する場合 (バックトラックしたときにプログラムがクイーンを同じ場所に配置できないようにするため)、2 つの潜在的な問題があります。
a) 5 番目のクイーンを削除し、次の可能な位置を決定するコードを作成する必要があるとします。これは、現在の位置 (削除される前) を無視することで解決でき、次の行で可能な場所を探し続けます。
b) 以前のすべてのクイーンを追跡する必要がありますか? そうらしい。実際には、1 つのクイーンではなく 2 つのクイーン (またはそれ以上) を削除する必要があるとしましょう。それらの現在の位置をすべて追跡する必要があります。しかし、これは見た目よりもはるかに複雑です。
- それで、教科書で答えを探し始めました。残念ながら、バックトラッキング コードはなく、再帰コードしかありません。次に、ここにコードを見つけました：
http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/
これはとてもシンプルでありながら機能するので、私は非常に驚きました! 唯一のバックトラック部分は、最後のクイーンを削除することです! 問題は、次のコードは、4 つのクイーンの位置が与えられたときに、5 番目のクイーンが常に同じ場所に何度も落ちるとは限らないことをどのように確認するのでしょうか? 私が理解していないのは、再帰的にバックトラックする方法だと思います（より多くのクイーンを削除する必要があるとしましょう）。再帰的に進むときは問題ありませんが、再帰的に戻るにはどうすればよいですか?
/* 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)
return true;
/* Consider this column and try placing this queen in all rows
one by one */
for (int i = 0; i < N; i++)
{
/* Check if queen can be placed on board[i][col] */
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 remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}
/* If queen can not be place in any row in this colum col
then return false */
return false;
}
わかった。現在、動作するコードがいくつかありますが、上記のコードに従って自分のコードをほとんど変更したため、非常に不安定です。
bool EightQueen(int& numQueen) {
if (numQueen == 8) {
return true;
}
if (numQueen == 0) {
PlaceQueen(0, 0);
numQueen ++;
EightQueen(numQueen);
}
int row = 0;
for (row = 0; row <= 7; row ++) {
if (CheckThis(row, numQueen)) { //Check if next queen can be put
PlaceQueen(row, numQueen); //Place next queen
numQueen ++;
DisplayQueen();
cout << endl;
if (EightQueen(numQueen)) { //Try next queen
return true;
}
ClearQueen(numQueen - 1);
numQueen --;
}
}
return false;
}
numQueen が 5 であるとすると、for ループで 6 番目のクイーンを配置できるかどうかを確認します。すべての行でこれが不可能であることはわかっているため、関数は false を返します。その後、それが呼び出された場所、つまり numQueen が 4 のときに "縮小" すると仮定します。そのため、ClearQueen(4) が呼び出され、最後のクイーン (5 番目) が削除されます。どうやら for ループが終了していないため、次の行を試してさらに開発できるかどうかを確認します。つまり、5 番目のクイーンを次の行に配置できるかどうかを確認し、配置できる場合は、6 番目のクイーンを配置できるかどうかをさらに確認します。
ええ、うまくいくようです。