На головну

# 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 can not 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 can not 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 = 1204! = 4 * 3 * 2 * 1 = 243! = 3 * 2 * 1 = 62! = 2 * 1 = 21! = 10! = 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 #include #include using namespace std; int factorial (int n) {if (n == 0) {// base casereturn 1; } Else {// recursive callint 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 callcerr << "factorial (" << n << ") returns" << ret << endl; return ret; }} Listing 2A verbose function factorial

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

 factorial (5) beginfactorial (4) beginfactorial (3) beginfactorial (2) beginfactorial (1) beginfactorial (0) beginfactorial (0) returns 1factorial (1) returns 1factorial (2) returns 2factorial (3) returns 6factorial (4) returns 24factorial (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.

The Problem | The Call Stack
© um.co.ua - учбові матеріали та реферати