Глава     5

Учебный пример: задача о восьми ферзях

Разделы

Содержание

Эта глава представляет собой первый из нескольких примеров (или парадигм, в первоначальном значении этого слова) программ, разработанных с помощью объектно-ориентированных методов. Программы достаточно малы, поэтому мы сможем привести их версии для каждого обсуждаемого в книге языка. Последующие примеры будут представлены только на одном языке.

После описания задачи мы обсудим, чем объектно-ориентированное решение отличается от других. Глава заканчивается программным кодом на различных языках.

5.1. Задача о восьми ферзях

Разделы

В шахматах ферзь может бить любую фигуру, стоящую в одном с ним ряду, столбце или диагонали. Задача о восьми ферзях является классической логической проблемой. Необходимо расставить на шахматной доске 8 ферзей так, чтобы ни один из них не бил другого. Решение приведено на рис. 5.1, но оно не единственное. Задача о восьми ферзях часто используется для иллюстрации решения логических задач и техники вычислений с возвратом (см., например, [Griswold 1983, Budd 1987, Berztiss 1990]).

Чем объектно-ориентированное решение задачи о восьми ферзях отличается от кода на обычном директивном языке программирования? В традиционном решении для описания позиций фигур использовалась бы какая-нибудь структура данных. Программа решала бы задачу, систематически перебирая значения в этих структурах и проверяя каждую позицию: не удовлетворяет ли она условию?

Можно привести забавную и поучительную метафору о разнице между традиционным и объектно-ориентированным решениями. Традиционная программа подобна человеку, находящемуся над доской и передвигающему безжизненные фигуры. В объектно-ориентированном подходе, напротив, мы наделяем фигуры жизнью, чтобы они решили проблему самостоятельно. То есть вместо одного существа, управляющего процессом, мы разделяем ответственность за нахождение решения среди многих взаимодействующих агентов. Это происходит так, как если бы шахматные фигуры были одушевленными существами, взаимодействующими между собой, которым поручено найти решение.

Таким образом, сущность нашего объектно-ориентированного подхода состоит в создании объектов, представляющих ферзей, и наделении их способностями найти решение. С точки зрения программирования как имитации, приведенной в главе 1, мы создаем мир, определяя в нем поведение его объектов. Когда состояние мира стабилизируется, решение будет найдено.


Рис. 5.1. Одно из решений задачи о восьми ферзях

5.1.1. Создание объектов, решающих «самих себя»

Задача о восьми ферзях

Как определить поведение каждого ферзя, чтобы группа ферзей, работающих совместно, могла прийти к решению? Первое наблюдение состоит в том, что в любом случае никакие два ферзя не могут занимать один столбец и, следовательно, все столбцы заняты. Поэтому мы можем сразу присвоить каждому ферзю определенный столбец и свести задачу к более простой — найти соответствующие строки.

Чтобы прийти к решению, ферзи должны взаимодействовать друг с другом. Поняв это, мы можем сделать следующее важное наблюдение, которое очень упростит нашу задачу, а именно: каждый ферзь должен знать только о своем соседе слева. Таким образом, данные о ферзе будут состоять из трех значений: столбец, который остается неизменным; строка, меняющаяся в ходе решения; и сосед слева.

Определим приемлемое решение для столбца N как такую конфигурацию столбцов с 1 по N, в которой ни один ферзь из этих столбцов не бьет другого. Каждому ферзю будет поручено найти приемлемое решение для себя и своих соседей слева. Мы получим решение всей задачи, когда самый правый ферзь отыщет приемлемое решение. Описание класса Queen (Ферзь) на CRC-карточке, включая данные о каждом представителе (напомним, что эта информация содержится на обороте), приведено на рис. 5.2.


Рис. 5.2. Две стороны CRC-карточки для класса Queen

5.2. Использование генераторов

Разделы

