"drive ya nuts"퍼즐에 대한 모든 고유 한 조합 생성

Question

이전에 단순한 python 프로그램을 사용하여 드라이브에 대한 단일 솔루션을 강요했습니다.

alt text http://www.tabbykat.com/Drive%20ya%20Nuts%20Travel%20Sol%20c.jpg

퍼즐은 숫자 그들에 1-6 7 개 육각형로 구성되며, 각 숫자는 다음 조각에 같은 번호에 인접 있도록 모든 조각을 정렬되어야합니다.

퍼즐은 ~1.4G 고유하지 않은 가능성을 가지고 : 당신이 순서에 의해 조각을 정렬 할 수 7! 옵션이 있습니다 (예를 들어, center=0, top=1, ... 시계 방향으로 순서 계속). 조각을 정렬 한 후에는 각 조각을 6 가지 방법으로 회전 할 수 있습니다 (각 조각은 육각형입니다). 따라서 7 조각의 주어진 순열에 대해 6**7 가능한 순환을 얻을 수 있습니다. 총계 : 7!*(6**7)=~1.4G 가능성. 각각의 가능한 솔루션은 5에 해당하기 때문에 당신이 6 가능성의 총 수를 분할해야한다 그러나

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독특한 가능한 해결책을 가지고 있습니다 : 다음 파이썬 코드는이 가능한 솔루션을 생성 다른 솔루션 (단순히 전체 퍼즐을 1/6 회전).

유일한 퍼즐을 생성하는 더 좋은 방법은이 퍼즐을위한일까요?

Answer 1

고유 한 유효한 솔루션 만 얻으려면 가운데에서 조각의 방향을 고정 할 수 있습니다. 예를 들어, 중앙의 조각에있는 "1"은 항상 "위로"향하고 있다고 가정 할 수 있습니다.

아직 작성하지 않은 경우 각 프로그램을 배치 한 후 올바른 솔루션을 확인하여 훨씬 효율적으로 프로그램을 만들 수 있습니다. 잘못된 방법으로 두 조각을 배치하면 다른 모든 잘못된 조합을 열거 할 필요가 없습니다.

Answer 2

중앙에 조각이 없다면 이것은 쉽습니다. 조각 0이 맨 위에있는 상황 만 고려하면됩니다.

그러나 우리는 그 생각을 실제 상황까지 확장 할 수 있습니다. 조각 i이 가운데에 있고 (i+1) % 7 부분이 맨 위에있는 상황 만 고려할 수 있습니다.

Answer 3

검색 공간이 아주 작다고 생각합니다. 프로그래밍은 어색 할 수 있습니다.

센터 피스에는 7 가지 선택 사항이 있습니다. 그 다음 위의 그림은 위의 6 가지 선택 항목이 있지만 방향이 고정되어 있습니다. 하단 가장자리가 가운데 조각의 상단 가장자리와 일치해야하며 마찬가지로 슬롯에 들어가는 조각을 선택할 때마다 방향이 고정됩니다.

나머지 조각에 대한 선택의 수가 줄어 듭니다. 우리가 그림에서와 같이 센터 피스와 탑 피스를 선택한 예제를 으로 가정하십시오. 오른쪽 상단 피스는 피스와 일치하도록 (시계 방향으로) 연속적인 모서리 (5,3)를 가져야하며,이 중 3 개의 피스는 오직 한 쌍의 모서리를 갖습니다 (실제로 이미 중앙 조각으로).

먼저 각 엣지 쌍에 대해 개의 조각 목록을 가진 테이블을 작성한 다음, 42 개의 중앙 및 상단 선택 항목 각각에 대해 시계 방향으로 진행하고 필요한 모서리 쌍이있는 조각 중에서 선택하십시오 (센터 피스와 이전에 배치 된 피스와 일치시키기 위해) 그리고 그런 조각이 없다면 역 추적.

가장 일반적인 가장자리 쌍은 4 조각에서 발생하며 (1,6) 2 개의 다른 가장자리 쌍 ((6,5) 및 (5,3))은 3 조각에서 발생하며 9 개의 가장자리 2 조각에서 발생하는 쌍, 1 조각에 발생하는 14 과 4는 전혀 발생하지 않습니다. 그래서 우리가해야하는 선택의 수에 대한 매우 비관적 인 예측은 7 * 6 * 4 * 3 * 3 * 2 또는 3024입니다.