3. Учебный пример: задача о восьми ферзях
В шахматах ферзь может бить любую фигуру, стоящую с ним на одной строке, столбце или диагонали. Задача о восьми ферзях ставится следующим образом: надо расставить восемь ферзей на шахматной доске, чтобы ни один ферзь не угрожал другому. Эта задача является хорошо известным примером использования метода проб и ошибок и алгоритмов с возвратом. У нее 92 решения, но принципиально различных решений только 12, остальные решения оказываются симметричными с ними относительно поворотов. Одно из решений показано на рис. 4.1.
Рис. 4.1. Одно из решений задачи о восьми ферзях.
При традиционном программировании для описания позиций фигур использовалась бы какая-нибудь структура данных, и программа решала бы задачу, перебирая значения в этой структуре и проверяя каждую позицию: не является ли она решением?
При объектно-ориентированном подходе нахождение решения надо запрограммировать как динамическую модель, состоящую из набора однотипных агентов – фигур, обладающих вполне определенным поведением и взаимодействующих друг с другом. Когда состояние модели стабилизируется, решение будет найдено.
3.1 Идентификация компонент
В данной задаче выделяются объекты одного класса – ферзи, которые совместно должны прийти к решению задачи. В любом случае никакие два ферзя не могут занимать один столбец, следовательно, все столбцы заняты. Поэтому каждому ферзю можно сразу присвоить определенный столбец и свести задачу к более простой – поиску соответствующих строк.
Относительно взаимодействия ферзей можно сделать важное упрощающее замечание: каждый ферзь должен знать только о своем соседе слева. Т.о., данные о ферзе состоят из трех значений: столбец, который остается неизменным, строка, которую надо подобрать в процессе решения, и сосед слева.
Будем считать приемлемым решением для столбца N такую конфигурацию столбцов с 1 по N, в которой ни один ферзь из этих столбцов не бьет другого. Каждому ферзю будет поручено найти приемлемое решение для себя и своих соседей слева. Решение всей задачи будет получено, когда самый правый ферзь отыщет приемлемое решение.
Класс CQueen: методы
|
Класс CQueen: атрибуты
|
Initialize – инициализировать строку, затем найти первое приемлемое для себя и соседа решение
Advance – перейти к следующей строке и найти приемлемое решение
CanAttack – проверить, может ли заданная позиция быть атакована данным ферзем или его соседями
|
row – номер текущей строки (изменяется в процессе решения)
column – номер столбца (постоянен)
neighbor – сосед слева (постоянен)
|
Рис. 4.2. Две стороны CRC-карточки для класса CQueen.
Учитывая все перечисленные соображения, CRC-карточку для класса CQueen (Ферзь) можно записать так, как показано на рис. 4.2. На лицевой стороне описаны методы класса, на оборотной – атрибуты класса.
3.2 Описание класса CQueen
Ниже приведено описание класса CQueen. Каждый объект этого класса хранит указатель pNeighbor на другого ферзя-соседа слева (у крайнего слева ферзя pNeighbor=0). Метод Initialize реализован в виде конструктора.
class CQueen {
public:
CQueen( int, CQueen* );
CQueen* GetNeighbor() { return pNeighbor; }
bool FindSolution();
bool Advance();
void Print();
private:
const int column; // Номер столбца (от 1 до 8)
int row; // Номер строки (от 1 до 8)
CQueen* pNeighbor; // Указатель на ферзя-соседа слева
bool CanAttack( int r, int c );
};
Переменная-член column (номер столбца) описана как константа. Ее значение задается в конструкторе и больше не изменяется. Т.к. константу нельзя использовать в левой части оператора присваивания, то для инициализации column надо воспользоваться инициализирующей записью в заголовке конструктора. При такой записи в конструкторе после заголовка функции ставится двоеточие и через запятую перечисляются атрибуты класса со своими начальными значениями в круглых скобках.
CQueen::CQueen( int col, CQueen* pNgb ) :
column( col ),
pNeighbor( pNgb ),
row( 1 )
{
}
3.3 Функции-члены класса CQueen
Для поиска решения каждый ферзь, в порядке справа-налево, опрашивает своих соседей, могут ли они его атаковать. Если да, то ферзь продвигается вниз (или возвращается признак "нет решения", если дальнейшее перемещение невозможно). Если соседи сообщают, что они атаковать не могут, то решение найдено. Это решение – "локальное", верное только для текущего ферзя. Общее решение компонуется из локальных решений для всех ферзей. Поиск локального решения выполняет функция-член FindSolution():
bool CQueen::FindSolution()
{
if ( pNeighbor )
if ( pNeighbor->CanAttack( row, column ) )
return Advance();
return true;
}
Проверка потенциального решения выполняется с помощью функции-члена CanAttack(), которая определяет, будет ли заданный ферзь или один из его соседей слева бить заданную клетку. В реализации используется тот факт, что при движении по диагонали смещение по строкам равно смещению по столбцам.
bool CQueen::CanAttack( int r, int c )
{
// Проверка на ту же строку
if ( row == r )
return true;
// Проверка диагонали
int deltaCol = c - column;
if ( ( row + deltaCol == r ) || ( row - deltaCol == r ) )
return true;
// Проверка, могут ли бить клетку (r, c) соседи
if ( pNeighbor )
return pNeighbor->CanAttack( r, c );
return false;
}
Перемещение ферзя на следующую позицию выполняет функция-член Advance(). В ней можно выделить две части. Если ферзь не достиг последней строки, то эта функция просто увеличивает номер строки и выполняет поиск решения. Если ферзь достиг последней строки, то он пытается попросить соседа слева сместиться на одну строку и затем снова найти решение, начиная с 1-й строки.
bool CQueen::Advance()
{
// Пробуем переместиться на следующую строку
if ( row < 8 )
{
row++;
return FindSolution();
}
// Если ферзь стоит на последней строке, то надо
// попытаться сдвинуть соседа к следующему решению
if ( pNeighbor )
if ( pNeighbor->Advance() )
{
// Начинаем снова с 1-й строки
row = 1;
return FindSolution();
}
return false;
}
После того, как решение найдено, его надо напечатать. Это делается путем прохода по связному списку ферзей в функции Print():
void CQueen::Print()
{
if ( pNeighbor )
pNeighbor->Print();
cout << "Строка: " << row << "; Cтолбец: " << column << "\n";
}
3.4 Главная программа
Т.к. инициализация выполняется в конструкторе, то основная программа может просто создать восемь объектов-ферзей, по одному в каждом столбце, и потом напечатать решение. В показанной далее функции main() переменная pLastQueen указывает на последнего созданного ферзя (крайнего справа). За счет того, что внутри CQueen есть указатель на соседа, ферзи образуют связный список. Явное обращение к этому списку производится при удалении динамически созданных объектов в конце функции main().
void main()
{
CQueen* pLastQueen = NULL;
for ( int i = 1; i <= 8; i++ )
{
// Создать и инициализировать нового ферзя в i-м столбце
pLastQueen = new CQueen( i, pLastQueen );
if ( !pLastQueen->FindSolution() )
cout << "Нет решения.\n";
}
// Печать решения
pLastQueen->Print();
// Удаление объектов-ферзей
while ( pLastQueen )
{
CQueen* pPrevQueen = pLastQueen->GetNeighbor();
delete pLastQueen;
pLastQueen = pPrevQueen;
}
}
|
