Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?work=124 Дата изменения: Fri May 5 15:25:32 2006 Дата индексирования: Tue Oct 2 02:32:18 2012 Кодировка: koi8-r Поисковые слова: extremely red object

Щепин Никита ученик 11М класса школы 79 г. Москвы


О раскладках кубиков на плоскости



Проблема Арнольда.

Данная программа возникла в связи с проблемой Арнольда [1] об отображениях

квадрата на куб. «Непрерывная» проблема Арнольда имеет дискретный аналог
[2].

Предположим, что квадрат и куб разбиты на одинаковое число n равных кубиков
и квадратиков соответственно.

Существует ли такое взаимно-однозначное соответствие между квадратиками и
кубиками, чтобы соседним квадратикам соответствовали соседние кубики?

Назовем сформулированную выше задачу n-элементной проблемой Арнольда.

Доказано [2], что положительное решение n-элементной проблемы Арнольда при
сколь угодно большом n влечет положительное решение исходной «непрерывной»
проблемы Арнольда.

Число n фигурирующее в проблеме Арнольда должно быть одновременно кубом и
квадратом. Наименьшим, большим единицы, кубо-квадратом является 64. И 64-
элементная проблема Арнольда достаточно сложна. Предлагаемая программа
представляет собой инструмент исследований этой проблемы для 64-элементных
разбиений.

Результаты.

Программа позволяет исследовать два варианта сформулированной задачи. В
первом случае, когда параметр программы «число соседей» принимает значение
4, соседними считаются клетки имеющие общую сторону, то есть лежащие или в
одном ряду или в одной строке (клетки соседние по диагонали соседними не
считаются). Во втором случае, соответствующем значению 8 параметра «число
соседей», соседними считаются клетки имеющие хотя бы общую точку. Кубики
считаются соседними, если они имеют непустое пересечение.

С помощью данной программы во-первых удалось найти несколько решений 64-
элементной задачи Арнольда для случая 4-соседства, а во-вторых убедиться в
том, что в варианте 8-соседства эта задача решений не имеет.

Программа может быть использована в качестве игры-головоломки. Построить
хотя бы одно решение описанной задачи - задача по уровню сложности близкая
к «кубику Рубика». Программа всячески помогает в этом.

Методы.

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

Программа может просчитывать длинные цепочки ходов и рекомендовать на
основе своих расчетов лучшие ходы в данной позиции. Так ходов за 20 до
конца партии (для 4-соседства) программа за несколько минут счета уже может
точно определить выигрывается ли данная позиция. В случае положительного
ответа вы можете выиграть партию просто следуя рекомендациям программы.
Если же программа обнаруживает проигрыш, то это означает, что позиция
действительно проигрышная.

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

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

В режиме «оценка позиции» программа рассматривает все предпочтительные
цепочки ходов, длина которых определяется редактируемым параметром «глубина
просчета» и оценивает возникающие позиции.

Оценка позиции представляет собой произведение двух функций, первая из
которых представляет собой среднее геометрическое числа ходов на свободную
клетку в данной позиции, а вторая - среднее геометрическое числа соседей у
непоставленных на доску «кубиков». Эта оценка хорошо себя зарекомендовала.
Выбирая ход с максимальной оценкой при глубине просчета около 10, вы редко
ошибетесь.

Помимо оценок, программа помогает игроку меняющейся раскраской кубиков и
квадратиков. Раскраска у непоставленных на доску кубиков соответствует
количеству имеющихся у них соседей. А раскраска свободных квадратиков
сигнализирует количество возможных ходов на них. В первую очередь нужно
ходить теми кубиками, у которых осталось мало соседей и ходить лучше на те
поля, где меньше вариантов хода. Меньше вариантов - меньше шансов
ошибиться.



Перспективы

Следующим после 64 кубо-квадратом является 3^6=729. Для решения 729-
элементной проблемы Арнольда видимо потребуется разработка эвристик
позволяющих перейти от полного перебора предпочтительных цепочек данной
длины к частичному.




Литература

1. В. И. Арнольд, «Задачи Арнольда», Фазис, Москва, 2000, (проблема 1988-
5)
2. Е. В. Щепин, "On Holder mappings of cubes",
http//:genesis.mi.ras.ru/~scepin