Тетромино. Алгоритм поиска.

Модератор: SergR

Аватара пользователя
PROLD
Старожил
Сообщения: 1704
Зарегистрирован: 07 мар 2016, 11:18
Откуда: Россия
Интересы: Puzzle
Пол: Не выбран
Страна: Russia

Тетромино. Алгоритм поиска.

Сообщение PROLD » 06 июн 2017, 21:25

Решил обнародовать задачу, к которой пока не могу подступиться.
Суть в следующем:
- имеется восемь элементов тетро-кубиков (исчерпывающий комплект).
- конструкция, которую надо замостить этим набором представляет из себя два слоя, нижний из которых-квадрат 5*5 -
полностью должен быть заполнен и верхний - оставшиеся семь единичных кубиков.
- расположение семи кубиков верхнего слоя (назовем его - "узор") в принципе может быть каким угодно, но некоторые расположения дают возможность замостить указанным набором, а некоторые - нет.
Программно выявить возможность (невозможность) замощения , естественно, просто.

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

Screenshot_15.png
У вас нет необходимых прав для просмотра вложений в этом сообщении.

#1
Влад
Ветеран
Сообщения: 791
Зарегистрирован: 21 май 2015, 09:12
Откуда: Черкасская обл.
Интересы: Головоломки, фото, шахматы
Пол: Мужской
Страна: Ukraine
Возраст: 76

Re: Тетромино. Алгоритм поиска.

Сообщение Влад » 07 июн 2017, 22:51

Программно выявить возможность (невозможность) замощения , естественно, просто.

Действительно, если известна фигура и есть программа, то зачем изобретать велосипед? Ведь программа очень быстро сообщает все решения. А чтобы усложнить себе жизнь достаточно добавить дополнительные условия. Я, например, искал только симметричные фигуры.Даже при этом ограничении программа находит по несколько решений. Вот кое что из найденного.
Сим вар.jpg
У вас нет необходимых прав для просмотра вложений в этом сообщении.

#2
Аватара пользователя
PROLD
Старожил
Сообщения: 1704
Зарегистрирован: 07 мар 2016, 11:18
Откуда: Россия
Интересы: Puzzle
Пол: Не выбран
Страна: Russia

Re: Тетромино. Алгоритм поиска.

Сообщение PROLD » 08 июн 2017, 01:47

Феноменально!

#3

Вернуться в «Песочница»

Кто сейчас на конференции

Сейчас этот форум просматривают: CommonCrawl [Bot] и 0 гостей