Программирование игр и головоломок

Пансион Киркмана — это колледж для девушек из высшего общества. Надзирательницей там — мисс Фармер. Каждую среду после полудня она сопровождает класс на прогулку. В своей нарядной униформе, в соломенных шляпках они медленно вышагивают по трое в три ряда. Мисс Фармер несговорчива: «Я не хочу маленьких компаний; вы должны располагаться так, чтобы не оказаться с той же подругой в вашем ряду до тех пор, пока вы не проведете этих прогулок со всеми остальными». На это наши девушки заявили, что поступать так очень трудно. Поэтому мисс Фармер решила сама организовать ряды. Для начала она веяла класс с 9 ученицами. Ей удалось быстро организовать ряды. У каждой ученицы было 8 подружек, и она должна была находиться с двумя новыми подружками каждую неделю, так что мисс Фармер предусмотрела цикл в 4 недели.

Затем мисс Фармер был поручен класс с 15 ученицами. Поэтому было необходимо ввести цикл в 7 недель для того, чтобы каждая ученица была за это время в одном ряду с 14 остальными. Тогда мисс Фармер поняла, в какое ужасное предприятие она оказалась вовлеченной.

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

Эта задача принадлежит Т. П. Киркману и была впервые опубликована в Lady’s and Gentleman’s Diary за 1850 год. Для ее решения нужно пролить немало чернил, и вы можете рассмотреть значения, отличные от 9 и 15. Но выглядит вполне правдоподобным, что 15 — патологическое число, и Роуз Болл [BAL] предложил геометрический подход к решению, если число девочек не равно 15. Может быть, подход с точки зрения информатики позволит вам получить в этой задаче новые результаты…

*** Головоломка 26. Пентамино.

Домино, пентамино: очевидная игра слов, заставляющая перейти от шашек с двумя квадратами, к шашкам с 5 квадрата. Вот двенадцать возможных шашек, получаемых объединением 5 квадратов равной площади.

Все они приведены на рис. 31. Эти двенадцать шашек, каждая из которых имеет площадь 5, могут быть собраны в прямоугольник с площадью 60. Есть много решений для прямоугольника 6 x 10, а также 5 x 12. Меньше решений для прямоугольника 4 x 15 и только два для прямоугольника 3 x 20, если, конечно, не различать решения, отличающиеся только симметрией. Можете ли вы найти их за разумное время на вашем компьютере, проверив, что их действительно именно 2?

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

* Головоломка 27. Песенка почти спета.

Знаменитая игра Армана Жаммо уже была упомянута выше (игра 12). Но сейчас мы еще не описываем ее полностью; она довольно трудна для программирования. Вот другая форма, которую проще реализовать и которая еще не лишена интереса. Я верю также, что для любителей математических развлечений здесь есть что делать.

Возьмем случайным образом p двузначных чисел. Возьмем случайным образом также двузначное число s. Соединим эти p чисел между собой сложениями или вычитаниями. Все числа должны быть использованы. Можно ли таким образом получить число s?

При последовательных испытаниях компьютер будет работать быстро. Тогда вы можете попытаться увидеть, что происходит, когда мы заставляем меняться p. Если у вас мало чисел, то у вас и мало шансов получить Если вы берете много чисел (большое p), то, поскольку вы обязаны использовать их все, то у вас снова мало шансов прийти к цели. Мне кажется, что наиболее благоприятны значения p около 8 или 9. Но я не осмеливаюсь гарантировать этого полностью. Нужно быть уверенным в генераторе случайных чисел. Получаете ли вы тот же результат? Я не пытался получить его математическим рассуждением. Может быть, я и неправ. Если я действительно неправ, дайте мне знать об этом!

*** Головоломка 28. Песенка спета.

На этот раз дело идет именно об игре Армана Жаммо. Вам надлежит гадать вашему компьютеру шесть шашек, взятых среди 24; а именно, в набор входят:

по два раза — шашки от 1 до 10,

один раз — шашки 25, 50, 75, 100.

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

Если число n получить нельзя, то телевизионная игра допускает и числа, близкие к n, и тот, чье число ближе всего к n, и становится победителем.

Теоретически эта программа не должна быть трудной. Есть ограниченное число возможных комбинаций: