Текст книги "Программирование игр и головоломок"
Автор книги: Жак Арсак
Жанр:
Программирование
сообщить о нарушении
Текущая страница: 11 (всего у книги 16 страниц)
5. Стратегия без игры (выигрывающие стратегии)
Игра 27.
Чтобы найти рекурсивное решение в игре НАДЕВАТЬ, нужно действовать по индукции. Назовем НАДЕВАТЬ(n) решение, которое помещает n шашек на первоначально пустое игровое поле. Предположим, что мы умеем выполнять задание игры НАДЕВАТЬ для p, меньших n.
Как поставить на место последнюю шашку? Мы не можем ее поставить, если это поле не является следующим за первым полем, занятым шашкой. Следовательно, для ее помещения на место нужно, чтобы в игре участвовала одна-единственная шашка шашка с номером n − 1. С помощью НАДЕВАТЬ(n − 1) можно поставить на место все шашки от 1 до n − 1. Если мы удалим все шашки от 1 до n − 2, то останется только шашка n − 1, можно будет поставить шашку n, а затем снова надеть шашки от 1 до n − 2:
НАДЕВАТЬ(n) = НАДЕВАТЬ(n − 1);
СНИМАТЬ(n − 2); поместить(n); НАДЕВАТЬ(n − 2)
То же самое вы должны проделать и для СНИМАТЬ. Эта запись не учитывает простых частных случаев, позволяющих избежать в этом рекурсивном определении порочного круга: оно должно содержать не рекурсивные случаи, Определение должно включать n − 1 и n − 2, Вы можете либо определить игру НАДЕВАТЬ для n = 0 (ничего не делать) и n = 1 (поставить первую шашку, что всегда возможно), либо для n = 1 и n = 2. Вы сами решите, как лучше сделать.
Но еще более удивительно изучение «итеративной» стратегии для этой игры, т, е. последовательности ходов, приводящих к выигрышу. Рассмотрим игру НАДЕВАТЬ. Вы увидите, что первый ход предопределен. Используйте тот факт, что ход не должен разрушать то, что было сделано на предыдущем ходе. Вы установите, что
– вы делаете первой шашкой один ход из двух,
– остальные ходы полностью определены,
так что в игре НАДЕВАТЬ нет никакого выбора. Она полностью определена на каждом ходе: делайте единственно возможный не глупый ход…
Для игры СНИМАТЬ есть два способа начать игру:
– удалить сначала шашку 1 (это возможно всегда),
– удалить сначала шашку 2 (это шашка, которая следует за первой шашкой, расположенной на игровом поле).
Никакого другого выбора сделать уже нельзя, все остальное полностью определено, Выясните, как сделать этот первый выбор.
Игра 28.
Есть только одно указание, чтобы помочь вам, если вы не нашли решение: есть промежуточное решение, в котором шашки перемежаются. Вы можете составить сначала рекурсивную процедуру, которая их перемежает, а затем рекурсивную процедуру, которая их заново разделяет. Но вы можете сделать это и итеративным способом…
Игра 29.
Используйте индукцию или ее двоюродную сестру рекурсию. Если у вас на вашем компьютере рекурсивных возможностей нет (бедные владельцы Бейсика…), используйте ее по крайней мере в вашем черновике: хорошая рекурсивная процедура – лучшее из описаний решаемой задачи.
Решите сначала задачу с 8 буквами и 10 полями.
Рассмотрим теперь более общую задачу. Пусть X обозначает некоторую последовательность пар аб без пустых полей. Используя предыдущий метод (та же последовательность ходов плюс один), перейдите от ситуации
..абабХабаб
к ситуации
бббб..Хаааа
затем решите задачу для X и отправьте два последних а на их место.
Но таким способом вы не охватываете всех возможных случаев. Нужно найти решения в других частных случаях. Вы легко найдете, в каких.
Игра 30.
Это – типичная игра, которая анализируется методом систематического перебора всех возможных решений. Их гораздо меньше, чем может показаться, до такой степени, что в наиболее простых случаях все это выполнимо вручную. Так, для креста на рис. 23 есть (с точностью до симметрий) только три игровых хода.
Если вы поднимете шашку на пересечении двух ветвей креста, то следующие два хода вынуждены и вы проиграли. Если вы спустили шашку до низа креста, то у вас после этого есть выбор между двумя ходами и в любом случае вы проигрываете. Если вы перемещаете шашку на пересечении двух ветвей креста вправо (или влево), то следующий ход вынужден, а затем у вас есть выбор между тремя ходами, два из которых сразу проигрывают, а оставшийся выигрывает.
Тогда без колебаний составляйте:
– либо рекурсивное решение. У меня есть процедура, которая решает задачу с n шашками. Какова бы ни была начальная конфигурация, для любого возможного хода вы этот ход осуществляете и решаете задачу с n − 1 шашками;
– либо итеративное решение. Оно отличается от предыдущего только необходимостью восстанавливать игру при возвращении назад. Это приводит вас к вопросу о представлении игры. Возможностей много…
Игра 31.
Поскольку рекурсивное решение тащится по всем книгам, я его вам здесь и предлагаю: это избавит вас от поисков…
Нужно перенести диски со стержня номер н (начального) на конечный стержень номер к. Номер запасного стержня x (хранилища) таков, что н, к, x есть перестановка чисел 0, 1, 2, поэтому н + к + x = 3. Номер запасного стержня равен 3 − н − к. Чтобы решить задачу, перенесем n − 1 первых дисков со стержня н на стержень x с помощью Н(n − 1, к, 3 − к − н).
Затем мы переносим последний диск n с н на к, что обозначается
Р(n, н, к).
Эта процедура, которая реализует, например, сообщение
n ИДЕТ С н НА к
Наконец, мы переносим n − 1 первых дисков с запасного стержня на стержень к:
Н(n −1, 3 − н − к, к).
Нужен частный случай, не являющийся рекурсивным. Если диск всего один, то можно сразу перенести его от н к к:
Н(р, н, к) = ЕСЛИ р = 1 ТО Р(1, н, к) ИНАЧЕ Н(р − 1, н, 3 − н − к)
Р(р, н, к)
Н(р − 1, 3 − н − к, к)
КОНЕЦ_ЕСЛИ
Проще некуда. Как же может случиться, что находятся и такие, кому эта процедура внушает опасения? В том ли дело, что они не видят, как на самом деле двигаются шашки? Или дело в том, что они испытывают сомнения в правильности процедуры? Продумайте это решение: если оно составляет для вас задачу, то только потому, что вы не владеете рекурсией, и жаль, что это так…
Число ходов игры легко выводится из этой процедуры. Обозначим через f(p) число ходов, необходимых для игры с p дисками. Из рекурсивной процедуры следует, что
f(1) = 1,
f(p) = 2 * f(p − 1) + 1.
(Почему?) Исходя из этого, вы можете вычислить f(p) (на самом деле g(p) = f(p) + 1 имеет более простой закон построения, чем f(p). Образуйте сначала этот закон, найдите решение, а затем выведите закон для f(p)).
Чтобы доказать свойство, касающееся четности дисков, действуйте по индукции подходу вычислений. Предположите, что это свойство выполняется для Н(р − 1, …). Покажите, что от сюда следует его справедливость и для Н(р, …).
У вас не получается? Вот дополнительная помощь. Начнем с переноса р − 1 дисков на запасной стержень. Пока не передвинут (р − 1)-й диск, нп один диск не кладется непосредственно на диск с номером р, и требуемое свойство выполняется. Рассмотрим момент, когда р − 2 дисков находятся на одном стержне, диски с номерами р − 1 и р – на другом стержне, а третий стержень пуст, Вы перемещаете диск с номером р − 1. Теперь, поскольку нужно переместить первые р − 2 дисков на диск с номером р − 1, то диски будут оказываться на диске с номером р. Если мы помещаем диск с номером q на диск с номером р, то для того, чтобы образовать пирамиду дисков с номерами от q до 1 и иметь возможность переместить диск с номером q + 1, который отправится на диск с номером р − 1. Но требуемое свойство выполняется для р − 1 дисков, и поэтому четность диска q + 1 не может совпадать с четностью р − 1. Следовательно, она совпадает с четностью р. Следовательно, р и q имеют разные четности.
Потренируйтесь в доказательствах такого рода…
Игра 32.
Предыдущее рекурсивное решение имеет ту особенность, что она не включает в ход игры никакого представления этой игры. Если вы хотите представить игру на экране даже символическим образом, вам придется создавать представление игры самому.
Но трудность состоит только в осуществлении видимого представления, потому что нужно учесть все, сказанное выше. Предположим, что нужно выполнить Р(р, н, к). Вы знаете, что нужно осуществить движение, которое вводит в игру диск размера р, покидающий стержень н, с которого он отправляется на стержень к. Это означает, что диск р находится на вершине стержня к, в противном случае его нельзя было бы оттуда взять. Поэтому вы можете не обращать никакого внимания на значение р.
Операция Р(р, н, к) на самом деле следующая: снять диск с вершины стержня н и поместить его на вершину стержня к.
Если представить игру в виде 3 строк с помощью последовательностей чисел, то, таким образом, достаточно снять крайнее правое число со строки н и присоединить его справа к строке к.
Если вы хотите представить стержни вертикально, создайте, кроме того, внутреннее представление с помощью трех цепочек символов и составьте процедуру вывода на экран. Это, как кажется, проще всего. Если вы не любите цепочек символов, используйте три таблицы, но вы не выиграете в легкости.
Игра 33.
Если ваш компьютер допускает рекурсию, заставьте работать рекурсивную процедуру и понаблюдайте за движением дисков. В противном случае выполните вручную рекурсивную процедуру для маленького n (например 4), что поможет вам наглядно увидеть то, что уже доказано: два диска одинаковой четности не могут оказаться друг на друге.
Вы должны заметить, что
– диск с номером 1 перемещается один раз за любые два хода,
– он перемещается циклически, причем всегда в одном направлении, а именно
либо 0 – 1 1 – 2 2 – 0…
либо 0 – 2 2 – 1 1 – 0…
Следующий ход, перемещающий диск с номером 1, полностью определен. Недостаточно проверить это, это нужно доказать. После этого итеративное решение тривиально. Можете ли вы априори определить перемещение диска с номером 1 в зависимости от четности числа дисков?
Можете ли вы сказать что-нибудь о движении остальных дисков?
Пронумеруйте ходы. Диск с номером 1 перемещается в ходах с нечетными номерами. Проверьте, а затем докажите, что диск с номером 2 перемещается в ходах с номерами 2, 6, 10, …, т. е. в ходах, номер которых кратен двум, но не кратен четырем. Обобщите. Исходя отсюда, вы можете сказать, зная номер хода, какой диск будет перемещаться, с какого стержня он уйдет и куда придет.
Красиво, не правда ли?
Игра 34.
Существование четвертого стержня не упрощает стратегию, даже наоборот. Одна из возможностей состоит в том, чтобы перемещать р верхних дисков, используя 4 стержня, затем оставшиеся диски – используя только 3 стержня (поскольку четвертый стержень блокирован башней самых маленьких дисков). Наконец, вы восстанавливаете р маленьких дисков над остальными, используя 4 стержня. Обозначим через
f4(р) – число ходов для перемещения р дисков, используя 4 стержня;
f3(р) – число ходов для перемещения р дисков, используя 3 стержня (известное число, см. игру 31).
Тогда наша стратегия дает
f4(n) = f4(р) + f3(n−p) + f4(р).
Нужно выбрать значение р, которое минимизирует эту сумму.
Первые несколько значений для /4 получить легко:
f4(1) = 1, f4(2) = 3, f4(3) = 5.
В этих случаях на самом деле есть только один способ действовать. Вычислите сначала на руках следующие значения. Воспользуйтесь вашим компьютером, чтобы составить таблицу, дающую последовательные значения для f4(n), вместе с оптимальным значением р для каждого n (оно не всегда однозначно определено. Вы по своему произволу можете выбирать из них наименьшее).
Игра 35.
Итеративная программа для игры с 4 стержнями есть обобщение итеративной программы для игры с 3 стержнями. Это видно по рекурсивной форме. Она не идеально проста…
Это замечание позволит вам перейти к любому числу стержней.
Игра 36.
Нужно снова взять все, что было нами оставлено в игре 23. Предположите, что для некоторого р существует такое значение q, что
SG(p, q) = 0.
Покажите, что в этом случае SG(р, q') = 0 для всех q' < q. Следовательно, если р таково, что SG(р, 1) = 0, то должно существовать некоторое g такое, что SG(р, g) = 0, но SG(р, g + 1) ≠ 0; g – наибольшее из значений q, дающих равенство SG(р, q) = 0.
Нужно построить последовательность pi, gi.
Вы можете показать, что если gi = 1, то pi+1 = pi + 2, в то время как если gi > 1, то pi+1 = pi + 3.
Хороший способ действия состоит в том, чтобы опереться на геометрические рассмотрения. Числа Спрага-Грюнди интересуют нас только с одной стороны– равны они нулю или нет (у нас нет намерения играть несколько игр одновременно, что избавляет нас от вычисления Ним-сумм и, следовательно, от заботы о значениях ненулевых чисел Спрага-Грюнди). Число Спрага-Грюнди равно нулю тогда и только тогда, когда невозможен никакой переход к нулевому числу. Но положение р, q допускает переходы к p − k, для k ≤ 2q. Следовательно, мы получим SG(p, q) = 0 тогда и только тогда, когда
SG(p − k, k) ≠ 0 для всех k от 1 до 2q.
Нарисуйте на плоскости две перпендикулярные оси, p как абсциссу и q как ординату. Обозначьте точки с нулевыми значениями SG.
Рассмотрите те прямые, которые проходят через точки p c SG(p, 1) = 0. Нужно изучить прямые p − k, k, где меняется от 1, т. е. те, которые параллельны биссектрисе второго и четвертого координатного угла и проходят через точку p − 1, 1.
Мы представили отрезок такой прямой для p = 28 (см. рис. 38). Он пересекает точку с нулевым значением на вертикали 21 = 28 − 7. Значит, нужно ограничить число k шестью, задавая g = 3 при p = 28.
Для p = 34 диагональ, проходящая через 33, 1 проходит над всеми отрезками с 0 для p ≠ 0 и пройдет поэтому, пересекая ось q при q = 34. Поэтому нужно ограничить число k тридцатью тремя и, следовательно, взять g = 33 : 2 = 16.
У вас есть также некоторое число таких pi, что диагональ, выходящая из pi − 1, 1, не пересекает никакого отрезка нулей перед осью q, что дает gi = (pi − 1) : 2.
Исходя отсюда, следующие числа p определяются диагоналями, которые перерезают вертикальный отрезок, выходящий из pi так, что p − pi ≤ gi = (pi − 1) : 2. Тогда можно восстановить первоначальную последовательность, несущую нули, вплоть до (pi − 1) : 2.
Теперь вы легко сможете доказать, что интересующая нас последовательность pi есть последовательность чисел Фибоначчи.
Составьте программу, перечисляющую pi, gi.
6. Комбинаторные задачи
Головоломка 20. Полное решение.
Поскольку эта задача всюду решена, предложим также и здесь решение: это избавит вас от поисков других решений; и, кроме того, я буду уверен, что вы посмотрели на все существенные места этой задачи. Есть книги, которые… Но это – совсем другая история.
Заметим сначала, что два ферзя не могут находиться на одной строке (горизонтали) и, поскольку нужно поставить 8 ферзей на 8 строк, то на каждой строке есть ферзь. Поэтому я буду говорить «ферзь k» вместо «ферзь, стоящий на строке k».
Точно также, есть только один ферзь в каждом столбце. Но совершенно ясно, что я не могу управлять в одно и то же время размещением и по строкам и по столбцам – собственно, это от меня в задаче и требуется. Я собираюсь поэтому размещать ферзей на последовательных строках, начиная сверху.
Чтобы начать, я помещаю ферзя в первый столбец на первой строке. Тогда мне остается решить меньшую задачу; разместить 7 ферзей на 7 последних строках шахматной доски, учитывая, что ферзь стоит на первом поле первой строки. Я получу тогда все решения с ферзем 1 в столбце 1. Затем я поставлю ферзя 1 в столбец 2 и разрешу задачу с 7 ферзями, и т. д. – 8 раз.
Обобщим. Мы собираемся решить частную, но нужную задачу: полагая, что уже есть ферзи, правильно размещенные на строках от 1 до k − 1, и зная их положение, найти все возможные решения, размещая подходящим образом ферзей с номерами от k до 8. Обозначим программу, которая это делает, через HR(k)[24]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. Нужна инициализация, которая бы это открыто провозглашала:
ПРОГРАММА: 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 в СБ), освобождая ферзей, пока не окажется возможным передвинуть какого-то ферзя правее (цикл СБ, И, СБ из И). Как только оказывается возможным переместить ферзя правее, он туда перемещается и возобновляется спуск.
Учитывая все это, мы видим, что наша стратегия достаточно проста и выглядит естественной, как только мы к ней привыкаем: ведь привычка – вторая натура, не так ли?
Существенное замечание: я говорю о программе так, как будто она закончена. Но еще ничего завершенного нет: вы никак не можете ввести эту программу в машину, потому что все записано символически. Как вы узнаете, является ли поле свободным? Что это такое – занять поле? Такая ситуация не является исключительной: мы можем обсуждать стратегию программы, совсем не обсуждая представление данных. Две вещи полностью разделены;
– алгоритм или стратегия, которой мы следуем при проведении вычислений;
– структуры данных, или способ представления элементов вычислений посредством основных типов, имеющихся в распоряжении используемого языка (в основном: числа, символы, таблицы или массивы чисел, цепочки символов).
Это – один из фундаментальных принципов программирования: стараться отложить на как можно более позднее время любое решение относительно выбора наиболее удобного представления данных. Рассмотрите сначала стратегию, которой вы следуете, используя символические формулы, которые вы впоследствии разовьете. Есть только две возможности:
– либо, как в рассматриваемом случае, вы приходите к цели. Как только этот первый этап пройден, вы спокойно обсуждаете представление данных;
– либо вы не в состоянии добраться до цели вследствие некоторого влияния структуры данных на стратегию. Такое бывает. Когда вы не можете продвинуться дальше в разработке стратегии, тогда начинайте с выбора представления данных, в котором вам послужит все то, что вы уже сделали к этому времени, и вы учтете то, что вас остановило.
Программирование всегда должно идти нисходящим путем. Сначала – алгоритм или стратегия. Потом – структура данных.
Посмотрим, какие структуры данных возможны в нашей задаче. Первая, наиболее естественная идея: я представляю шахматную доску с помощью квадратной таблицы с 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. Ну, уж теперь-то я сказал вам достаточно…
Я не знаю простого решения для симметрии относительно диагонали. Если вы найдете такое решение, напишите мне…
Головоломка 21.
Я не вижу способа взяться за эту задачу, существенно отличного от предыдущего. Нужно найти нижнюю границу для числа ферзей. На пустой шахматной доске ферзь может блокировать 28 полей. Следовательно, нужно по крайней мере 3 ферзя, чтобы блокировать доску. Их нужно не больше 7: если вы уже пытались вручную поставить 8 ферзей, то вы должны были убедиться, что шахматная доска часто блокируется до того, как мы смогли поставить восьмого ферзя. Точно так же вероятно, что 6 ферзей должно хватить. Поэтому нужно исследовать отрезок от 3 до 6 ферзей.
