28
ЭВМ
опровергает
Великому математику Л. Эйлеру принадлежит следующая задача:
Обойти конем все клетки шахматной доски, повышав в каждой клеткеровно по одному разу.
В 1823 году Варисдорф в брошюре «Простейшее и наиболее общее решение задачи о хode коня» предложил следующей правила обхода доски:
На каждом ходу ставка коня на маску клетку, из которой можно совершить наименьшее число ходов на еще не проиденные клетки. Если маски клеток несколько, разрешается выбирать любую из них.
Отметим, что правило Варисдорфа не является алгоритмом, поскольку оно не всегда однозначно указывает следующий ход коня (см. вторую фразу правила).
Например, если конь начинает свое движение с поля d4, правила Варисдорфа позволяет ему пойти первым ходом на любое из полей b3, b5, c2, e2 (рис. 1). (Оdnako, если конь начинает свое движение с поля c2, то даже на первом ходу правила Варисдорфа однозначно указывает ему, куда пойти — на поле a1!)
Варисдорф высказал утверждение: с какого бы поля конь ни начинаал свое движение, любой путь, удовлетворяющий его правила, в конце концов приведет к полному обходу доски (т. е. к решению задачи Эйлера). До недавнего времени не было известно, справедливо ли это утверждение. Еще в 1971 году Е. Я. Гик писал в «Кванте» (№ 9, с. 53), что утверждение Варисдорфа «на практике всегда оправдывается…, хотя оно и не подтверждено теоретически».
Для ЭВМ «Проминь-2» была составлена программа перечисления некоторого множества путей коня. Первый контрирмер был построен менее чем за 1 минуту. Перебрав 6464 путей, ЭВМ получила контрирмеры
Рис. 1.
Рис. 2.