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

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

Объединим куски. Мы получим программу, реализующую автомат, как мы уже видели в игре 12. Вы можете рассматривать имена, написанные прописными буквами (С, СБ, СОК, С8, ПРОГРАММА) как метки, позволяющие отсылать к части программы, в начале которой стоят эти имена со знаком «:» после них, и как инструкцию ПЕРЕЙТИ К, если они указаны в конце последовательности операций. Поэтому все это непосредственно переводится на совершенно любой язык.

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

С: ЕСЛИ k = 9 ТО С8

ИНАЧЕ искать первое свободное поле на строке k и придать значение этого поля величине i ;

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

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

КОНЕЦ_ЕСЛИ

СОК: занять k , i ; k := k + 1; С

СБ: k := k − 1;

ЕСЛИ k = 0 ТО Я

ИНАЧЕ найти место i ферзя k ; освободить k , i ;

ИСКАТЬ первое свободное поле на строке k , расположенное правее i , и придать значение этого поля величине i ;

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

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

КОНЕЦ_ЕСЛИ

С8: выписать решение;

найти место i ферзя 8;

освободить 8, i ;

k := 8; СБ

Мы можем улучшить эту программу. Неприятно иметь необходимость находить заново место ферзя в строке, тем более, что знание этого места необходимо дли вывода на экран полученного решения. Заменим i номером c [ k ] столбца, где расположен ферзь k . Тогда искать место этого ферзя больше не нужно. Именно операция «занять k , i » и будет давать величине c [ k ] значение i . У нас есть два похожих отрывка в программе:

— в СБ:

искать первое свободное поле на строке k , расположенное правее i , и придать значение этого поля величине i ;

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

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

— в С:

искать первое свободное поле на строке k и придать значение этого поля величине i ;

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

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

Второй отрывок идентичен первому, если вместо того, чтобы искать первое свободное поле (что подразумевается как начальный ход), мы потребуем искать первое свободное поле после i , где i придано значение 0. Эту общую последовательность команд мы назовем И (от «искать»). Вот новая программа:

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

С: ЕСЛИ k = 9 ТО С8

ИНАЧЕ c [ k ] := 0; И

КОНЕЦ_ЕСЛИ

КОНЕЦ_ЕСЛИ

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

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

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

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

СОК: занять k , c [ k ]; k := k + 1; С

СБ: k := k − 1;

ЕСЛИ k = 0 ТО Я

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

И

КОНЕЦ_ЕСЛИ

С8: выписать решение;

k := 8; освободить k , c [ k ], СБ

Мы можем еще немного выиграть. Значение 9 для k не может быть достигнуто иначе как после размещения ферзя на строке 8 с помощью СОК. Вместо того, чтобы проверять справедливость соотношения к = 9 в С, можно сделать это в СОК. Если нужно разместить восьмого ферзя, то бесполезно требовать «занять k , i » с тем, чтобы сразу после этого освободить указанное поле. Отсюда — новая, еще более простая программа.

ПРОГРАММА: 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 в СБ), освобождая ферзей, пока не окажется возможным передвинуть какого-то ферзя правее (цикл СБ, И, СБ из И). Как только оказывается возможным переместить ферзя правее, он туда перемещается и возобновляется спуск.

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

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

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

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

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