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

Понаблюдайте за результатами. Попытайтесь угнать их свойства и, если вам хватит смелости, проверить их.

Вы наверняка знаете числа Фибоначчи: они определяются рекуррентным соотношением

f(n) = f(n − 1) + f(n − 2)

и единичными значениями двух первых чисел. Какой черт их сюда занес…

6. Комбинаторные задачи

Я объединил здесь различные головоломки, решение которых для компьютера в принципе нетрудно. Есть конечное число возможных случаев. Мы испытываем их все и выбираем наилучший. К этой категории относится и чемпион мира по шахматам: конечное число шахматных фигур, конечное число правил, конечное число ходов…

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

Головоломка 20. Восемь ферзей.

Возьмите на заметку: это самая простая головоломка подобного типа. Поставить на шахматной доске 8 ферзей так, чтобы они друг другу не угрожали. Ферзь может взять все, что находится в этой же строке, что и он, в том же столбце или на той же диагонали. Представим, как обычно, шахматную доску квадратной таблицей полей, среди которых свободные поля помечены точками, а ферзи помечены крестиками (×).

На рис. 28 представлены две попытки решения. На левой доске поставлены 4 ферзя. Все поля строки 6 ими уже блокированы. Продолжать дальше бесполезно. На правой доске мы сумели поставить 7 ферзей, но восьмая строка блокирована.

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

Деликатный вопрос связан с представлением шахматной доски. Но и возможности этого выбора также обсуждаются в известных книгах.. Что же тогда остается найти?

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

Поэтому пытайтесь искать только основные решения, исходя ив которых и используя симметрии шахматной доски, можно найти все остальные решения…

В этом примере вам не следует бояться сложности. Даже самые плохие программы будут все еще достаточно быстры…

?** Головоломка 21. X ферзей.

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

Каково наименьшее число ферзей, необходимых для блокирования шахматной доски, так, чтобы не было возможности поставить ни одной фигуры ни на одно поле, чтобы один из уже стоящих ферзей не мог эту фигуру взять?

Так как я вам не задал x, то вам нужно пытаться заставить x либо расти, либо уменьшаться. Впрочем, в этой задаче наши дела идут хуже, чем с 8 ферзями. В предыдущей задаче мы знали, что в каждой строке и каждом столбце обязательно должен быть ферзь. Если ферзей меньше 8, то это уже неверно.

* Головоломка 22. Домино.

Маленькая прелестная головоломна, совсем не трудная. Она была предложена на испытании на проницательность на конкурсе организации АФСЕТ по программированию в 1981 году.

Берутся 7 костяшек из одного набора домино. Напомним, что эти шашки сделаны из двух частей, на каждой из которых либо ничего не написано (чистая сторона), либо очки в числе от 1 до 6,

Задача состоит в том, чтобы образовать из этих 7 костей все возможные цепи, состыковывая костяшки домино частями с равными количествами точек. Нет никакой уверенности, что такая цепь существует.

Не ведите себя так, как некоторые из соревнующихся на этом конкурсе. Я тогда входил в жюри. Мы должны были оценивать работы соревнующихся. Если бы я принимал решения единолично, я потребовал бы, чтобы мне были представлены тексты программ, и я бы судил по самим произведениям. Но другие члены жюри нашли более длинный и более сложный метод, Они приготовили специальные тесты. Они должны были быть испытаны на программах соревнующихся, и нужно было подсчитать число правильных ответов, чтобы расклассифицировать соревнующихся. Новое обсуждение: я выдвигаю оценку, что и один-единственный неверный ответ выражает ошибочность программы и, следовательно, выводит ее из конкурса. В конце концов было решено, что так и будем делать. Все программы, содержащие ошибку, будут рассматриваться как неверные, Если две команды получат одинаково верные ответы, то мы еще раз детально изучим полученные результаты, стараясь разгадать природу ошибки при переходе к данному тесту от уже удавшихся, чтобы отдать одному из них предпочтение. Вот нам и досталось: один ив соревнующихся, думая, что с удавшимися тестами это согласуется, пытался упростить программу для домино. Он сказал себе, что вне всякого сомнения, будут даны кости, из которых никаких цепей ставить нельзя. Его программа читала последовательность костей домино и сообщала НЕВОЗМОЖНО без каких-либо других вычислений. Если бы я не настаивал на своем так решительно, то он был бы не хуже других…

Не поступайте так. Эта задача при всем том нетрудная… Рис. 29 дает пример цепи.

* Головоломка 23. Последовательность 0—1—4—6.

Это головоломка, на которую я натолкнулся, работая над своей диссертацией на ученую степень по физике. Я занимался сетями антенн для радиоастрономии. Сеть антенн состоит из основания, на котором по одной линии размещены отдельные антенны, доставляющие информацию о наблюдаемых нами звездах. Каждая нара антенн дает информацию о некоторой величине, пропорциональной расстоянию между двумя антеннами этой пары. Нас интересуют значения этой величины, образующие арифметическую прогрессию. Таким образом, нужно было располагать антенны таким образом, чтобы расстояния между равными парами образовывали арифметическую прогрессию. Я предложил систему из 4 антенн, расположенных на прямой в точках с абсциссами 0 1 4 6.

Тогда получаемые из них 6 различных пар приводят к расстояниям между антеннами, пропорциональным следующим числам:

0—1 1

4—6 2

1—4 3

0—4 4

1—6 5

0—6 6

Можно сформулировать задачу по-другому. Нужно найти последовательность натуральных чисел a1, a2, …, an — последовательность, которую можно предполагать возрастающей — такую, чтобы попарные разности членов этой последовательности aj − ai (j > i) были попарно различны и образовывали последовательность всех целых чисел от 1 до n(n − 1)/2.

Это — еще и проблема трансформатора (см. рис. 30), Если включить во вторичную обмотку 4 выхода так, чтобы число витков между первым и другими выходами находилось в отношениях 1, 4 и 6, то можно получить 6 напряжений на выходе, образующих арифметическую прогрессию.

Опустим другие физические задачи, порождающие такие последовательности. Четырехчленная последовательность 0—1—4—6, по-видимому, является наибольшей последовательностью, обладающей свойством порождать последовательность первых целых чисел, не пропуская и не повторяя дважды ни одного из них, при попарном вычитании членов этой последовательности.

Так, для 5 целых можно образовать 10 разностей. Поэтому крайние члены должны быть a1 = 0, a5 = 10. Чтобы получить в виде разности 9 из двух членов последовательности, нужно, чтобы либо было a2 = 1, и тогда a5 − a2 = 9, либо a4 = 9. Эти два решения легко получаются одно из другого операцией симметрии, Поэтому положим a2 = 1.

К этому моменту мы получили уже a1 = 0, a2 = 1, a5 = 10. Чтобы получить разность, равную 8, нужно взять

— либо a3 = 2, но тогда разность, равная 1, получается дважды:

a3 − a2 = a2 − a1

— либо a4 = 8,

— либо a4 = 9, но тогда снова дублируется разность 1. Следовательно, a1 = 0, a2 = 1, a4 = 8, a5 = 10.

Достаточно теперь пересмотреть одно за другим возможные значения а3 и удостовериться, что каждое ив них дублирует какую-то разность.

Для a3, равного 2, дублируется разность 1:

3 2

4 4

5 5

6 2

7 1

Таким образом, нет последовательности из 5 целых, попарные разности которых порождают 10 первых натуральных чисел. Допустим теперь возможность повторений в последовательности разностей. Можно ли с помощью 5 членов породить — с помощью их разностей — 9 первых натуральных чисел?