Каков хороший подход к решению головоломок Tangram в Прологе?

Question

Я не уверен, что это лучше всего здесь или в математике, но я полагаю, что я могу также получить некоторые подсказки о коде. Для выполнения задания мне нужно решить выпуклые головоломки Tangram , используя Prolog.

Все головоломки и доступные кусочки определяются как списки вершин. Например: puzzle(1,[(0,0),(4,0),(4,4),(0,4)]) представляет собой квадратную головоломку, а piece(1,[(0,0),(4,0),(2,2)]) может быть одним из больших треугольников.

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

Большинство заданий в этом курсе основаны на классических комбинаторных задачах, таких как коммивояжер. Существуют ли такие проблемы, связанные с выпуклыми формами (или любой другой формой), которые могут вдохновить меня на поиск решения? Мне трудно найти в Интернете примеры декларативного кода, который имеет дело с формами таким образом. Было бы очень полезно, если бы я знал, что искать.

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

Answer 1

Вам нужно решить проблему с помощью чистого Пролога, или вы также можете использовать Constraint Programming?

Если вы можете использовать CP, взгляните на этот документ: Перспективы логических подходов к рассуждениям о действиях и изменениях .В разделе 6 описывается, как авторы решили танграмму с помощью CLP (FD).

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

Я также помню, что кто-то в курсе CLP, который я давным-давно взял, использовал основы Грёбнера для рассуждений о геометрии ("как переместить пианино в узкий угол? "), хотя я не уверен, будет ли это применимо для решения танграмм.

Извините, если это все немного теоретически и продвинуто.

Answer 2

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

Каждая фигура может быть представлена ​​как объединение наименьших треугольников, возникающих в результате разбиения единичной сетки.У нас есть всего 100 (4 * 5 * 5) маленьких треугольников.

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

Например, нумерация в восходящих координатах и ​​по часовой стрелке, piece(1, [(0,0), (1,1), (2,0)]) становится [2, 3, 4, 7].

Поворот формы по часовой стрелке на 90 ° вокруг начала координат это легко, если заметить, что для каждого поворота: X'= Y и Y' = - X.Часть выше, повернутая на 90 ° по часовой стрелке: часть (1, [(0,0), (1, -1), (0, -2)]).При нормализации по Y: кусок (1, [(0,2), (1,1), (0,0)]).

Определение того, какие маленькие треугольники покрывают форму, можно сделать наивно, повторяя ' точка в многоугольнике 'тест для каждого маленького треугольника.