Классификация червяков
После выхода Ломтика с червяками и
колонки про них на Информационном Буме с просьбой
попытаться посчитать варианты и как-то их классифицировать получил письмо от
Юрия Тилина. Юрий придумал алгоритм перебора вариантов и выложил в своем блоге,
посмотрите.
Чуть изменив методику Тилина и используя его картинки (спасибо!) я пришел почти
к тому же результату. Поясняю методику. В самой левой колонке учтены все
варианты с замыканием на одно ребро более одного раза. Во втором столбце все
варианты с одним замыканием на одном ребре.
В третьей колонке все варианты с наличием соединения ближайших точек смежных
ребер исключая варианты, попавшие в первые две колонки.
В четвертой колонке все варианты соединения не ближайших точек смежных ребер
исключая варианты, попавшие в первые три колонки. Это самый сложный перебор, так
как много вариантов, возможны ошибки. Ну и в пятой - соединения противоположных
ребер.
По сравнению с классификацией Тилина добавлен вариант - в третьем столбце и
пятом ряду. Поэтому общее количество вариантов 30, а не 29 как у Юрия. Напомню,
что варианты, получаемые поворотом и отражением не рассматриваются, иначе
набирается 105 способов соединений - проверьте!
Остается просьба придумать характеристическое число, определяющее
единственным образом соединения в квадрате - пока не получается. |