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

Исходя отсюда, следующие числа p определяются диагоналями, которые перерезают вертикальный отрезок, выходящий из p i так, что p − p i ≤ g i= ( p i − 1) : 2. Тогда можно восстановить первоначальную последовательность, несущую нули, вплоть до ( p i − 1) : 2.

Теперь вы легко сможете доказать, что интересующая нас последовательность p i есть последовательность чисел Фибоначчи.

Составьте программу, перечисляющую p i , g i .

Головоломка 20.Полное решение.

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

Заметим сначала, что два ферзя не могут находиться на одной строке (горизонтали) и, поскольку нужно поставить 8 ферзей на 8 строк, то на каждой строке есть ферзь. Поэтому я буду говорить «ферзь k » вместо «ферзь, стоящий на строке k ».

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

Чтобы начать, я помещаю ферзя в первый столбец на первой строке. Тогда мне остается решить меньшую задачу; разместить 7 ферзей на 7 последних строках шахматной доски, учитывая, что ферзь стоит на первом поле первой строки. Я получу тогда все решения с ферзем 1 в столбце 1. Затем я поставлю ферзя 1 в столбец 2 и разрешу задачу с 7 ферзями, и т. д. — 8 раз.

Обобщим. Мы собираемся решить частную, но нужную задачу: полагая, что уже есть ферзи, правильно размещенные на строках от 1 до k − 1, и зная их положение, найти все возможные решения, размещая подходящим образом ферзей с номерами от k до 8. Обозначим программу, которая это делает, через HR( k ) [24] Маленькая головоломка для знающих французский (или хотя бы имеющих словарь): откуда это обозначение? — Примеч. ред. . Стратегия очень проста:

— мы пробегаем все поля на строке k ,

— если поле свободно (т. е. не бьется уже поставленными ранее ферзями), то мы ставим на него ферзя k и решаем ту же задачу для k + 1.

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

Для задачи HR ( k ) необходимо знание состояния игры, получающегося после размещения первых k − 1 ферзей. Это предполагает по крайней мере, что известны столбцы, занятые этими ферзями. Может быть, следовало бы сказать больше. Обозначим символически «занять k , i » операцию, которая констатирует факт, что в столбце i на строке k помещен ферзь.

HR ( k =

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

ЕСЛИ место k , i свободно ТО

занять k , i

ЕСЛИ k = 8 ТО выписать решение

ИНАЧЕ HR(к + 1)

КОНЕЦ_ЕСЛИ

освободить k , i

КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Операция «освободить k , i » отменяет то, что делает операция «занять k , i ». Для решения задачи нужно изложить последовательность инициализации, отмечающую, что ничего не сделано и ни один ферзь в игре не участвует, а затем вызвать HR (1).

Эта процедура рекурсивна, так как она обращается сама к себе. Тщательно изучите ее. Если вы исходите из гипотезы, что HR ( k + 1) находит и выводит такие решения, у которых первые k ферзей стоят там, где они поставлены, то у вас не будет никаких затруднений в том, чтобы убедиться, что эта процедура совершенно правильна. Используйте крайние случаи: k = 8 и начальное обращение с k = 1.

Если у вас в наличии нет никакого другого языка, кроме Бейсика, или если вы раб своего языка до такой степени, что не желаете учить что-нибудь, кроме Бейсика, то вам придется писать итеративное решение. Это сложнее.

Будем исходить из наиболее общей ситуации. Пусть на шахматной доске уже размещено k − 1 ферзей. Обозначим это состояние буквой С (в смысле «самое общее состояние»). Это состояние раскладывается на три подсостояния:

— уже размещено по местам 8 ферзей ( k − 1 = 8): состояние С8;

— на строке с номером k есть допустимое место для ферзя: состояние СОК;

— либо строка с номером k блокирована полностью, либо все возможные поля на ней уже исследованы: СБ.

Запишем кусок программы, который различает эти три случая:

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

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

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

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

КОНЕЦ_ЕСЛИ

Рассмотрим теперь каждое из подсостояний.

СОК: есть свободное место в точке k , i . Туда ставим ферзя k и получаем снова самое общее состояние с еще одним размещенным ферзем.

Формально:

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

Если строка k блокирована, а также если она полностью исследована, то нужно изменить выбор, который был сделан для ферзя k − 1, и передвинуть его на свободное место правее (если оно есть). Это возвращение назад относится непосредственно к ферзю k − 1 и, следовательно, сохраняет только k − 2 первых ферзей, что вызывает необходимость уменьшить k на 1. Может случиться, что это приведет нас к k = 0, т. е. может случиться, что все места на строке 1 уже исследованы и, следовательно, работа закончена, что мы обозначим как состояние Я, конец программы.

СБ: k := k − 1;

ЕСЛИ k = 0 ТО Я

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

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

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

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

КОНЕЦ_ЕСЛИ

Когда 8 ферзей уже размещены, нужно записывать решение. Бесполезно искать другое место для восьмого ферзя, потому что если на восьмой строке и есть свободное место, то только одно. Таким образом, строка 8 оказывается полностью исследованной и нужно снова размещать 7 предыдущих ферзей. А состояние, в котором строка 8 полностью исследована, — это состояние СБ с k = 8.

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

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

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

k := 8; СБ

Остается пустить этот процесс в ход. В начале ни один ферзь в игре не участвует и, следовательно, k − 1 = 0. Нужна инициализация, которая бы это открыто провозглашала: