Озадаченный возвращением в восьмерку королевы
Мне трудно понять рекурсию и возврат, хотя я выполнил несколько простых упражнений (например, Фибоначчи). Итак, позвольте мне представить мой «мозговой поток» здесь:
-
Я прочитал учебник и знаю, что вы можете использовать обратный трекинг, чтобы удалить предыдущую королеву, если ее текущая позиция исключает возможность размещения следующей ферзя в следующем столбце. Так что это кажется легким, и все, что мне нужно сделать, это удалить его и позволить программе выбрать следующее возможное место.
-
Через некоторое время я обнаружил, что программа остановилась на 6-й королеве, поэтому я понял, что если я просто удаляю 5-ую королеву, программа просто вернет ее на свою текущую позицию (т. Е. При первых четырех королевах 5-я королева всегда попадает в одну и ту же ферзь). место, что не удивительно). Поэтому я подумал, что мне нужно отследить положение последней королевы.
-
Это когда я озадачился. Если бы я должен был отследить положение последней королевы (чтобы при возврате программа НЕ позволяла поместить королеву в одно и то же место), возникли бы две потенциальные трудности:
а) Скажите, что я удалил 5-ю королеву, и мне нужно написать код, определяющий его следующую возможную позицию. Это может быть решено путем игнорирования его текущего положения (перед удалением) и продолжения поиска возможных мест в следующих строках.
б) Должен ли я отслеживать все предыдущие королевы? Вроде бы так. Допустим, что на самом деле мне нужно убрать не одну королеву, а две королевы (или даже больше), мне обязательно нужно отследить все их текущие позиции. Но это намного сложнее, чем кажется.
- Поэтому я начал искать ответы в учебнике. К сожалению, у него нет кода возврата, а есть только код рекурсии. Тогда я нашел код здесь:
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-ю Королеву в следующем ряду, и если это произойдет, мы дополнительно проверим, можно ли разместить шестую Королеву и т. д.
Да, это похоже на работу, ну да.
Решение
Рассмотрим вашу начальную доску:
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
Когда вы впервые вызываете свою функцию, алгоритм помещает ферзь в столбец 0 и строку 0, потому что вы вызываете его с помощью col = 0 и потому что for (int i = 0; i < N; i++) начинается с 0. Ваша доска становится
+---+---+---+---+---+---+---+---+
| Q | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
Затем вы вызываете функцию рекурсивно, с col = 1так что вы попытаетесь поместить королеву в col=1 а также line=0, Вы получаете невозможное размещение, потому что королевы могут брать друг друга, поэтому вы продолжаете for (int i = 0; i < N; i++) цикл и в конечном итоге преуспеть в размещении королевы в col=1 а также line=2Вы получаете эту доску:
+---+---+---+---+---+---+---+---+
| Q | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
Теперь вы продолжаете делать это, увеличивая col каждый раз. Со временем вы попадете на эту доску:
+---+---+---+---+---+---+---+---+
| Q | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | Q | | | | |
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | Q | | | |
+---+---+---+---+---+---+---+---+
| | | Q | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | Q | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | Q | |
+---+---+---+---+---+---+---+---+
У вас возникла проблема, потому что эта доска не допускает положение ферзя в столбце 7. Вам придется вернуться назад. Что происходит, так это то, что рекурсивная функция достигает только return false; после того, как все позиции в столбце были предприняты и позиция не была найдена Когда функция возвращает false, предыдущий вызов функции возобновит выполнение на линии
if ( solveNQUtil(board, col + 1) == true )
Поскольку вызов вернул true, остальная часть тела цикла for будет выполнена, i будет увеличен, и алгоритм будет продолжать пробовать позиции. Думайте об этом как о гигантском наборе вложенного цикла:
for(int i = 0; i < 8; ++i) {
for(int j = 0; j < 8; ++j) {
//Snip 6 other fors
board[0, i] = 1;
board[1, j] = 1;
//Snip
if(isValid(board)) return board;
//Snip clean up
}
}
Это вы замените рекурсивными вызовами функций. Это показывает, что «возврат» действительно позволяет предыдущему рекурсивному уровню повторяться до следующей попытки. В этом случае это означает пробовать новую позицию, в то время как в других приложениях это будет попытка следующего сгенерированного движения.
Я думаю, что вам нужно понять, что состояние предыдущего рекурсивного вызова не теряется при повторном вызове той же функции. Когда вы достигнете линии
if ( solveNQUtil(board, col + 1) == true )
Состояние текущей функции все еще находится в стеке, и для нового вызова создается новый кадр стека. solveNQUtil, Когда эта функция возвращается, предыдущая может продолжить свое выполнение и, в этом случае, увеличить, в какую строку она пытается поместить королеву.
Надеюсь это поможет. Лучший способ обдумать это — уменьшить проблему до меньшего домена (скажем, с меньшим количеством ферзей) и выполнить выполнение с помощью отладчика.
Другие решения
Прямой ответ на ваш вопрос прост: вы позиционируете и
удалить королеву в цикле. В следующий раз через цикл вы
попробую следующую позицию.
Что подводит меня к следующему пункту: вы говорите, что учебник
не имеет кода возврата, а только код рекурсии.
Код рекурсии является код возврата. Когда повторяется,
Каждый экземпляр функции имеет свой собственный полный набор переменных.
Так что в этом случае, когда solveNQUtil называется, проблема имеет
уже решено для первого col - 1 колонны.
Функция перебирает строки, каждый раз проверяя,
можно разместить королеву, а если да, то разместить ее и повторно.
итерация гарантирует, что будут проверены все возможные места (если
необходимо — ваш код завершается, как только мы находим решение).
Вы должны помнить, что есть два причины перемещения королевы вниз по доске:
- Это не в безопасном положении
- Он находится в безопасном положении, но когда вы попытались установить следующую ферзь, рекурсивный вызов вернулся ложный, имея в виду вы исчерпали все возможности в следующем столбце.
Ваша программа остановилась на Queen 5, потому что она не учитывала второе условие. Нет необходимости в отслеживании позиций, как сказал Джеймс, каждый рекурсивный вызов имеет неявное отслеживание для королевы, которую он должен разместить.
Попытайтесь представить стек вызовов (на самом деле, вы можете изменить свою программу, чтобы генерировать такой же вывод):
Queen 1 is safe on row 1
Queen 2 is safe on row 3
Queen 3 is safe on row 5
Queen 4 is safe on row 2
Queen 5 is safe on row 4
No more rows to try for Queen 6. Backtracking...
Queen 5 is safe on row 8
No more rows to try for Queen 6. Backtracking...
No more rows to try for Queen 5. Backtracking...
Queen 4 is safe on row 7
Queen 5 is safe on row 2
Queen 6 is safe on row 4
Queen 7 is safe on row 6
No more rows to try for Queen 8. Backtracking...
Каждый раз, когда вы возвращаетесь назад, понимаете, что вы возвращаетесь к предыдущему вызову функции, в том же состоянии Вы оставили это. Таким образом, когда вы достигаете Queen 6 и нет никаких возможностей, функция возвращает false, что означает вы завершили solveNQUtil(board, col + 1) вызов для Queen 5. Вы вернулись в for цикл для Queen 5, и следующая вещь, которая произойдет, это то, что i увеличивается, и вы пытаетесь поставить Queen 5 на 5 ряд и так далее …
Я предлагаю вам поиграть с это демо (попробуйте «Управление размещением: опция« Вручную с помощью »»), наш мозг намного лучше понимает вещи визуально. Код слишком абстрактный.