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

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

Эта программа замечательно иллюстрирует то, что называется «проблемой остановки». Существуют простейшие программы, относительно которых нет уверенности, что они остановятся…

Теперь, когда вы уже познакомились с этой последовательностью, получите предмет головоломки. Заметим сначала, что если p нечетно, то мы переходим к Зp + 1 — числу, отличному от 1. Очевидно, что непосредственно предшествующий шаг есть деление на 2. Поэтому можно изменить правило построения последовательности описанным ниже образом: следующее за числом p равно

p/2, если p четно,

(Зp + 1)/2, если p нечетно,

Это вычеркивает некоторые члены предыдущей последовательности, не меняя проблемы остановки:

7 11 17 26 13 90 10 5 8 4 2 1

Вы можете пойти еще дальше в том же направлении, объединяя вместе все последовательные шаги, действующие по правилу (Зp + 1)/2, и все следующие за ними шаги, состоящие в делении на два. Вы получите два новых правила перехода, гораздо более уплотненные. Свяжите их и пустите в ход. Для числа 7 вы должны без задержки получить последовательность

7 13 5 1

Это позволяет рассматривать обобщения задачи. Пусть k — нечетное число. Возьмем в качестве правил перехода следующие:

p/2, если p четно,

k * p + k ? 2, если p нечетно.

Возможно уплотнение, аналогичное предыдущему. Для k = 5 следующее за числом 3 есть 3, и существуют исходные точки, для которых программа не останавливается. Для k = 7 она идет точно так же. Так что проблема остановки связана со свойством числа k. Я бы здесь… Впрочем, мало ли чего я хочу!

Зашифрованные операции

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

Головоломка 8. SEND MORE MONEY.[4]

Это — лаконичная телеграмма английского студента своему отцу. История умалчивает о том, как отец это принял и были ли отправлены деньги…

SEND + MORE = MONEY

Программа очень легкая. Время вычисления короткое. Едва ли это головоломка. Как раз для тренировки…

Головоломка 9. HELP THE YOUNG.[5]

Конечно, конечно. Почему бы не послать им еще денег? Та же задача:

HELP + THE = YOUNG

Отметим разницу с предыдущей задачей. Предыдущая использовала не все цифры от 0 до 9. В этой участвуют все. Можете ли вы воспользоваться этим?

DEVOIR, LECON, ELEVE.[6]

Есть аналогичные зашифрованные сложения по-французски. Например, такая:

ELEVE + LECON = DEVOIR

? Головоломка 10. Зашифрованное умножение.

Довольно сложений, это становится скучным. Вот зашифрованное умножение:

ABCDE * 9 = FGHIJ

Здесь 10 букв представляют 10 различных цифр, так что одна из них равна 9. Можно сразу кое-что сказать о возможных значениях букв, но чтобы получить решение, придется идти буквально ощупью. Столько же придется искать и компьютеру.

?* Головоломка 11. Забавное число.

Число 123456789 обладает забавными свойствами:

123456789 * 2 = 246913578

Как и исходное, удвоенное число образовано всеми девятью цифрами, кроме 0.

123456789 * 4 = 493827156

Результат снова образован девятью цифрами, отличными от 0.

123456789 * 5 = 617283945

По-прежнему 9 цифр.

123456789 * 7 = 864197523

Опять 9 цифр, и это еще не все.

123456789 * 8 = 987654312

Но это не работает ни для 3, ни для 6. Это не может работать и для 9, потому что в результате больше 9 цифр,

Тем не менее есть много чисел, образованных всеми 9 цифрами (кроме 0), которые после умножения на 3 дают результат, образованный теми же девятью цифрами. Можете ли вы дать список всех таких чисел, оканчивающихся на 9? И также список тех, которые кончаются на 3?

Можно ли распространить использованный метод на случай умножения на 6?

Доказательства теорем

Компьютер можно использовать для доказательства теорем. Это — трудная задача искусственного интеллекта. Мы снабжаем компьютер правилами вывода, даем формулировку того, что требуется доказать, и исходные аксиомы. Компьютер пытается найти последовательность правил вывода, которые могут привести от исходных данных к требуемым рёзультатам.

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

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