Как и в других подобных задачах, решение проблемы восьми ферзей состоит из двух взаимосвязанных шагов: генерация возможных частичных решений и отсеивание решений, не удовлетворяющих дальнейшим тестам. Такой стиль анализа проблем иногда называют «генерация и тестирование» [Hanson 1981], [Bertiss 1990].

Сначала рассмотрим шаг отсеивания как более простой. Для проверки потенциального решения системе достаточно, чтобы ферзь взял координатную пару (строка-столбец) и выдал логическое значение, указывающее, будет ли этот ферзь (или какой-нибудь другой слева) бить это поле (см. приведенный ниже алгоритм на псевдокоде). Процедура canAttack использует тот факт, что при движении по диагонали смещение по строкам равно смещению по столбцам. 

function queen.canAttack(testRow, testColumn) -> boolean

  /* проверка на ту же строку */
  if row = testRow then
    return true

  /* проверка диагонали */
  columnDifference := testColumn — column
  if (row + columnDifference = testRow) or
     (row — columnDifference = testRow)
  then return true

  /* мы не можем бить, а соседи? */
  return neighbor.canAttack(testRow, testColumn)
end

5.2.1. Инициализация

Использование генераторов

Мы разделим задачу на части. Метод initialize устанавливает необходимые начальные условия, в данном случае — просто задает данные. Далее обычно сразу же следует вызов метода findSolution, находящего решение для данного столбца. Поскольку решение часто будет неудовлетворительным для последующих ферзей, сообщение advance (продвинуться) используется для перехода к следующему решению.

Ферзь из столбца N инициализируется присваиванием номера столбца и определением соседнего ферзя (из столбца N–1). На этом уровне анализа мы оставим неопределенными действия самого левого ферзя, не имеющего соседа. Предполагаем, что ферзи-соседи уже инициализированы, это значит, что они нашли взаимно удовлетворяющее решение. Ферзь из текущего столбца просто ставит себя в первую строку. Ниже приведен алгоритм на псевдокоде. 

function queen.initialize(col, neigh) -> boolean

  /* инициализация значений столбца и соседа */
  column := col
  neighbor := neigh

  /* начинаем со строки 1 */
  row := 1
end

5.2.2. Нахождение решения

Использование генераторов

Чтобы найти решение, ферзь просто спрашивает своих соседей, могут ли они его атаковать. Если да, то ферзь продвигается. Если дальнейшее передвижение запрещено, возвращается значение «неудача». Если соседи сообщают, что они атаковать не могут, то (локальное) решение найдено. 

function queen.findSolution -> boolean

  /* проверка позиции */
  while neighbor.canAttack (row, column) do
    if not self.advance then
     return false

  /* нашли решение */
  return true
end

Как мы указывали в главе 4, псевдопеременная self обозначает получателя последнего сообщения. В данном случае мы хотим, чтобы ферзь, которому поручено найти решение, послал сообщение advance самому себе.

5.2.3. Продвижение на следующую позицию

Использование генераторов

Процедура advance распадается на два случая. Если мы еще не достигли конца, ферзь просто увеличивает номер строки на 1. Если ферзь уже попробовал все позиции и не нашел решения, то не остается ничего, кроме как попросить у соседа нового решения и начать со строки 1. 

function queen.advance -> boolean

  /* пробуем следующую строку */
  if row < 8 then
  begin
    row := row + 1
    return self.findSolution
  end

  /* не можем двигаться дальше */

  /* сдвинем соседа к следующему решению */
  if not neighbor.advance then
    return false

  /* начнем снова с 1-й строки */
  row := 1
  return self.findSolution
end

Теперь осталось только напечатать решение. Это делается очень просто с помощью метода print, который рекурсивно повторяется для всех соседей. 

procedure print

  neighbor.print
  write row, column
end

5.3. Задача о восьми ферзях на различных языках программирования

Разделы

