Возможно, не до конца понял, но, по-моему, 3 изначальных правила (все клетки нашего игрового поля будут покрыты хотя бы одной фигурой, исключить пересечения фигур, кажная фигура может присутствовать на игровом поле только один раз) избыточны: можно, например, 2 и 3 только оставить. Или 1 и 3.

RedStone Nov 20 2017 at 12:14

Откровенно говоря маловато формул. Клоз — дизъюнкт.

andy_p Nov 20 2017 at 12:20

Нет, недостаточно. Фигура (загогулина) появляется много раз в виде сдвигов, поворотов и отражений. Поэтому, чтобы исключить две или более копии, надо все условия. Иначе, например, можно все поле заполнить фигурой 2х2.

AntonSt Nov 20 2017 at 16:35

Но ведь этот случай покрывается правилом 3? А правила 1 и 2 становятся эквивалентны друг другу, если удовлетворено 3. Разве нет?

andy_p Nov 20 2017 at 18:40

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

GlukKazan Nov 20 2017 at 18:53

Думаю, AntonSt имеет в виду, что если на поле ровно по одному варианту каждой фигуры (3), они не пересекаются (2) и не выходят за границы поля (исходя из особенностей их построения), то они должны покрыть ровно все клетки (поскольку количество покрываемых ими клеток в точности равно размеру поля). Аналогично можно прийти от (1,3) к (2) — фигуры просто не смогут пересекаться, поскольку лишних клеток для образования пересечений у них не останется. Чем-то напоминает принцип Дирихле.

andy_p Nov 20 2017 at 20:11

Хмм… Пожалуй соглашусь. Надо будет попробовать.

andy_p Nov 20 2017 at 21:28

Попробовал. Результаты следующие на моем компьютере:

processor: 0
vendor_id: GenuineIntel
cpu family: 6
model: 42
model name: Intel® Core(TM) i7-2600K CPU @ 3.40GHz

Методика, описанная в статье:
real 0m9.585s
user 0m9.548s
sys 0m0.024s

Если убрать ограничение на заполнение каждой клетки (1) — не работает (выдает пустое поле).

Если убрать условие пересечения (2), работает очень долго, не смог дождаться результата.

andy_p Nov 20 2017 at 21:47

Понятно, почему не работает вариант при исключении заполнения каждой клетки (1) — булева функция выполняется для 2 и 3 если нет ни одной загогулины на поле.
Чтобы это опять работало, надо ставить дополнительное условие, чтобы на поле была хотя бы одна фигура для каждого типа.

robo2k Nov 20 2017 at 12:44

Не очень понял, 1364 это количество уникальных вариантов решения?

andy_p Nov 20 2017 at 13:24

Да.

vesper-bot Nov 21 2017 at 16:14

Судя по формулировке задачи для minisat, 1364 это с учетом поворотов и отражений. То есть поворот решения — другое решение. Правильно?

vesper-bot Nov 21 2017 at 16:20

Упс, там было написано, что сравнение было отдельно. Сорри.

Tachyon Nov 23 2017 at 11:12

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

vassabi Nov 23 2017 at 11:18

пентамино ручной работы — это не тот масштаб и цена.
А так — нарезали простых брусков, потом склеили их в фигурки.

GlukKazan Nov 23 2017 at 21:53

Даже если говорить о ручной работе… Когда я в детстве делал кубики сома, я просто взял 27 детских кубиков без наклеек (как раз продавался такой набор) и склеил их эпоксидкой. Поверьте, это проще чем вырезать фигурные детали. На кубиках были выжжены какие-то буквы, но с ними даже прикольнее. Когда через пять лет пара кубиков расклеилась, не стал морочиться с эпоксидкой. Просто прибил их гвоздями. Картинка на КДПВ, это головоломка к журналу «Занимательные головоломки». Они на этом типа бизнес делают. Серьёзно хотите, убедить их в том, что делать надо качественнее (и дороже)?

GlukKazan Nov 28 2017 at 20:35

Вот так это выглядит

В сборе

Show the best of all time