Решение
Чтобы решить проблему Восьми Королев, мы используем алгоритм отслеживания в обратном порядке. Алгоритм включает размещения королев, столбец за столбцом, на шахматную доску. Алгоритм завершается, когда он размещает все восемь королев на доску без атакующих друг друга. Алгоритм отслеживает в обратном порядке, когда он достигает ситуации, куда новая королева не может быть размещена в плату, не атакуя королеву уже на плате. Когда алгоритм достигает этой ситуации, он передвигает фигуру, которую он последний раз добавил на доске к другому расположению. Идея здесь, это передвигая фигуры создать комбинацию, которая позволяет алгоритму добавлять как можно больше фигур. Например, рассмотрите шахматную доску на рисунке 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
|