The Solution

To solve the Eight Queens problem, we use a backtracking algorithm. The algorithm involves placing queens, column by column, onto the chessboard. The algorithm terminates when it places all eight queens on the board with no two queens attacking each other. The algorithm backtracks when it reaches a situation where a new queen cannot be placed on the board without attacking a queen already on the board. When the algorithm reaches this situation, it moves the piece that it most recently added to the board to another location. The idea here is that moving this piece may create a combination that allows the algorithm to add more pieces. For example, consider the chessboard in Figure 6. Here, we have placed seven queens successfully in the first seven columns such that no two queens are attacking each other. We must backtrack, however, since no legal space in column eight exists where we can place the eighth queen.

Figure 6 Seven queens placed, but we must backtrack

The backtracking portion of the algorithm would then attempt to move the seventh queen to another spot in the seventh column to open a spot in the eighth column for the eighth queen. If the seventh queen cannot be moved because no other legal spaces exist in column seven, the algorithm must remove that queen and back up and consider moving the queen in column six. Eventually, the algorithm repeats this process of placing queens and backing up until it finds a combination that solves the problem.

• queens.cpp - Includes main and the backtracking algorithm
• Queenboard.h - Defines a class that models a chessboard of only queens

The above implementation of the Eight Queens problem outputs the first solution it finds and then terminates. As an exercise, can you extend it to find and display all possible solutions?

 

 

Рекурсивные функции Рекурсивная функция это функция, которая может вызывать саму себя. Использование рекурсивных функций может привести к изящным решениям сложных проблем. C++, как многие другие языки программирования, поддерживает рекурсию. Программист должен использовать рекурсивные функции осторожно, чтобы избежать создание функции, которая вызывает себя вечно. Псевдокод типовой рекурсивной функции имеет следующий вид. if (simplest case) then solve directly else make recursive call to a simpler case Пример 1 типовая рекурсивная функция Создание и использование эффективных рекурсивных функций это разбиение большого на меньшие. В итоге, проблема становится достаточно маленькой, чтобы можно было решить ее, не используя рекурсию. Её вызывают base case. Вычисление факториалов является примером, как решается проблема рекурсией. Факториал числа N есть произведение целых чисел от N до единицы. Например, факториал пять равняется 5 * 4 * 3 * 2 * 1. Как известно, оно равно 120. Факториал от 3 (3 * 2 * 1) равняются значению 6. Восклицательный знак обозначает факториал числа. Таким образом, "пять факториалов" могут быть показаны так 5!. В примере 2 приведены несколько положительных целых чисел и вычисление их факториалов. Факториал нуля является особым случаем и всегда равен 1.   5! = 5 * 4 * 3 * 2 * 1 = 120 4! = 4 * 3 * 2 * 1 = 24 3! = 3 * 2 * 1 = 6 2! = 2 * 1 = 2 1! = 1 0! = 1 Пример 2 Некоторые факториалы Выразим факториалы рекурсивно, то есть, с точки зрения других факториалов. Рассмотрим вычисление факториала для значения 5. Из примера 2, видим 5! = 5 * 4 * 3 * 2 * 1. Но, для 4, мы знаем это 4! = 4 * 3 * 2 * 1. Тогда рекурсивно, 5! = 5 * 4!. В примере 3 приведены рекурсивные определения тех же самых чисел примера 2. Так как мы не можем выразить нулевой факториал рекурсивно, это - base case.   5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! 0! = 1 Пример 3 Рекурсия факториалов Листинг 1 содержит код C++, который рекурсивно вычисляет факториалы.  

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24:	#include <iostream> #include <cstdlib> #include <string>   using namespace std;   int factorial(int n) {   if (n == 0) { // base case return 1; } else { // recursive call int value = factorial(n - 1); return n * value; } }   int main(int argc, char* argv[]) {   cout << factorial(5) << endl; return EXIT_SUCCESS; }
Listing 1Calculating a factorial recursively

Выполнение программы в листинге 1 выводит, разумеется - 120. Мы знаем, что это корректно, но как получен этот результат? Добавим операторы вывода, чтобы увидеть, как этот пример работает. Листинг 2 содержит обновленную функцию factorial, которая выводит строку, указывающую, когда экземпляр функции начинается и когда экземпляр функции заканчивается. Эта измененная версия также выводит возвращаемое значение функции factorial.

 

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:	int factorial(int n) {   cerr << "factorial(" << n << ") begin" << endl;   if (n == 0) { cerr << "factorial(" << n << ") returns 1" << endl; return 1; // base case } else { int ret = n * factorial(n - 1); // recursive call cerr << "factorial(" << n << ") returns " << ret << endl; return ret; } }
Listing 2A verbose function factorial

Пример 4 содержит Output of Listing 2, программы factorial после добавления операторов вывода.

 

factorial(5) begin factorial(4) begin factorial(3) begin factorial(2) begin factorial(1) begin factorial(0) begin factorial(0) returns 1 factorial(1) returns 1 factorial(2) returns 2 factorial(3) returns 6 factorial(4) returns 24 factorial(5) returns 120

Example 4 Output of Listing 2

Вывод в примере 4 показывает, что программа сначала вызывает функцию factorial с параметром 5. Функция main выполняет этот начальный вызов. Во время выполнения factorial (5) вызывает функцию factorial со значением аргумента 4. Экземпляр factorial (4) начинает выполнение и вызывает factorial (3), который последовательно вызывает factorial (2). Так продолжается, пока factorial (0) не возвращает значение 1. После этого factorial (1) возвращает значение 1 в factorial (2), factorial (2) возвращает значение 2 в factorial (3), и так далее до factorial (5) которое возвращает в main значение 120.