добрый день!

задача практическая.

есть такие блоки


углы на блоках маркируются при производстве. суть маркировки: соединять можно только углы с разными обозначениями. 

например так можно


а так нельзя



из этих блоков выкладываются структуры. например
 

блоки в структуре можно проворачивать, чтобы добиться корректного соединения в углах согласно маркировке.

блок А - просто квадрат,  переходит сам в себя при повороте на 90.
блок B - квадрат с линией посредине, переходит сам в себя при повороте на 180.
блок С - квадрат с линией по краю, его нельзя проворачивать.

теперь сама задача. задана структура (пример - см большую картинку выше). на ней указано расположение блоков A и расположение и ориентация блоков B и C. Нужно определить, возможно ли (и как именно) провернуть блоки A и B так, чтобы в каждой точке соединения углов оказались углы с разной маркировкой.

вот пример структуры, для которой это сделать невозможно


может у кого-то есть идея, в какую сторону копать?

Не вижу особой проблемы. Задачу вполне может решить рекурсивная процедура присоединения к текущему промежуточному набору очередной плитки (при этом порядок заполнения должен определяться однозначно). На каждом шаге проверяется, можно ли в очередное место присоединить очередную плитку (одним или несколькими способами), если такая возможность имеется, то каждое полученное состояние передаётся на следующий шаг рекурсии для присоединения очередной плитки.
Максимальная вложенность алгоритма получается равной количеству плиток, а количество допустимых вариантов на каждом шаге - от нуля до 3. Если ты не собираешься мостить пустыню, то есть шанс дождаться окончания процесса.

Добавлено @ 15:23
PS. В начальном состоянии можно сразу разместить блоки типа С и организовать их "обход" при выборе очередной плитки для заполнения. Наиболее просто это, наверное, сделать предрасчитанным массивом порядка заполнения, но можно и запрограммировать. Опять же для снижения количества просчитываемых вариантов наиболее разумно на начальных шагах класть плитки возле плиток типа С, и по возможности пораньше переходить у плиткам типа В и отдавать предпочтение плиткам, имеющим максимальное количество уже размещённых соседних. 

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

А задача по-любому переборная. Просто надо максимально оптимизировать её выполнение, уже на первых шагах просчёта организовав максимальное "отсечение" невалидных вариантов.

Добавлено через 2 минуты и 29 секунд
Каков максимальный ожидаемый размер поля для заполнения в плитках и количество на нём плиток различного типа?

2000 x 2000 блоков максимум. содержимое структуры можно рассматривать как случайные данные.

4кк блоков? мощненько... рекурсией тут делать нечего - это точно. Думаю, придётся тебе придумывать что-то типа волнового алгоритма с дополнительной валидацией. И за вменяемое время оно будет работать только в случае, если блоки (или агломераты таких блоков) типов В и С достаточно редки - т.е. количество альтернативных решений достаточно велико.

А задача всё равно имхо переборная.

Добавлено через 11 минут и 30 секунд
С другой стороны...

Если нумерация именно такова (у всех типов блоков совершенно одинакова, как в начальном посте), то несложно сделать простой, но достаточно любопытный вывод - блоки типа А при наличии хотя бы одного блока типа В или С по возможным вращениям полностью эквивалентны блокам типа В. Иными словами, если в структуре зафиксированы хотя бы один блок, расположенный "вертикально", и один блок, расположенный "горизонтально" - эту структуру замостить бесконфликтно невозможно в принципе. Можешь попробовать замостить полосу из 3 блоков (В-А-С), причём полоска на блоках В и С ориентирована одинаково (скажем, вертикально, тю.е. относительно первого твоего рисунка блок С повёрнут на 90 градусов) - хрен что у тебя получится.
Что в свою очередь тянет вывод, что для того, чтобы произвольный рисунок мог быть замощён блоками, должны существовать по два типа блоков В и С - с горизонтальной и с вертикальной полосой (при нумерации, как на первом рисунке).
А это приводит к выводу, что в таком случае достаточно просто выбрать ориентацию нумераций (либо "горизонтально", либо "вертикально"), и в нужных местах использовать блоки типов В и С нужной ориентации полосы на них.

Ну, если посмотреть внимательно, то задача очень простая
Каждый блок имеет одно из 4-х состояний, пронумеруем, например, по числу из правого нижнего угла
Какие соседи могут быть у блока с состоянием 1? Только 1 или 3
для блока с состоянием 2 соседями могут быть только 2 и 4
и т.д.
Т.е. задача решается, если все блоки типа B и C имеют одинаковую чётность

спасибо за участие в обсуждении!!

задача оказалась еще проще. я картинки из первого поста делала в inkscape. посидела в нем еще немного, покрутила блоки и вот к чему пришла: если в структуре есть хотя бы один ориентированный блок (B или C), то степеней свободы у такой структуры очень мало.

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

если два блока соединены, то любой один из них можно провернуть на 180, и это положение тоже будет соединяемым (говорю только о нумерации углов). но если к двум соединенным зафиксированным блокам добавить третий, который должен присоединяться к обоим, то у него есть только одно возможное положение. т.е. если в структуре все блоки соединяются как минимум с 3 другими (т.е. нет "мостов" шириной в 1 блок), то проворот каждого блока однозначно задается положением любых двух выбранных фиксированных блоков, и проверка возможности соединения всей структуры сводится к скромному числоу проходов по ней, начиная с любых двух выбранных соседних блоков. если в структуре есть блок C, тогда вся проверка выполнится за 2 прохода (два возможных положения комплекса из выбранного блока C и какого-то из соседних с ним). если C нет, но есть блок B, проходов будет 4 (т.к. сам B тоже можно провернуть. а может быть и 2 будет достаточно, если поворот B на 180 рассматривать как поворот всей структуры на 180). если вся структура состоит из блоков A, тогда задача всегда имеет решение.

итого осталось учесть ситуацию с мостами шириной в 1 блок, и готово  

Добавлено @ 13:38

у меня есть пример структуры, в которой по два блока B и C "одинаковой четности", и которую нельзя соединить

вот даже еще проще пример несоединяемой структуры с двумя C "одинаковой четности"


а если добавать один ряд из A, тогда структура станет соединяемой


Это сообщение отредактировал(а) Makise - 5.6.2015, 13:50

Что-то не возьму я в толк - что в данном случае названо несоединяемостью? Вполне себе замощено, вроде конфликтных узлов не видать...

1-1 и 4-4 встречаются в точке соединения

Пффф... приехали... да при ТАКОМ условии (если ещё и у соседа по диагонали не должен быть тот же номер) у тебя вообще положение ЛЮБОЙ ОДНОЙ "внутренней" (для которой хотя бы на одном из углов имеется 3 соседа) плитки полностью определяет ориентацию ВСЕХ внутренних плиток узора, если между ними можно построить путь из только внутренних плиток. Т.е. степени свободы имеет только полоса шириной в 1 плитку. Убери на этом своём рисунке любой (скажем, правый) вертикальный крайний ряд - и всё равно узор останется несовместным.

Можно: http://hkar.ru/Daat.