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

— в СБ:

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

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

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