??? Игра 36. Спички Бергсона.

Эта игра была предложена выше (игра 23). Тогда требовалось только дать компьютеру указание, что он должен будет сделать, чтобы выиграть наверняка, если исходить из 50 спичек. Теперь нужно заглянуть глубже и изучить выигрывающую стратегию в полной общности.

Как и во многих играх, есть ситуации, которые позволяют игроку выиграть наверняка (если он их знает), и другие ситуации, исходя из которых выиграть невозможно. Пусть П обозначает ситуацию, благоприятную первому игроку (или предыдущему. П — это первая буква слова «позитивный», как это заметил Роуэ Болл [BAL]). Эта ситуация хороша для меня, если это такая ситуация, которой я достигаю после своего хода. Ситуация Н благоприятна второму, «новому», игроку (неблагоприятна первому, негативна). Она хороша для меня, если это — та ситуация, которую я застаю в момент своей игры. Вся моя стратегия есть переход от ситуации Н в ситуацию П.

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

— из ситуации Н всегда можно достичь ситуации П,

— из ситуации П можно достичь только ситуаций Н,

— выигрывающая ситуация есть ситуация П.

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

В игре в спички Бергсона ситуация характеризуется двумя целыми числами p, q:

p — число спичек, оставшихся в куче;

q — число спичек, взятых на предыдущем шаге. Тогда можно взять от 1 до 2q спичек.

Ситуация 0, q — выигрывающая для любого q.

Ситуации 1, q и 2, q суть ситуации Н. Исходя из них,; можно взять последнюю спичку. Ситуация 3, 1 есть П: исходя из нее, нельзя получить ничего, кроме 2, 1 и 1, 2, и обе эти ситуации относятся к классу Н.

Составьте программу, перечисляющую положения П вплоть до некоторого уровня.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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