Создание всех уникальных комбинаций для головоломки «drive ya nuts»

Question

A while back Я написал простую программу python для перебора единственного решения для головоломки с ядром гайки.

alt text 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, так как каждому возможному решению эквивалентно- другие решения (просто поверните всю головоломку на 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.