Генерация всех уникальных комбинаций для головоломки "Drive Ya Nuts"

Question

Некоторое время назад я написал простую программу на python, чтобы перебрать единственное решение для загадки Drive and Nuts.

альтернативный текст http://www.tabbykat.com/Drive%20ya%20Nuts%20Travel%20Sol%20c.jpg

Головоломка состоит из 7 шестиугольников с номерами 1-6 на них, и все части должны быть выровнены так, чтобы каждое число было смежно с тем же числом на следующей части.

Головоломка имеет ~1.4G неуникальных возможностей: у вас есть 7! вариантов сортировки кусочков по порядку (например, center=0, top=1, продолжая по часовой стрелке ...). После того, как вы отсортировали фигуры, вы можете вращать каждую фигуру 6 способами (каждая фигура представляет собой шестиугольник), так что вы получаете 6**7 возможных вращений для данной перестановки из 7 фигур. Итого: 7!*(6**7)=~1.4G возможностей. Следующий код Python генерирует эти возможные решения:

def rotations(p):
    for i in range(len(p)):
        yield p[i:] + p[:i]

def permutations(l):
    if len(l)<=1:
        yield l
    else:
        for perm in permutations(l[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + l[0:1] + perm[i:]

def constructs(l):
    for p in permutations(l):
        for c in product(*(rotations(x) for x in p)):
            yield c

Тем не менее, обратите внимание, что головоломка имеет только ~0.2G уникальных возможных решений, так как вы должны разделить общее количество возможностей на 6, так как каждое возможное решение эквивалентно 5 другим решениям (просто поверните все головоломка на 1/6 хода).

Есть ли лучший способ создать только уникальные возможности для этой головоломки?

Answer 1

Чтобы получить только уникальные действительные решения, вы можете зафиксировать ориентацию фигуры в центре. Например, вы можете предположить, что «1» на фигуре в центре всегда указывает «вверх».

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

Answer 2

Если бы в центре не было фигуры, это было бы легко. Просто рассмотрим только те ситуации, когда фигура 0 находится наверху.

Но мы можем распространить эту идею на реальную ситуацию. Вы можете рассмотреть только ситуации, когда фигура i находится в центре, а фигура (i+1) % 7 вверху.

Answer 3

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

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

Есть меньше вариантов для оставшихся частей. Предположим для Например, мы выбрали центральную часть и верхнюю часть, как на рисунке; тогда верхняя правая часть должна иметь (по часовой стрелке) последовательные края (5,3), чтобы соответствовать частям в место, и только три из частей имеют такую ​​пару ребер (и на самом деле мы уже выбрал один из них в качестве центральной части).

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

Я считаю, что наиболее распространенной парой ребер является (1,6), которая встречается на 4 фигурах, две другие пары ребер ((6,5) и (5,3)) встречаются на 3 фигурах, существует 9 пар ребер которые происходят на две части, 14 которые встречаются на 1 части и 4, которые не встречаются вообще. Таким образом, очень пессимистическая оценка количества выборов, которые мы должны сделать, 7 * 6 * 4 * 3 * 3 * 2 или 3024.