Программирование игр и головоломок - Жак Арсак

ПРОГРАММА: k := 1; инициализировать игру; С

С: c[k] := 0; И

И: искать первое свободное поле на строке k после c[k]

  и придать значение этого поля величине c[k];

  ЕСЛИ таких полей нет ТО СБ

  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

СОК: ЕСЛИ k = 8 ТО записать решение; СБ

  ИНАЧЕ занять k, c[k]; k := k + 1; С

СБ: k := k − 1;

  ЕСЛИ k = 0 ТО Я

    ИНАЧЕ освободить k, c[k]; И

  КОНЕЦ_ЕСЛИ

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

Перечитаем нашу программу, чтобы лучше понять ее стратегию. Мы начинаем с пустой шахматной доски. Строчка за строчкой мы ищем первое свободное поле и занимаем его. Это — цикл, который идет от С к И, затем в СОК и затем в С, и который останавливается, когда либо все ферзи уже размещены (выход в СБ из СОК), либо, что более вероятно, когда одна из строк блокирована (выход в СБ из И).

Если строка блокирована (или после того, как решение выписано), мы поднимаемся строчкой вверх (k := k − 1 в СБ), освобождая ферзей, пока не окажется возможным передвинуть какого-то ферзя правее (цикл СБ, И, СБ из И). Как только оказывается возможным переместить ферзя правее, он туда перемещается и возобновляется спуск.

Учитывая все это, мы видим, что наша стратегия достаточно проста и выглядит естественной, как только мы к ней привыкаем: ведь привычка — вторая натура, не так ли?

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

— алгоритм или стратегия, которой мы следуем при проведении вычислений;

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

Это — один из фундаментальных принципов программирования: стараться отложить на как можно более позднее время любое решение относительно выбора наиболее удобного представления данных. Рассмотрите сначала стратегию, которой вы следуете, используя символические формулы, которые вы впоследствии разовьете. Есть только две возможности:

— либо, как в рассматриваемом случае, вы приходите к цели. Как только этот первый этап пройден, вы спокойно обсуждаете представление данных;

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

Программирование всегда должно идти нисходящим путем. Сначала — алгоритм или стратегия. Потом — структура данных.

Посмотрим, какие структуры данных возможны в нашей задаче. Первая, наиболее естественная идея: я представляю шахматную доску с помощью квадратной таблицы с 8 строками и 8 столбцами. Я ставлю нули на пустые клетки. Чтобы найти свободное поле на строке, я перебираю поле за полем на строке, пока не нахожу поле с нулем. Это просто. Но как теперь занять поле k, c[k]? Поместив туда значение k. Это тоже просто. Но ферзь, которого нужно разместить, бьет некоторое количество полей, и их уже нельзя будет в дальнейшем занимать. Чтобы это учесть, нужно записать значение к по всем ранее свободным полям, которые теперь бьет этот новый ферзь. Здесь нужен цикл для занятия полей под ферзем на той же вертикали, а затем два других цикла — для каждой из диагоналей, проходящих через это поле (бесполезно занимать поля строки, потому что строка больше рассматриваться не будет). Это проще всего. Что касается освобождения, то нужно пробежать по шахматной доске и заменить там все значения k нулями. Очень долго…

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

Таким образом, нужен вектор с 8 полями, чтобы сказать, свободны ли столбцы. Обозначим этот вектор cm. Тогда cm[i] = 0 будет означать, что в столбце i нет ни одного ферзя. Его не надо путать с c[k], который отвечает на вопрос, в каком столбце стоит ферзь k.

Диагонали характеризуются тем условием, что сумма или разность номеров строки и столбца постоянны. Обозначим через дп диагонали, соответствующие сумме, дм — диагонали, соответствующие разности. В первом приближении диагонали, соответствующие полю k, i, суть дп[k + i] и дм[k − i].

Но при 1 ≤ k ≤ 8, 1 ≤ i ≤ 8 сумма меняется от 2 до 16, а разность — от −7 до 7. Чтобы остаться в промежутке от 1 до 13 (чего некоторые языки просто требуют), нужно вычитать 1 из суммы и прибавлять 8 к разности, Тогда диагонали, проходящие через k, i, суть дп[k + i − 1] и дм[k − i + 8].

Операция «искать первое свободное поле…» реализуется маленьким циклом в программе. Вот — на псевдоязыке, используемом в этой книге и близком к Бейсику, LSE и языку Паскаль, — что из всего этого получается:

  ТАБЛИЦА с[8], ст[8], дп[15], дм[15]

    k := 1

  ДЛЯ j := 1 ДО 8 ВЫПОЛНЯТЬ

    ст[j] = 0

  ВЕРНУТЬСЯ

  ДЛЯ j := 1 ДО 15 ВЫПОЛНЯТЬ

    дп[j] := 0; дм := 0

  ВЕРНУТЬСЯ

С c[k] : = 0

И i := c[k] + 1

  ВЫПОЛНЯТЬ

    ЕСЛИ i = 9 ТО КОНЧЕНО

    КОНЕЦ_ЕСЛИ

    ЕСЛИ ст[i] = 0 И дп[k + i − 1] = 0 И

      дм[k − i + 8] = 0 ТО КОНЧЕНО

    КОНЕЦ_ЕСЛИ

    i := i + 1

  ВЕРНУТЬСЯ

  ЕСЛИ i = 9 ТО ПЕРЕЙТИ К СБ КОНЕЦ_ЕСЛИ

СОК c[k] := i

  ЕСЛИ k = 8 ТО ВЫВЕСТИ c;

  ПЕРЕЙТИ К СБ КОНЕЦ_ЕСЛИ

  ст[i] := k; дп[k + i − 1] := k;

  дм[k − i + 8] := k; k := k + 1

  ПЕРЕЙТИ К С

СБ k := k − 1

  ЕСЛИ k = 0 ТО ПЕРЕЙТИ К Я КОНЕЦ_ЕСЛИ

  i := c[k]; ст[i] := 0; дп[k + i − 1] := 0;

  дм[k − i + 8] := 0

  ПЕРЕЙТИ К И

Я КОНЕЦ_РАБОТЫ

У вас теперь есть все, что только может быть вам нужно для того, чтобы это заработало на вашем компьютере.

Что касается симметрии, то вот указание. Эта программа заставляет первого ферзя пробежать всю первую строку. Но достаточно, чтобы он пробежал половину, а затем дополнить результат по симметрии. Остановить пробег, когда c[1] достигает значения 4, нелегко, но легко начать пробег с цифры 5. Ну, уж теперь-то я сказал вам достаточно…