Что такое эффективный алгоритм решения головоломки Jigshaw?

Question

Вчера я просто играл в Jigshaw Puzzle и почему-то задавался вопросом, каким будет алгоритм его решения.

Как человека, шаги, которые я последовал где:

1. Отдельные все части в 3-х частей, одной плоской кромки, двойной плоской кромки и кромки не на всех.
2. Отдельные плоские краевые части, как они были бы углы изображения
3. Отдельные куски одного края, как они образуют 4 торцевые кромки изображений
4. Наконец, куски без каких-либо кромок будет образовывать внутреннее изображения.
5. Сопоставьте цвета и части изображения, чтобы собрать их вместе.

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

Спасибо.

Answer 1

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

Вот мои мысли о подходе к написанию программы для решения такой загадки.

Есть четыре ключевых элементов информации, которые можно использовать по отдельности и вместе, как ключи к решению головоломки:

1. информация Форма каждой из частей (как выглядят их края)
2. информация о цветах каждой из частей (смежные части обычно имеют плавные переходы)
3. Информация о ориентации каждой детали (где могут быть плоские и угловые края)
4. Общий размер и количество деталей обеспечивают общие размеры o f the puzzle

Какая информация будет предоставлена ​​программой? Предположим, что каждая головоломка представляет собой небольшое прямоугольное изображение с информацией о прозрачности, используемой для идентификации части куска головоломки, которая представляет собой непрямоугольные ребра ,

Относительно легко идентифицировать четыре угловых элемента (в типичной лобзике). Они имеют ровно два ребра, которые имеют плоские контуры (см. Схему контура ниже).

Далее я бы построил информацию о форме каждого из четырех краев кусочка головоломки. Эта информация может быть использована для построения adjacency matrix, указывающего, какие части подходят друг к другу.

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

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

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

Answer 2

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

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

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

Это, конечно, как раз от головы.

Answer 3

Удостоверьтесь, что вы просматриваете детали для мужчин и женщин - это сократит поиск пополам.

Answer 4

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

Учитывая набор изображений всех частей, я попытался бы получить простой дескриптор для каждой части или края. Дескриптор должен содержать информацию о грубой форме и цвете части, соответственно, четырех краях. Учитывая головоломку с 1000 штуками, есть 4000 ребер, и всегда два должны быть равны (игнорируя границу головоломки). Вследствие этого дескриптор должен иметь возможность отличать 2000 ребер, требующих не менее 11 бит.

Разделение одной части на 3-х контрольную панель с девятью полями даст три цвета на край - с восемью битами на канал у нас уже есть 72 бит. Сначала я имел тенденцию предлагать уменьшить цветовое разрешение, но это, кажется, не очень хорошая идея - например, голубое небо может действительно выиграть от высокого разрешения цвета. Обратите внимание, что для вычисления цветов, вероятно, требуется отделить кусок от фона и попытаться совместить края с горизонтальной и вертикальной осями.

В очень однородных областях, таких как голубые небеса, информации о цветах, вероятно, будет недостаточно, чтобы найти хорошие соответствия, и потребуется дополнительная геометрическая информация. Я попытался бы описать форму ребра на его curvature или производную меру. Может быть, пробовал от 10 до 20 очков за край. Вероятно, это снова связано с разделением фона и выравниванием краев.

Наконец, компьютер может сделать легкую часть - сравнить все пары описателей границ и найти лучшие совпадения. Этот процесс, вероятно, должен контролироваться, чтобы стать более локальным, а не простым лучшим совпадением, потому что когда вы нашли угол (правильное английское слово? Я имею в виду три части в L-форме.) У вас есть два края, сдерживающие кусок, чтобы найти и можно отследить назад, если не найдено хорошего совпадения (с указанием ошибки, сделанной ранее или жесткой загадкой).

Answer 5

Пройдя это, я подумал о интересном решении, которое решает его с увеличением затрат за несколько этапов.

1. Отделить все кусочки головоломки от наборов из двух. Протестируйте, чтобы убедиться, что они подходят друг другу. Если нет, попробуйте другой кусок, который он не видел раньше. Если это так, поставьте набор в правильную кучу. Повторяйте до тех пор, пока все наборы из двух не найдут совпадение.

2. Из правильной сваи комбинируйте набор из двух элементов, чтобы сделать набор с наборами из двух элементов i.e {{1,2}, {5,6}}. Посмотрите, если хотя бы один кусочек головоломки из одного набора из двух приемов, по крайней мере с другой частью головоломки из другого набора из двух. Если нет, попробуйте другой набор из двух, которые он не видел раньше. Если это так, объедините два набора в один набор из четырех в правильной ориентации с частью, которую вы нашли, чтобы поместиться вместе и поместите комбинированный набор в правильную кучу. Повторяйте до тех пор, пока не будут найдены все четыре набора.

3. Повторите шаги до тех пор, пока конечная проблема, когда набор n/2 не будет объединен с набором n/2.

Непонятно, какими будут расчеты для этого.