В этом параграфе мы приведем решение задачи о восьми ферзях для каждого рассматриваемого языка программирования. Сравните тексты программ. Обратите внимание на то, как свойственные языку черты привносят хитроумные изменения в решение задачи. В частности, проанализируйте решения на языках Smalltalk и Objective-C, использующие специальный «караульный» класс, и сравните их с кодом на Object Pascal, C++ или Java, каждый из которых использует нулевой указатель для самого левого ферзя и постоянно вынужден проверять значение указателей.

5.3.1. Задача о восьми ферзях: Object Pascal

Задача о восьми ферзях на различных языках программирования

Определение класса для задачи о восьми ферзях на языке Object Pascal версии Apple приведено ниже. Тонкой и важной чертой является то, что это определение рекурсивно — объекты типа Queen содержат поле данных типа Queen. Это достаточно ясно показывает, что объявление и выделение памяти не обязательно связаны. В противном случае для каждого объекта Queen потребовалось бы бесконечно много памяти. Мы сравним это с кодом для C++ и детально рассмотрим связь между объявлением и выделением памяти в главе 12. 

type

  Queen = object

    (* поля данных *)
    row  : integer;
    column : integer;
    neighbor : Queen;

    (* инициализация *)
    procedure initialize (col : integer; ngh : Queen);

    (* операции *)
    function canAttack (testRow, testColumn : integer) :
	     boolean;
    function findSolution : boolean;
    function advance : boolean;
    procedure print;
end;

Для языка Delphi определение класса будет отличаться совсем немного (оно показано ниже). Вариант языка для фирмы Borland позволяет разбить определение класса на открытую (public) и закрытую (private) части, а также добавить функцию-конструктор, используемую вместо программы initialize. 

TQueen = class (TObject)

public
  constructor Create (initialColumn : integer; 
    nbr : TQueen);
  function findSolution : boolean;
  function advance : boolean;
  procedure print;

private

  function canAttack (testRow, testColumn : integer) :  
    boolean;

  row  : integer;
  column : integer;
  neighbor : TQueen;
end;

Псевдокод, приведенный в предыдущих параграфах, достаточно близок к варианту на языке Pascal с двумя основными отличиями. Первое: отсутствие в языке Pascal оператора return. Второе: необходимость сначала проверить, есть ли у ферзя сосед, перед посылкой сообщения этому соседу. Функции findSolution и advance, приведенные ниже, демонстрируют эти различия. (Заметим, что язык Delphi Pascal отличается от стандартного Pascal тем, что допускает «быстрое» выполнение директив and (и) и or (или), как и C++. Таким образом, код на языке Delphi может в одном выражении объединить проверку существования ненулевого соседа и посылку сообщения этому соседу.) 

function Queen.findSolution : boolean;

var

  done : boolean;

begin
  done := false;
  findsolution := true;

  (* проверка позиции *)
  if neighbor < > nil then

  while not done and neighbor.canAttack(row, column) do
    if not self.advance then
    begin
      findSolution := false;
      done := true;
    end;
end;

function Queen.advance : boolean:
begin

advance := false;

  (* пробуем следующую строку *)
  if row < 8 then
  begin
    row := row + 1;
    advance := self.findSolution;
  end
  else begin

    (* не можем двигаться дальше *)

    (* сдвинуть соседа к следующему решению *)
    if neighbor < > nil then
     if not neighbor.advance then
       advance := false
     else begin
       row := 1;
       advance := self.findSolution;
     end;
  end;
end;

Основная программа отводит память для каждого из восьми ферзей и инициализирует их, определяя столбец и соседа. Поскольку во время инициализации будет найдено первое (локальное) решение, ферзи должны будут напечатать это решение. Код на языке Apple Object Pascal, выполняющий эту задачу, показан ниже. Здесь neighbor и i — временные переменные, используемые во время инициализации, а lastQueen — последний созданный ферзь. 

begin
  neighbor := nil;

  for i := 1 to 8 do
  begin

    (*   создать и инициализировать нового ферзя *) 
    new (lastQueen);
    lastQueen.initial (i, neighbor);
    if not lastQueen.findSolution then
      writeln(‘no solution’);

    (* самый новый ферзь — сосед предыдущего *)
    neighbor := lastQueen;
  end;

  (* печать решения *)
  lastQueen.print;
  end;
