Решение - раздел Философия, Recursive factorials Чтобы Решить Проблему Восьми Королев, Мы Используем Алгоритм Отслеживания В О...
Чтобы решить проблему Восьми Королев, мы используем алгоритм отслеживания в обратном порядке. Алгоритм включает размещения королев, столбец за столбцом, на шахматную доску. Алгоритм завершается, когда он размещает все восемь королев на доску без атакующих друг друга. Алгоритм отслеживает в обратном порядке, когда он достигает ситуации, куда новая королева не может быть размещена в плату, не атакуя королеву уже на плате. Когда алгоритм достигает этой ситуации, он передвигает фигуру, которую он последний раз добавил на доске к другому расположению. Идея здесь, это передвигая фигуры создать комбинацию, которая позволяет алгоритму добавлять как можно больше фигур. Например, рассмотрите шахматную доску на рисунке 6. Здесь, мы разместили семь королев успешно в первые семь столбцов так, что, никакие две королевы не атакуют друг друга. Мы должны отследить в обратном порядке, однако, так как никакое пространство в столбце для восьмой не существует, куда мы можем разместить восьмую королеву.
Рисунок 6, Seven queens placed, but we must backtrack
Часть отслеживания в обратном порядке алгоритма тогда попыталась бы переместить седьмую королеву в другое пятно в седьмом столбце, чтобы открыть пятно в восьмом столбце для восьмой королевы. Если седьмая королева не может быть перемещена, потому что никакие другие пробелы не существуют в столбце семь, алгоритм должен удалить ту королеву и поддержать и рассмотреть перемещение королевы в столбце шесть. В конечном счете, алгоритм повторяет этот процесс размещения королев, и поддержка вплоть до этого находит комбинацию, которая решает проблему.
queens.cpp - Включает основной и алгоритм отслеживания в обратном порядке
Queenboard.h - Определяет класс, который моделирует шахматную доску только королев
Вышеупомянутая реализация проблем Восьми Королев выводит первое решение, которое это находит и затем завершает. Как осуществление, можно расширить это, чтобы найти и вывести на экран все возможные решения?
queens.cpp
Queenboard.h
#include <iostream>
#include <cstdlib>
#include <stdexcept>
#include "Queenboard.h"
using namespace std;
bool place_queens(Queenboard& qb, int col);
int main(int argc, char* argv[]) {
try {
Queenboard qb;
if (! place_queens(qb, 0)) {
cout << "No solution found.
";
}
return EXIT_SUCCESS;
}
catch (exception& e) {
cerr << e.what() << "
";
}
catch (...) {
cerr << "Unknown exception caught.
";
}
return EXIT_FAILURE;
}
bool place_queens(Queenboard& qb, int col) {
bool inserted = false;
for (int row = 0; row < BOARDSIZE; row++) {
if (! qb.is_space_under_attack(row, col)) {
// insert a queen
qb.occupy_space(row, col);
inserted = true;
if (col == BOARDSIZE - 1) {
// solution found!
cout << qb << "
";
return true;
}
else {
// place a queen in the next column
if (place_queens(qb, col + 1)) {
return true;
}
else {
inserted = false;
}
}
}
}
if (! inserted) {
// backtrack to previous column
qb.clear_column(col - 1);
return false;
}
}
#ifndef _QUEENBOARD_H_
#define _QUEENBOARD_H_
const int BOARDSIZE = 8;
using namespace std;
class Queenboard {
private:
bool board[BOARDSIZE][BOARDSIZE];
public:
Queenboard();
bool is_space_under_attack(int, int) const;
void occupy_space(int, int);
void clear_column(int);
friend ostream& operator<<(ostream& out, const Queenboard& cb);
};
Queenboard::Queenboard() {
// Initialize the board to contain zero queens.
for (int row = 0; row < BOARDSIZE; row++) {
for (int col = 0; col < BOARDSIZE; col++) {
board[row][col] = false;
}
}
}
ostream& operator<<(ostream& out, const Queenboard& cb) {
// output the board
for (int row = 0; row < BOARDSIZE; row++) {
out << "---------------------------------" << endl;
for (int col = 0; col < BOARDSIZE; col++) {
out << "|";
if ( cb.board[row][col]) {
out << " Q ";
}
else {
out << " ";
}
}
out << "|" << endl;
}
out << "---------------------------------" << endl;
return out;
}
void Queenboard::clear_column(int col) {
if (col >= BOARDSIZE || col < 0) {
throw out_of_range("Queenboard::clear_column()");
}
for (int row = 0; row < BOARDSIZE; row++) {
board[row][col] = false;
}
}
void Queenboard::occupy_space(int row, int col) {
if (col >= BOARDSIZE || col < 0 ||
row >= BOARDSIZE || row < 0) {
throw out_of_range("Queenboard::occupy_space()");
}
// places a queen on the board
board[row][col] = true;
}
bool Queenboard::is_space_under_attack(int row, int col) const {
if (col >= BOARDSIZE || col < 0 ||
row >= BOARDSIZE || row < 0) {
throw out_of_range("Queenboard::is_space_under_attack()");
}
// check to the left
int i = col - 1;
while (i >= 0) {
if (board[row][i]) return true;
i--;
}
// check diagonal up and left
int j = row - 1;
int k = col - 1;
while (j >= 0 && k >= 0) {
if (board[j][k]) return true;
j--; k--;
}
// check diagonal down and left
j = row + 1;
k = col - 1;
while (j < BOARDSIZE && k >= 0) {
if (board[j][k]) return true;
j++; k--;
}
return false;
}
#endif
Example contains the output of the factorial program after the addition of the output statements to function factorial factorial begin... The output in Example shows that the program first calls function factorial... Problem Solving with Recursion Divide and...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Решение
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
The Call Stack
The call stack is an area of a program's memory used to manage the currently executing function and all pending function calls. Figure 3 lends some insight into what is meant by a "pend
Removing Recursion
Recursion comes with a price: the run time system has to maintain a complicated call stack, on top of having to perform the usual evaluations contained in the function. Often, we can eliminate recu
Divide and Conquer
Divide and conquer is a problem solving technique that utilizes recursion to solve a problem by "dividing" the problem into smaller and smaller sub-problems. The base case of the r
Backtracking. The Concept
Backtracking is a problem solving technique that involves examining all possibilities in the search for a solution. An example of backtracking can be seen in the process of finding the solution to
The Problem
A classic problem that we can solve using backtracking is the Eight Queens problem. This difficult problem deals with placing eight queens on a chessboard such that no two queens are attacking each
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 q
The Call Stack
Call Stack это область памяти программы, используемая, чтобы управлять выполняющейся функцией и всеми последующими вызовами находящиеся в ожидании. Рисунок 3 отражает то понимание, которое принято
Замена рекурсии
Рекурсия имеет собственное решение: т.е. система времени выполнения должна поддержать сложный стек вызовов, сверх необходимости выполнять обычные оценки в функции. Часто бывает выгодно заменить рек
Отслеживание в обратном порядке. Понятие
Отслеживание в обратном порядке является проблемой, решая метод, который включает исследование всех возможностей в поиске решения. Пример отслеживания в обратном порядке может быть замечен в процес
Проблема
Классической проблемой, решения задачи методом «отслеживание в обратном порядке», является проблема Восьми Королев. Эта трудная проблема соглашения с размещением восьми королев на шахматной доске т
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов