4

しばらく前に、単純な python プログラムを作成して、ドライブ ヤ ナッツ パズルの単一のソリューションをブルート フォースしました。

代替テキスト
(ソース: tabbykat.com )

パズルは 1 ～ 6 の数字が書かれた 7 つの六角形で構成され、すべてのピースを並べて、各数字が次のピースの同じ数字に隣接するようにする必要があります。

パズルには~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 一意の可能なソリューションしかないことに注意してください。各可能なソリューションは他の 5 つのソリューションに相当するため、可能なソリューションの総数を 6 で割る必要があります (パズル全体を 1/6 回転させるだけです)。

このパズルのユニークな可能性だけを生成するより良い方法はありますか?

4

3 に答える 3

5

一意の有効なソリューションのみを取得するには、ピースの向きを中央に固定します。たとえば、中央のピースの「1」は常に「上」を指していると想定できます。

まだ行っていない場合は、各ピースを配置した後に有効なソリューションをチェックすることで、プログラムをより効率的にすることができます。2 つのピースを無効な方法で配置したら、他の無効な組み合わせをすべて列挙する必要はありません。

于 2010-04-08T15:39:58.373 に答える
3

中心にピースがなければ、これは簡単です。ピースが一番上にある状況だけを考えてみて0ください。

しかし、その考えを実際の状況に拡張することはできます。i駒が中央にあり、駒が上にある状況だけを考えることができます(i+1) % 7。

于 2010-04-08T15:00:25.673 に答える
1

プログラミングは厄介かもしれませんが、検索スペースはかなり小さいと思います。

センターピースには7つの選択肢があります。次に、その上のピースには6つの選択肢がありますが、その下端が中央のピースの上端と一致する必要があるため、その向きは固定されています。同様に、スロットに入れるピースを選択するたびに、向きが固定されます.

残りのピースの選択肢は少なくなります。たとえば、写真のようにセンター ピースとトップ ピースを選択したとします。次に、右上のピースには、所定のピースと一致するように (時計回りに) 連続したエッジ (5,3) が必要であり、そのようなエッジのペアを持つピースは 3 つだけです (実際、それらの 1 つをセンターピース）。

最初に、各エッジ ペアのピースのリストを含むテーブルを作成し、次に中央と上部の 42 の選択肢のそれぞれについて、必要なエッジ ペアを持つピースの中からのみを選択して時計回りに進みます (中央のピースに一致させるため)。と前に配置されたピース) およびそのようなピースがない場合はバックトラック。

最も一般的なエッジのペアは (1,6) であり、4 つのピースで発生し、他の 2 つのエッジのペア ((6,5) と (5,3)) は 3 つのピースで発生し、9 つのエッジのペアで発生します。 2 ピース、1 ピースで発生する 14 個とまったく発生しない 4 個。したがって、私たちがしなければならない選択の数の非常に悲観的な見積もりは、7*6*4*3*3*2 または 3024 です。

于 2010-07-23T18:46:45.263 に答える