end.

Предоставляя явные конструкторы, объединяющие создание новых объектов и их инициализацию, язык Delphi позволяет ликвидировать одну из временных переменных. Основная программа на Delphi будет такова: 

begin

  lastQueen := nil;
  for i := 1 to 8 do
  begin

    (* создать и инициализировать нового ферзя *)
    lastQueen := Queen.create(i, lastQueen);
    lastQueen.findSolution;
  end;

  // печать решения
  lastQueen.print;
end;

5.3.2. Задача о восьми ферзях: C++

Задача о восьми ферзях на различных языках программирования

Наиболее существенной разницей между приведенным ранее описанием алгоритма на псевдокоде и типичным кодом для C++ является непосредственное использование указателей. Ниже приведено описание класса Queen. Каждый представитель класса содержит в себе указатель на другого ферзя. Заметьте, что в отличие от Object Pascal в языке C++ это значение должно быть объявлено как указатель на объект, а не как сам объект. 

class Queen
{
public:

    // конструктор
    Queen (int, Queen *);

    // поиск и печать решения
    bool findSolution();
    bool advance();
    void print();

private:

    // поля данных
    int row;
    const int column;
    Queen *neighbor;

    // внутренний метод
    bool canAttack (int, int);
};

Как и в случае программы на языке Delphi Pascal, мы реализовали метод initialize в конструкторе. Коротко опишем его.

Есть три поля данных. Целочисленное поле column объявлено как const. Это определяет поле как неизменяемое. Третье поле данных имеет тип указателя; оно либо содержит нулевое значение (то есть ни на что не указывает), либо ссылается на другого ферзя.

Поскольку инициализация осуществляется конструктором, основная программа может просто создать восемь объектов-ферзей и потом напечатать решение. Переменная lastQueen указывает на последнего созданного ферзя. Вначале это значение равно null-указателю — ни на что не указывает. Затем в цикле конструируются восемь ферзей, инициализируемых значениями столбца и предыдущего ферзя. Когда цикл закончится, самый левый ферзь будет содержать нулевой указатель в поле neighbor, а все остальные — указатели на своих соседей; lastQueen указывает на самого правого ферзя. 

void main()
{
  Queen *lastQueen = 0;
  for (int i = 1; i <= 8; i++)
   {
    lastQueen = new Queen(i, lastQueen);
    if (! lastQueen -> findSolution())
      cout << "no solution\n";
   }
  lastQueen -> print();
}

Мы опишем только методы, иллюстрирующие важные моменты. Полное решение можно посмотреть в Приложении A.

Конструктор должен использовать в заголовке инициализирующую конструкцию для присваивания значения константе column, так как запрещается присваивать что-либо полям, объявленным как const. Инициализирующая конструкция используется и для поля neighbor, хотя мы не объявляли это поле как константу. 

Queen::Queen(int col, Queen *ngh)
  : column(col), neighbor(ngh)
{
  row = 1;
}

Поскольку значение переменной neighbor может быть либо ссылкой на ферзя, либо нулевым, необходима проверка, прежде чем сообщение будет послано соседу. Это показано в методе findSolution. Использование укороченного вычисления логических выражений и возможность выхода из середины процедуры упрощают код по сравнению с версией на Object Pascal — в остальном же они очень похожи. 

bool Queen::findSolution()
{
  while (neighbor && neighbor->canAttack(row, column))
    if (! advance())
      return false;
  return true;
}

Метод advance подобным же образом должен проверять наличие соседа перед тем, как продвигать его к следующему решению. Посылая сообщение себе, как это делается в рекурсивном findSolution, не обязательно указывать получателя. 

bool Queen::advance()
{
  if (row < 8)
  {
    row++;
    return findSolution();
  }

  if (neighbor && ! neighbor->advance())
    return false;

  row = 1;
  return findSolution();
}

5.3.3. Задача о восьми ферзях: Java

Задача о восьми ферзях на различных языках программирования

Решение на языке Java во многом напоминает код на C++. Однако в Java тело метода пишется прямо «на месте», и указания public и private помещаются в определение класса. Ниже приводится определение класса Queen; некоторые методы опущены. 

class Queen
{
   // поля данных
   private int row;
   private int column;
   private Queen neighbor;

   // конструктор
   Queen (int c, Queen n)
    {
     // инициализировать поля данных
     row = 1;
     column = c;
     neighbor = n;
    }

   public boolean findSolution()
    {
     while (neighbor != null &&
       neighbor.canAttack(row, column))

     if (! advance ())
       return false;

     return true;
    }

   public boolean advance()
    {
     . . .
    }

   private boolean canAttack(int testRow, int testColumn)
    {
     . . .
    }

   public void paint (Graphics g)
    {
     . . .
    }
}

В отличие от языка C++ в Java связь со следующим ферзем определяется как объект типа Queen, а не как указатель на Queen. Перед посылкой сообщения ферзю, определяемому переменной neighbor, выполняется явная проверка на ненулевое значение.

Поскольку язык Java предоставляет богатое множество графических подпрограмм, решение будет отличаться от прочих тем, что окончательная расстановка ферзей будет нарисована на экране. Метод paint рисует ферзя, потом изображает соседей. 

class Queen
{
  . . .
  public void paint (Graphics g)
   {
    // x, y — левый верхний угол
    int x = (row — 1) * 50;
    int y = (column — 1) * 50;

    g.drawLine(x+5, y+45, x+45, y+45);
    g.drawLine(x+5, y+45, x+5, y+5);
    g.drawLine(x+45, y+45, x+45, y+5);
    g.drawLine(x+5, y+35, x+45, y+35);
    g.drawLine(x+5, y+5, x+15, y+20);
    g.drawLine(x+15, y+20, x+25, y+5);
    g.drawLine(x+25, y+5, x+35, y+20);
    g.drawLine(x+35, y+20, x+45, y+5);
    g.drawLine(x+20, y+20, 10, 10);

    // затем рисуем соседа
    if (neighbor != null)
      neighbor.paint(g);
  }
}

В языке Java нет ни глобальных переменных, ни «безклассовых» функций. Как мы опишем более детально в главе 8, программа начинается с определения подкласса системного класса Applet и переопределения некоторых методов. В частности, метод init используется для инициализации приложения, а метод paint — для перерисовки экрана. Мы также определим метод mouseDown, вызываемый при нажатии кнопки мыши, чтобы заставить программу переходить к следующему решению. Назовем класс нашего приложения QueenSolver и определим его так: 

public class QueenSolver extends Applet
{
private Queen lastQueen;

  public void init()
   {
    lastQueen = null;
    for (int i = 1; i <= 8; i++)
     {
       lastQueen = new Queen(i, lastQueen);
       lastQueen.findSolution();
     }
   }

  public void paint(Graphics g)
   {
    // рисуем доску
    for (int i = 0; i <= 8; i++)
     {
      g.drawLine(50 * i, 0, 50 * i, 400);
      g.drawLine(0, 50 * i, 400, 50 * i);
     }

    // рисуем ферзей
    lastQueen.paint(g);
   }

  public boolean mouseDown(java.awt.Event evt, int x, 
    int y)
   {
    // найти и напечатать следующее решение
    lastQueen.advance();
    repaint();
    return true;
   }
}

Заметьте, что класс приложения должен быть объявлен как public, чтобы быть доступным в основной программе.

5.3.4. Задача о восьми ферзях: Objective-C

Задача о восьми ферзях на различных языках программирования

Описание интерфейса нашего класса Queen таково: 

@interface Queen : Object
{
   /* поля данных */
   int row;
   int column;
   id neighbor;
}

 /* методы */
- (void) initialize: (int) c neighbor: ngh;
- (int)  advance;
- (void) print;
- (int)  canAttack: (int) testRow 
            column: (int) testColumn;
- (int)  findSolution;

@end

Каждый ферзь имеет три поля данных: строку, столбец и ферзя-соседа. Последнее объявлено с типом id. Это указывает, что значением переменной будет объект, хотя и не обязательно ферзь.

В действительности мы можем использовать бестиповую сущность переменных в языке Objective-C себе во благо. Применим технику, которая невозможна или, по крайней мере, не так проста в языках со строгими ограничениями на тип (такими, как C++ или Object Pascal). Вспомним, что самый левый ферзь не имеет соседа. В решении на языке C++ признаком этого служило нулевое значение переменной, содержащей указатель на соседа, для самого левого ферзя. В данном решении мы вместо этого создаем новый класс — караульное (sentinel) значение. Самый левый ферзь будет указывать на это караульное значение, тем самым обеспечивая действительного соседа каждому ферзю.

Караульные величины часто используются как маркеры конца; их можно обнаружить в алгоритмах, работающих со списками, такими как наш список ферзей. Различие между объектно-ориентированным «караулом» и более традиционными проверками состоит в том, что первый может быть активным — у него есть поведение, то есть он может отвечать на запросы.

Каково должно быть поведение караульных величин? Вспомним, что ссылки на соседа в нашем алгоритме используются двояко. Во-первых, чтобы убедиться, что интересующая нас позиция не атакована; караульная величина на такой запрос всегда должна отвечать отрицательно, поскольку она не может ничего бить. Второе использование ссылок на соседа — в рекурсивном вызове процедуры print. В этом случае караульная величина просто ничего не делает, так как не имеет никакой информации о решении.

Объединяя вместе все эти рассуждения, приходим к следующей реализации нашего «караульного ферзя»: 

@implementation SentinelQueen : Object
- (int) advance
{
  /* ничего не делаем */
  return 1;
}

- (int) findSolution
{
  /* ничего не делаем */
  return 1;
}

- (void) print
{
  /* ничего не делаем */
}

- (int) canAttack
  :(int) testRow column
  :(int) testColumn;
{
  /* не можем атаковать */
  return 0;
}

@end

В полном решении есть часть, реализующая SentinelQueen, но к ней нет интерфейса. Это допустимо, хотя компилятор выдаст предупреждение, поскольку такая ситуация несколько необычна.

Использование караульного объекта позволяет методам класса Queen просто посылать сообщения соседу без предварительного изучения, является ли данный ферзь самым левым. Например, в методе canAttack: 

- (int) canAttack: (int) testRow 
           column: (int) testColumn
{
   int columnDifference;

   /* можем бить ту же строку */
   if (row == testRow)
     return 1;

   columnDifference = testColumn — column;

   if (
       (row + columnDifference == testRow)
       ||(row — columnDifference == testRow)
      )
     return 1;

   return [ neighbor canAttack: testRow 
                        column: testColumn ];
}

Внутри метода посылка сообщения самому себе осуществляется с помощью псевдопеременной self: 

- (void) initialize: (int) c neighbor: ngh
{
   /* установить поля — константы */
  column = c;
  neighbor = ngh;
  row = 1;
}

- (int) findSolution
{
  /* цикл, пока не найдем решение */
  while ([neighbor canAttack: row and: column ])
    if (! [self advance])
      return 0; /* возвращаем false */
  return 1;    /* возвращаем true */
}

Остальные методы аналогичны и здесь не рассматриваются.

5.3.5. Задача о восьми ферзях: Smalltalk

Задача о восьми ферзях на различных языках программирования

Решение задачи о восьми ферзях на языке Smalltalk во многих отношениях похоже на Objective-C. Как и последний, язык Smalltalk учитывает тот факт, что самый левый ферзь не имеет соседа, вводя специальный караульный (sentinel) класс. Его единственная цель в том, чтобы предоставить получателя сообщений, посланных самым левым ферзем.

Караульная величина является единственным представителем класса SentinelQueen (подкласс класса Queen), который реализует следующие три метода: 

advance
  " караульный ферзь не атакует "
  ^ false

canAttack: row column: column
  " караульный ферзь не может атаковать "
  ^ false

result
  " возвращаем пустой список в качестве результата "
  ^ List new

Единственное различие между версиями на Objective-C и Smalltalk в том, что программа на языке Smalltalk возвращает результат как список величин, а не выводит их на печать. Техника вывода на печать довольно хитро устроена в Smalltalk и различается от реализации к реализации. Возвращая список, мы можем отделить эти различия от основных методов.

Класс Queen является подклассом класса Object. Представители класса Queen содержат три внутренние переменные: row (строка), column (столбец) и neighbor (сосед). Инициализация осуществляется в методе setColumn : neighbor:. 

setColumn: aNumber neighbor: aQueen
  " инициализация полей данных "
  column := aNumber.
  neighbor := aQueen.
  row := 1.

Метод canAttack отличается от аналогичного метода для языка Objective-C только синтаксисом: 

canAttack: testRow column: testColumn 

  | columnDifference |

  columnDifference := testColumn — column.

  ((row = testRow) or:
    [ row + columnDifference = testRow]) or:
    [ row — columnDifference = testRow])
     ifTrue: [ ­ true ].

^ neighbor canAttack: testRow column: testColumn

Вместо того чтобы проверять условие на отрицание, язык Smalltalk предоставляет явный оператор ifFalse, используемый в методе advance: 

advance
  " сначала попробуем следующую строку "
  (row < 8)
    ifTrue: [ row := row + 1. ­ self findSolution].

  " не можем двигаться дальше, сдвигаем соседа "
  (neighbor advance)
    ifFalse: [ ­ false ].

  " начнем со строки 1 "
  row := 1.

  ^ self findSolution

Цикл while в языке Smalltalk должен использовать блок при проверке условия, как в следующем примере: 

findSolution
  [ neighbor canAttack: row column: column ]
     whileTrue: [ self advance ifFalse: [ ­ false ] ].

  ^ true

Для получения списка окончательных позиций используется рекурсивный метод. Вспомним, что караульная величина создает пустой список в ответ на сообщение result: 

result
  ^ neighbor result; addLast: row

Решение будет получено с помощью вызова следующего метода, не являющегося частью класса Queen и относящегося к некоторому другому классу, например, такому как Object: 

solvePuzzle 

  | lastQueen |
  lastQueen := SentinelQueen new.
   1 to: 8 do: [:i | lastQueen := (Queen new)
    setColumn: i neighbor: lastQueen.
    lastQueen findSolution ].

  ^ lastQueen result

Решение задачи о восьми ферзях, построенное без применения караульной величины, описано в моей более ранней книге по языку Smalltalk [Budd 1987].

Упражнения

Разделы

  1. Измените программы так, чтобы они выдавали все возможные решения, а не только одно. Сколько существует решений задачи о восьми ферзях? Сколько из них являются поворотами других? Как можно отбросить повороты?
  2. Как вы можете объяснить, что караульный класс в языках Objective–C и Smalltalk не предоставляет свою версию метода findSolution, несмотря на то что сообщение findSolution посылается соседу в методе advance?
  3. Предположим, мы обобщим задачу о восьми ферзях как проблему N ферзей. Задача: как расположить N ферзей на шахматной доске N * N? Как изменятся программы? Ясно, что существуют N, для которых нет решений (например, N=2 или N=3). Что будет в этом случае с нашими программами? Как можно организовать более осмысленный вывод ответа?
  4. Используя графические возможности вашей системы, измените одну из программ так, чтобы она динамически изображала на шахматной доске позиции каждого ферзя по мере своей работы. Какие части кода должны знать об устройстве вывода?

Учебный пример: задача о восьми ферзях

Сайт создан в системе uCoz